set_theory.zfc

A model of ZFC #

In this file, we model Zermelo-Fraenkel set theory (+ Choice) using Lean's underlying type theory. We do this in four main steps:

• Define pre-sets inductively.
• Define extensional equivalence on pre-sets and give it a setoid instance.
• Define ZFC sets by quotienting pre-sets by extensional equivalence.
• Define classes as sets of ZFC sets. Then the rest is usual set theory.

The model #

• pSet: Pre-set. A pre-set is inductively defined by its indexing type and its members, which are themselves pre-sets.
• Set: ZFC set. Defined as pSet quotiented by pSet.equiv, the extensional equivalence.
• Class: Class. Defined as set Set.
• Set.choice: Axiom of choice. Proved from Lean's axiom of choice.

Other definitions #

• arity α n: n-ary function α → α → ... → α. Defined inductively.
• arity.const a n: n-ary constant function equal to a.
• pSet.type: Underlying type of a pre-set.
• pSet.func: Underlying family of pre-sets of a pre-set.
• pSet.equiv: Extensional equivalence of pre-sets. Defined inductively.
• pSet.omega, Set.omega: The von Neumann ordinal ω as a pSet, as a Set.
• pSet.arity.equiv: Extensional equivalence of n-ary pSet-valued functions. Extension of pSet.equiv.
• pSet.resp: Collection of n-ary pSet-valued functions that respect extensional equivalence.
• pSet.eval: Turns a pSet-valued function that respect extensional equivalence into a Set-valued function.
• classical.all_definable: All functions are classically definable.
• Set.is_func : Predicate that a ZFC set is a subset of x × y that can be considered as a ZFC function x → y. That is, each member of x is related by the ZFC set to exactly one member of y.
• Set.funs: ZFC set of ZFC functions x → y.
• Class.iota: Definite description operator.

Notes #

To avoid confusion between the Lean set and the ZFC Set, docstrings in this file refer to them respectively as "set" and "ZFC set".

TODO #

Prove Set.map_definable_aux computably.

def arity (α : Type u) :
Type u

The type of n-ary functions α → α → ... → α.

Equations
• (n + 1) = (α → n)
• 0 = α
Instances for arity
def arity.const {α : Type u} (a : α) (n : ) :
n

Constant n-ary function with value a.

Equations
• (n + 1) = λ (_x : α), n
• 0 = a
@[protected, instance]
def arity.arity.inhabited {α : Type u_1} {n : } [inhabited α] :
Equations
inductive pSet  :
Type (u+1)
• mk : Π (α : Type ?), (α → pSet)pSet

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.

Instances for pSet
@[nolint]
def pSet.type  :
pSetType u

The underlying type of a pre-set

Equations
def pSet.func (x : pSet) :
x.typepSet

The underlying pre-set family of a pre-set

Equations
theorem pSet.mk_type_func (x : pSet) :
x.func = x
def pSet.equiv (x : pSet) (y : pSet) :
Prop

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
• x.equiv y = pSet.rec (λ (α : Type u_1) (z : α → pSet) (m : α → pSet → Prop) (_x : pSet), pSet.equiv._match_1 α m _x) x y
• pSet.equiv._match_1 α m (pSet.mk β B) = ((∀ (a : α), ∃ (b : β), m a (B b)) ∀ (b : β), ∃ (a : α), m a (B b))
theorem pSet.equiv.refl (x : pSet) :
x.equiv x
theorem pSet.equiv.rfl {x : pSet} :
x.equiv x
theorem pSet.equiv.euc {x : pSet} {y : pSet} {z : pSet} :
x.equiv yz.equiv yx.equiv z
theorem pSet.equiv.symm {x : pSet} {y : pSet} :
x.equiv yy.equiv x
theorem pSet.equiv.trans {x : pSet} {y : pSet} {z : pSet} (h1 : x.equiv y) (h2 : y.equiv z) :
x.equiv z
@[protected, instance]
Equations
@[protected]
def pSet.subset  :
pSetpSet → Prop

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
@[protected, instance]
Equations
theorem pSet.equiv.ext (x y : pSet) :
x.equiv y x y y x
theorem pSet.subset.congr_left {x y z : pSet} :
x.equiv y(x z y z)
theorem pSet.subset.congr_right {x y z : pSet} :
x.equiv y(z x z y)
def pSet.mem  :
pSetpSet → Prop

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

