An alternative to Zorn's lemma

The following theorem is independent of the axiom of choice, but the results in set theory traditionally deduced from Zorn's lemma can instead be deduced from this together with an elementary expression of the axiom of choice.

Theorem. Let φ a function whose domain D is a set of sets, such that∀x∈D, φ(x)∉x. Then there exists a unique subset K⊂D satisfying the following properties

• The restriction φ_|K is injective
• ∀x∈K, x⊂φ[K]
  
• The binary relation on K defined by (x,y)↦(φ(x)∈y)  is a strict well-ordering
• φ[K]∉D.

Proof.

Note : I'm not satisfied with this proof that is quite long and complicated. I hope to find a more elegant proof (through more interesting intermediate steps) in the future. In particular I'll surely re-write it as a consequence of Tarski's Fixed Point Theorem.

Let f be the function from P(D) to itself defined by:

• ∀x∈D, f({x}) =  {x∪{φ(x)}} if x∪{φ(x)}∈ D, or ∅ otherwise
• For any other A⊂D, f(A) = {∪A} if ∪A ∈ D, or ∅ otherwise. In particular, f(∅) = {∅}

If (∀y,y'∈K, ((y⊂A)∧ y∪{φ(y)}= y'⊂x)⇒y'⊂A)), then the set C={z∈K| z⊂x⇒z⊂A}is stable by f. Thus C=K. But x∈K, thus x⊂x⇒x⊂A. Finally A=x.

Let us show that C={x∈K|∀y∈K, x⊂y∨y⊂x}is stable by f. The stability by unions is straightforward : 

∀A⊂C, ∀y∈K, ((∃x∈A, y⊂x)⇒y⊂∪A ) and ((∀x∈A, x⊂y)⇒∪A⊂y)

Then ∀x∈C, ∀x',z∈K, x' = x∪{φ(x)}⇒((z⊂x⊂x')∨(x⊂z)). Now if x⊂z and φ(x)∉z then (∀y,y'∈K, (y⊂x ∧ y∪{φ(y)}= y'⊂z)⇒(x=y'∨x⊄y')⇒y'⊂x), so that x=z according to the above, and z⊂x'. In the other case of x⊂z and φ(x)∈z we have x'⊂z. Finally x'∈C.
Thus C is stable by f, thus C=K, thus ∀x,y∈K, (x⊂y ∨ y⊂x).

 ∀z,z'∈K, (z⊂x ∧ (z∪{φ(z)}= z'⊂y))⇒ (z'=x ∨ x⊄z') ⇒ z'⊂x.

Back to the main menu