Documentation

Mathlib.SetTheory.ZFC.PSet

Pre-sets #

A pre-set is inductively defined by its indexing type and its members, which are themselves pre-sets.

After defining pre-sets we define extensional equality over them, also inductively. We construct a Setoid instance from it, and in Mathlib/SetTheory/ZFC/Basic.lean we define ZFC sets as the quotient of pre-sets by extensional equality.

Main definitions #

inductive PSet :
Type (u + 1)

The type of pre-sets in universe u. A pre-set is a family of pre-sets indexed by a type in Type u. The ZFC universe is defined as a quotient of this to ensure extensionality.

The underlying type of a pre-set

Equations

The underlying pre-set family of a pre-set

Equations
@[simp]
theorem PSet.mk_type (α : Type u_1) (A : αPSet.{u_1}) :
(mk α A).Type = α
@[simp]
theorem PSet.mk_func (α : Type u_1) (A : αPSet.{u_1}) :
(mk α A).Func = A
@[simp]
theorem PSet.eta (x : PSet.{u_1}) :
mk x.Type x.Func = x

Two pre-sets are extensionally equivalent if every element of the first family is extensionally equivalent to some element of the second family and vice-versa.

Equations
theorem PSet.equiv_iff {x : PSet.{u_1}} {y : PSet.{u_2}} :
x.Equiv y (∀ (i : x.Type), ∃ (j : y.Type), (x.Func i).Equiv (y.Func j)) ∀ (j : y.Type), ∃ (i : x.Type), (x.Func i).Equiv (y.Func j)
theorem PSet.Equiv.exists_left {x : PSet.{u_1}} {y : PSet.{u_2}} (h : x.Equiv y) (i : x.Type) :
∃ (j : y.Type), (x.Func i).Equiv (y.Func j)
theorem PSet.Equiv.exists_right {x : PSet.{u_1}} {y : PSet.{u_2}} (h : x.Equiv y) (j : y.Type) :
∃ (i : x.Type), (x.Func i).Equiv (y.Func j)
theorem PSet.Equiv.euc {x : PSet.{u_1}} {y : PSet.{u_2}} {z : PSet.{u_3}} :
x.Equiv yz.Equiv yx.Equiv z
theorem PSet.Equiv.symm {x : PSet.{u_1}} {y : PSet.{u_2}} :
x.Equiv yy.Equiv x
theorem PSet.Equiv.trans {x : PSet.{u_1}} {y : PSet.{u_2}} {z : PSet.{u_3}} (h1 : x.Equiv y) (h2 : y.Equiv z) :
x.Equiv z

A pre-set is a subset of another pre-set if every element of the first family is extensionally equivalent to some element of the second family.

Equations
theorem PSet.Equiv.ext (x y : PSet.{u_1}) :
x.Equiv y x y y x
theorem PSet.Subset.congr_left {x y z : PSet.{u_1}} :
x.Equiv y → (x z y z)
theorem PSet.Subset.congr_right {x y z : PSet.{u_1}} :
x.Equiv y → (z x z y)
Equations
Equations
@[simp]
theorem PSet.le_def (x y : PSet.{u_1}) :
x y x y
@[simp]
theorem PSet.lt_def (x y : PSet.{u_1}) :
x < y x y
def PSet.Mem (y x : PSet.{u}) :

x ∈ y as pre-sets if x is extensionally equivalent to a member of the family y.

Equations
theorem PSet.Mem.mk {α : Type u} (A : αPSet.{u}) (a : α) :
A a PSet.mk α A
theorem PSet.func_mem (x : PSet.{u_1}) (i : x.Type) :
x.Func i x
theorem PSet.Mem.ext {x y : PSet.{u}} :
(∀ (w : PSet.{u}), w x w y)x.Equiv y
theorem PSet.Mem.congr_right {x y : PSet.{u}} :
x.Equiv y∀ {w : PSet.{u}}, w x w y
theorem PSet.equiv_iff_mem {x y : PSet.{u}} :
x.Equiv y ∀ {w : PSet.{u}}, w x w y
theorem PSet.Mem.congr_left {x y : PSet.{u}} :
x.Equiv y∀ {w : PSet.{u}}, x w y w
theorem PSet.mem_of_subset {x y z : PSet.{u_1}} :
x yz xz y
theorem PSet.subset_iff {x y : PSet.{u_1}} :
x y ∀ ⦃z : PSet.{u_1}⦄, z xz y
theorem PSet.mem_wf :
WellFounded fun (x1 x2 : PSet.{u_1}) => x1 x2
theorem PSet.mem_asymm {x y : PSet.{u_1}} :
x yyx
theorem PSet.mem_irrefl (x : PSet.{u_1}) :
xx
theorem PSet.not_subset_of_mem {x y : PSet.{u_1}} (h : x y) :
¬y x
theorem PSet.notMem_of_subset {x y : PSet.{u_1}} (h : x y) :
yx
@[deprecated PSet.notMem_of_subset (since := "2025-05-23")]
theorem PSet.not_mem_of_subset {x y : PSet.{u_1}} (h : x y) :
yx

Alias of PSet.notMem_of_subset.

Convert a pre-set to a Set of pre-sets.

Equations
@[simp]
theorem PSet.mem_toSet (a u : PSet.{u}) :
a u.toSet a u

A nonempty set is one that contains some element.

Equations
theorem PSet.nonempty_of_mem {x u : PSet.{u_1}} (h : x u) :
theorem PSet.Equiv.eq {x y : PSet.{u_1}} :

Two pre-sets are equivalent iff they have the same members.

@[simp]
theorem PSet.notMem_empty (x : PSet.{u}) :
x
@[deprecated PSet.notMem_empty (since := "2025-05-23")]
theorem PSet.not_mem_empty (x : PSet.{u}) :
x

Alias of PSet.notMem_empty.

@[simp]

Insert an element into a pre-set

Equations
@[simp]
theorem PSet.mem_insert_iff {x y z : PSet.{u}} :
x insert y z x.Equiv y x z
theorem PSet.mem_insert_of_mem {y z : PSet.{u_1}} (x : PSet.{u_1}) (h : z y) :
z insert x y
@[simp]
theorem PSet.mem_singleton {x y : PSet.{u_1}} :
x {y} x.Equiv y
theorem PSet.mem_pair {x y z : PSet.{u_1}} :
x {y, z} x.Equiv y x.Equiv z

The n-th von Neumann ordinal

Equations

The von Neumann ordinal ω

Equations

The pre-set separation operation {x ∈ a | p x}

Equations
theorem PSet.mem_sep {p : PSet.{u_1}Prop} (H : ∀ (x y : PSet.{u_1}), x.Equiv yp xp y) {x y : PSet.{u_1}} :
y PSet.sep p x y x p y

The pre-set powerset operator

Equations
@[simp]
theorem PSet.mem_powerset {x y : PSet.{u_1}} :

The pre-set union operator

Equations

The pre-set union operator

Equations
@[simp]
theorem PSet.mem_sUnion {x y : PSet.{u}} :
y ⋃₀ x zx, y z

The image of a function from pre-sets to pre-sets.

Equations
theorem PSet.mem_image {f : PSet.{u}PSet.{u}} (H : ∀ (x y : PSet.{u}), x.Equiv y(f x).Equiv (f y)) {x y : PSet.{u}} :
y image f x zx, y.Equiv (f z)

Universe lift operation

Equations

Embedding of one universe in another

Equations