Equations
@[protected, instance]
Equations
theorem pSet.mem.mk {α : Type u} (A : α → pSet) (a : α) :
A a A
theorem pSet.mem.ext {x y : pSet} :
(∀ (w : pSet), w x w y)x.equiv y
theorem pSet.mem.congr_right {x y : pSet} :
x.equiv y∀ {w : pSet}, w x w y
theorem pSet.equiv_iff_mem {x y : pSet} :
x.equiv y ∀ {w : pSet}, w x w y
theorem pSet.mem.congr_left {x y : pSet} :
x.equiv y∀ {w : pSet}, x w y w
def pSet.to_set (u : pSet) :

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

Equations
theorem pSet.equiv.eq {x y : pSet} :

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

@[protected, instance]
Equations
@[protected]
def pSet.empty  :

The empty pre-set

Equations
@[protected, instance]
Equations
@[protected, instance]
Equations
theorem pSet.mem_empty (x : pSet) :
@[protected]
def pSet.insert  :
pSet

Insert an element into a pre-set

Equations
@[protected, instance]
Equations
@[protected, instance]
Equations
@[protected, instance]
def pSet.of_nat  :

The n-th von Neumann ordinal

Equations
def pSet.omega  :

The von Neumann ordinal ω

Equations
@[protected]
def pSet.sep (p : set pSet) :

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

Equations
@[protected, instance]
Equations
def pSet.powerset  :

The pre-set powerset operator

Equations
theorem pSet.mem_powerset {x y : pSet} :
def pSet.Union  :

The pre-set union operator

Equations
theorem pSet.mem_Union {x y : pSet} :
y x.Union ∃ (z : pSet) (_x : z x), y z
def pSet.image (f : pSetpSet) :

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

Equations
• (pSet.mk α A) = (λ (a : α), f (A a))
theorem pSet.mem_image {f : pSetpSet} (H : ∀ {x y : pSet}, x.equiv y(f x).equiv (f y)) {x y : pSet} :
y x ∃ (z : pSet) (H : z x), y.equiv (f z)
@[protected]
def pSet.lift  :

Universe lift operation

Equations
@[nolint]
def pSet.embed  :

Embedding of one universe in another

Equations
theorem pSet.lift_mem_embed (x : pSet) :
def pSet.arity.equiv {n : } :
→ Prop

Function equivalence is defined so that f ~ g iff ∀ x y, x ~ y → f x ~ g y. This extends to equivalence of n-ary functions.

Equations
theorem pSet.arity.equiv_const {a : pSet} (n : ) :
n)
def pSet.resp (n : ) :
Type (u+1)

resp n is the collection of n-ary functions on pSet that respect equivalence, i.e. when the inputs are equivalent the output is as well.

Equations
• = {x // x}
Instances for pSet.resp
@[protected, instance]
def pSet.resp.inhabited {n : } :
Equations
def pSet.resp.f {n : } (f : pSet.resp (n + 1)) (x : pSet) :

The n-ary image of a (n + 1)-ary function respecting equivalence as a function respecting equivalence.

Equations
def pSet.resp.equiv {n : } (a b : pSet.resp n) :
Prop

Function equivalence for functions respecting equivalence. See pSet.arity.equiv.

Equations
theorem pSet.resp.refl {n : } (a : pSet.resp n) :
a.equiv a
theorem pSet.resp.euc {n : } {a b c : pSet.resp n} :
a.equiv bc.equiv ba.equiv c
@[protected, instance]
Equations
def Set  :
Type (u+1)

The ZFC universe of sets consists of the type of pre-sets, quotiented by extensional equivalence.

Equations
Instances for Set
def pSet.resp.eval_aux {n : } :
{f // ∀ (a b : , a.equiv bf a = f b}

Helper function for pSet.eval.

Equations
def pSet.resp.eval (n : ) :
n

An equivalence-respecting function yields an n-ary ZFC set function.

Equations
Instances for pSet.resp.eval
theorem pSet.resp.eval_val {n : } {f : pSet.resp (n + 1)} {x : pSet} :
pSet.resp.eval (n + 1) f x = (f.f x)
@[class]
inductive pSet.definable (n : ) :
nType (u+1)
• mk : Π {n : } (f : , f)

A set function is "definable" if it is the image of some n-ary pre-set function. This isn't exactly definability, but is useful as a sufficient condition for functions that have a computable image.

Instances of this typeclass
Instances of other typeclasses for pSet.definable
• pSet.definable.has_sizeof_inst
def pSet.definable.eq_mk {n : } (f : pSet.resp n) {s : n} (H : = s) :

The evaluation of a function respecting equivalence is definable, by that same function.

Equations
def pSet.definable.resp {n : } (s : n) [ s] :

Turns a definable function into a function that respects equivalence.

Equations
theorem pSet.definable.eq {n : } (s : n) [H : s] :
noncomputable def classical.all_definable {n : } (F : n) :

All functions are classically definable.

Equations
def Set.mk  :

Turns a pre-set into a ZFC set.

Equations
@[simp]
theorem Set.mk_eq (x : pSet) :
@[simp]
theorem Set.eval_mk {n : } {f : pSet.resp (n + 1)} {x : pSet} :
pSet.resp.eval (n + 1) f (Set.mk x) = (f.f x)
def Set.mem  :
SetSet → Prop

The membership relation for ZFC sets is inherited from the membership relation for pre-sets.

Equations
@[protected, instance]
def Set.has_mem  :
Equations
def Set.to_set (u : Set) :

Convert a ZFC set into a set of ZFC sets

Equations
@[protected]
def Set.subset (x y : Set) :
Prop

x ⊆ y as ZFC sets means that all members of x are members of y.

Equations
@[protected, instance]
Equations
theorem Set.subset_def {x y : Set} :
x y ∀ ⦃z : Set⦄, z xz y
theorem Set.subset_iff (x y : pSet) :
x y
theorem Set.ext {x y : Set} :
(∀ (z : Set), z x z y)x = y
theorem Set.ext_iff {x y : Set} :
(∀ (z : Set), z x z y) x = y
def Set.empty  :

The empty ZFC set

Equations
@[protected, instance]
Equations
@[protected, instance]
Equations
@[simp]
theorem Set.mem_empty (x : Set) :
theorem Set.eq_empty (x : Set) :
x = ∀ (y : Set), y x
@[protected]
def Set.insert  :
Set

insert x y is the set {x} ∪ y

Equations
@[protected, instance]
Equations
@[protected, instance]
Equations
@[protected, instance]
@[simp]
theorem Set.mem_insert {x y z : Set} :
x x = y x z
@[simp]
theorem Set.mem_singleton {x y : Set} :
x {y} x = y
@[simp]
theorem Set.mem_pair {x y z : Set} :
x {y, z} x = y x = z
def Set.omega  :

omega is the first infinite von Neumann ordinal

Equations
@[simp]
theorem Set.omega_zero  :
@[simp]
theorem Set.omega_succ {n : Set} :
@[protected]
def Set.sep (p : Set → Prop) :

{x ∈ a | p x} is the set of elements in a satisfying p

Equations
@[protected, instance]
def Set.has_sep  :
Equations
@[simp]
theorem Set.mem_sep {p : Set → Prop} {x y : Set} :
y {y ∈ x | p y} y x p y
def Set.powerset  :

The powerset operation, the collection of subsets of a ZFC set

Equations
@[simp]
theorem Set.mem_powerset {x y : Set} :
theorem Set.Union_lem {α β : Type u} (A : α → pSet) (B : β → pSet) (αβ : ∀ (a : α), ∃ (b : β), (A a).equiv (B b)) (a : (pSet.mk α A).Union.type) :
∃ (b : (pSet.mk β B).Union.type), ((pSet.mk α A).Union.func a).equiv ((pSet.mk β B).Union.func b)
def Set.Union  :

The union operator, the collection of elements of elements of a ZFC set

Equations
@[simp]
theorem Set.mem_Union {x y : Set} :
y x.Union ∃ (z : Set) (H : z x), y z
@[simp]
theorem Set.Union_singleton {x : Set} :
{x}.Union = x
theorem Set.singleton_inj {x y : Set} (H : {x} = {y}) :
x = y
@[protected]
def Set.union (x y : Set) :

The binary union operation

Equations
@[protected]
def Set.inter (x y : Set) :

The binary intersection operation

Equations
@[protected]
def Set.diff (x y : Set) :

The set difference operation

Equations
@[protected, instance]
Equations
@[protected, instance]
Equations
@[protected, instance]
Equations
@[simp]
theorem Set.mem_union {x y z : Set} :
z x y z x z y
@[simp]
theorem Set.mem_inter {x y z : Set} :
z x y z x z y
@[simp]
theorem Set.mem_diff {x y z : Set} :
z x \ y z x z y
theorem Set.induction_on {p : Set → Prop} (x : Set) (h : ∀ (x : Set), (∀ (y : Set), y xp y)p x) :
p x
theorem Set.regularity (x : Set) (h : x ) :
∃ (y : Set) (H : y x), x y =
def Set.image (f : SetSet) [H : f] :

The image of a (definable) ZFC set function

Equations
• = let r : := in , _⟩
theorem Set.image.mk (f : SetSet) [H : f] (x : Set) {y : Set} (h : y x) :
f y x
@[simp]
theorem Set.mem_image {f : SetSet} [H : f] {x y : Set} :
y x ∃ (z : Set) (H : z x), f z = y
def Set.pair (x y : Set) :

Kuratowski ordered pair

Equations
• x.pair y = {{x}, {x, y}}
Instances for Set.pair
def Set.pair_sep (p : SetSet → Prop) (x y : Set) :

A subset of pairs {(a, b) ∈ x × y | p a b}

Equations
@[simp]
theorem Set.mem_pair_sep {p : SetSet → Prop} {x y z : Set} :
z x y ∃ (a : Set) (H : a x) (b : Set) (H : b y), z = a.pair b p a b
theorem Set.pair_inj {x y x' y' : Set} (H : x.pair y = x'.pair y') :
x = x' y = y'
def Set.prod  :
Set

The cartesian product, {(a, b) | a ∈ x, b ∈ y}

Equations
@[simp]
theorem Set.mem_prod {x y z : Set} :
z x.prod y ∃ (a : Set) (H : a x) (b : Set) (H : b y), z = a.pair b
@[simp]
theorem Set.pair_mem_prod {x y a b : Set} :
a.pair b x.prod y a x b y
def Set.is_func (x y f : Set) :
Prop

is_func x y f is the assertion that f is a subset of x × y which relates to each element of x a unique element of y, so that we can consider fas a ZFC function x → y.

Equations
def Set.funs (x y : Set) :

funs x y is y ^ x, the set of all set functions x → y

Equations
@[simp]
theorem Set.mem_funs {x y f : Set} :
f x.funs y x.is_func y f
@[protected, instance]
noncomputable def Set.map_definable_aux (f : SetSet) [H : f] :
(λ (y : Set), y.pair (f y))
Equations
noncomputable def Set.map (f : SetSet) [H : f] :

Graph of a function: map f x is the ZFC function which maps a ∈ x to f a

Equations
@[simp]
theorem Set.mem_map {f : SetSet} [H : f] {x y : Set} :
y x ∃ (z : Set) (H : z x), z.pair (f z) = y
theorem Set.map_unique {f : SetSet} [H : f] {x z : Set} (zx : z x) :
∃! (w : Set), z.pair w x
@[simp]
theorem Set.map_is_func {f : SetSet} [H : f] {x y : Set} :
x.is_func y (Set.map f x) ∀ (z : Set), z xf z y
@[protected, instance]
@[protected, instance]
@[protected, instance]
@[protected, instance]
def Class  :
Type (u_1+1)

The collection of all classes. A class is defined as a set of ZFC sets.

Equations
Instances for Class
@[protected, instance]
@[protected, instance]
@[protected, instance]
@[protected, instance]
@[protected, instance]
def Class.of_Set (x : Set) :

Coerce a ZFC set into a class

Equations
@[protected, instance]
Equations
def Class.univ  :

The universal class

Equations
def Class.to_Set (p : Set → Prop) (A : Class) :
Prop

Assert that A is a ZFC set satisfying p

Equations
@[protected]
def Class.mem (A B : Class) :
Prop

A ∈ B if A is a ZFC set which is a member of B

Equations
@[protected, instance]
Equations
theorem Class.mem_univ {A : Class} :
∃ (x : Set), x = A

Convert a conglomerate (a collection of classes) into a class

Equations
def Class.Class_to_Cong (x : Class) :

Convert a class into a conglomerate (a collection of classes)

Equations
def Class.powerset (x : Class) :

The power class of a class is the class of all subclasses that are ZFC sets

Equations
def Class.Union (x : Class) :

The union of a class is the class of all members of ZFC sets in the class

Equations
theorem Class.of_Set.inj {x y : Set} (h : x = y) :
x = y
@[simp]
theorem Class.to_Set_of_Set (p : Set → Prop) (x : Set) :
p x
@[simp]
theorem Class.mem_hom_left (x : Set) (A : Class) :
x A A x
@[simp]
theorem Class.mem_hom_right (x y : Set) :
y x x y
@[simp]
theorem Class.subset_hom (x y : Set) :
x y x y
@[simp]
theorem Class.sep_hom (p : Set → Prop) (x : Set) :
{y ∈ x | p y} = {y ∈ x | p y}
@[simp]
theorem Class.empty_hom  :
@[simp]
theorem Class.insert_hom (x y : Set) :
= y)
@[simp]
theorem Class.union_hom (x y : Set) :
x y = (x y)
@[simp]
theorem Class.inter_hom (x y : Set) :
x y = (x y)
@[simp]
theorem Class.diff_hom (x y : Set) :
x \ y = (x \ y)
@[simp]
@[simp]
theorem Class.Union_hom (x : Set) :
def Class.iota (p : Set → Prop) :

The definite description operator, which is {x} if {a | p a} = {x} and ∅ otherwise.

Equations
theorem Class.iota_val (p : Set → Prop) (x : Set) (H : ∀ (y : Set), p y y = x) :
= x
theorem Class.iota_ex (p : Set → Prop) :

Unlike the other set constructors, the iota definite descriptor is a set for any set input, but not constructively so, so there is no associated (Set → Prop) → Set function.

def Class.fval (F A : Class) :

Function value

Equations
theorem Class.fval_ex (F A : Class) :
@[simp]
theorem Set.map_fval {f : SetSet} [H : f] {x y : Set} (h : y x) :
(Set.map f x)y = (f y)
noncomputable def Set.choice (x : Set) :

A choice function on the class of nonempty ZFC sets.

Equations
theorem Set.choice_mem_aux (x : Set) (h : x) (y : Set) (yx : y x) :
classical.epsilon (λ (z : Set), z y) y
theorem Set.choice_is_func (x : Set) (h : x) :
theorem Set.choice_mem (x : Set) (h : x) (y : Set) (yx : y x) :