Axiom of Choice Implies Zorn's Lemma

From ProofWiki
Jump to navigation Jump to search

Theorem

Acceptance of the Axiom of Choice implies the truth of Zorn's Lemma.


Statement of Zorn's Lemma

Let $\left({X, \preceq}\right), X \ne \varnothing$ be a non-empty ordered set such that every non-empty chain in $X$ has an upper bound in $X$.


Then $X$ has at least one maximal element.


Proof 1

For each $x \in X$, consider the lower closure $x^\preceq$:

$x^\preceq = \set {y \in X: y \preceq x}$

Let $\mathbb S \subseteq \powerset X$ be the image of $\cdot^\preceq$ considered as a mapping from $X$ to $\powerset X$, where $\powerset X$ is the power set of $X$.

From Ordering is Equivalent to Subset Relation:

$\forall x, y \in X: x^\preceq \subseteq y^\preceq \iff x \preceq y$

Thus the task of finding a maximal element of $X$ is equivalent to finding a maximal set in $\mathbb S$.


Thus the statement of the result is equivalent to a statement about chains in $\mathbb S$:

Let $\mathbb S$ be a non-empty subset of $\powerset X, X \ne \O$ such that every non-empty chain in $\mathbb S$, ordered by $\subseteq$, has an upper bound in $\mathbb S$.
Then $\mathbb S$ has at least one maximal set.


Let $\mathbb X$ be the set of all chains in $\struct {X, \preceq}$.

Every element of $X$ is included in $\map {s^\preceq} x$ for some $x \in X$.

$\mathbb X$ is a non-empty set of sets which are ordered (perhaps partially) by subset relation.

If $\mathcal C$ is a chain in $\mathbb X$, then:

$\displaystyle \bigcup_{A \mathop \in \mathcal C} A \in \mathbb X$

Since each set in $\mathbb X$ is dominated by some set in $\mathbb S$, going from $\mathbb S$ to $\mathbb X$ can not introduce any new maximal elements.


The main advantage of using $\mathbb X$ is that the chain hypothesis is in a slightly more specific form.

Instead of saying that each chain in $\mathcal C$ has an upper bound in $\mathbb S$, we can explicitly state that the union of the sets of $\mathcal C$ is an element of $\mathbb X$.

This union of the sets of $\mathcal C$ is clearly an upper bound of $\mathcal C$.

Another advantage of $\mathbb X$ is that, from Subset of Toset is Toset, it contains all the subsets of each of its sets.

Thus we can enlarge non-maximal sets in $\mathbb X$ one element at a time.


So, from now on, we need consider only this non-empty collection $\mathbb X$ of subsets of a non-empty set $X$.

$\mathbb X$ is subject to two conditions:

$(1): \quad$ Every subset of each set in $\mathbb X$ is in $\mathbb X$.
$(2): \quad$ The union of each chain of sets in $\mathbb X$ is in $\mathbb X$.

It follows from $(1)$ that $\O \in \mathbb X$.

We need to show that there exists a maximal set in $\mathbb X$.


Let $f$ be a choice function for $X$:

$\forall A \in \powerset X \setminus \O: \map f A \in A$

For each $A \in \mathbb X$, let $\hat A$ be defined as:

$\hat A := \set {x \in X: A \cup \set x \in \mathbb X}$

That is, $\hat A$ consists of all the elements of $X$ which, when added to $A$, make a set which is also in $\mathbb X$.


From its definition:

$\displaystyle \hat A = \bigcup_{x \mathop \in \hat A} \paren {A \cup \set x}$

where each of $A \cup \set x$ are chains in $X$ and so elements of $\mathbb X$.

Suppose there exists a maximal set $M$ in $\mathbb X$.

Then, by definition of maximal, there are no elements in $x \in X \setminus M$ which can be added to $M$ to make $M \cup \set x$ another element of $\mathbb X$.

Thus it follows that $\hat M = M$.

From Set Difference with Self is Empty Set it then follows that if $A$ is maximal, then $\hat A \setminus A = \O$.


The mapping $g: \mathbb X \to \mathbb X$ can now be defined as:

$\forall A \in \mathbb X: \map g A = \begin{cases} A \cup \set {\map f {\hat A \setminus A} } & : \hat A \setminus A \ne \O \\ A & : \text{otherwise} \end{cases}$

Thus what we now have to prove is that:

$\exists A \in \mathbb X: \map g A = A$


Note that from the definition of $g$:

$\forall A \in \mathbb X: A \subseteq \map g A$

Also note that $\map f {\hat A \setminus A}$ is a single element of $\hat A \setminus A$.

Thus we obtain the crucial fact that $\map g A$ contains at most one more element than $A$.


We (temporarily) define a tower as being a subset $\mathcal T$ of $\mathbb X$ such that:

$(1): \quad \O \in \mathcal T$
$(2): \quad A \in \mathcal T \implies \map g A \in \mathcal T$
$(3): \quad $ If $\mathcal C$ is a chain in $\mathcal T$, then $\displaystyle \bigcup_{A \mathop \in \mathcal C} A \in \mathcal T$


There is of course at least one tower in $\mathbb X$, as $\mathbb X$ itself is one.

It follows from its definition that the intersection of a collection of towers is itself a tower.

It follows in particular that if $\mathcal T_0$ is the intersection of all towers in $\mathbb X$, then $\mathcal T_0$ is the smallest tower in $\mathbb X$.

Next we demonstrate that $\mathcal T_0$ is a chain.


We (temporarily) define a set $C \in \mathcal T_0$ as comparable if it is comparable with every element of $\mathcal T_0$.

That is, if $A \in \mathcal T_0$ then $C \subseteq A$ or $A \subseteq C$.

To say that $\mathcal T_0$ is a chain means that all sets of $\mathcal T_0$ are comparable.

There is at least one comparable set in $\mathcal T_0$, as $\O$ is one of them.


So, suppose $C \in \mathcal T_0$ is comparable.

Let $A \in \mathcal T_0$ such that $A \subsetneq C$.

Consider $\map g A$.

Because $C$ is comparable, either $C \subsetneq \map g A$ or $\map g A \subseteq C$.

In the former case $A$ is a proper subset of a proper subset of $\map g A$.

This contradicts the fact that $\map g A \setminus A$ can be no more than a singleton.

Thus if such an $A$ exists, we have that:

$(A): \quad \map g A \subseteq C$


Now let $\mathcal U$ be the set defined as:

$\mathcal U := \set {A \in \mathcal T_0: A \subseteq C \lor \map g C \subseteq A}$

Let $\mathcal U'$ be the set defined as:

$\mathcal U' := \set {A \in \mathcal T_0: A \subseteq \map g C \lor \map g C \subseteq A}$

That is, $\mathcal U'$ is the set of all sets in $\mathcal T_0$ which are comparable with $\map g C$.

If $A \in \mathcal U$, then as $C \subseteq \map g C$, either $A \subseteq \map g C \lor \map g C \subseteq A$

So $\mathcal U \subseteq \mathcal U'$.


The aim now is to demonstrate that $\mathcal U$ is a tower.

From Empty Set is Subset of All Sets, $\O \subseteq C$.

Hence condition $(1)$ is satisfied.


Now let $A \in \mathcal U$.

As $C$ is comparable, there are three possibilities:

$(1'): \quad A \subsetneq C$

Then from $(A)$ above, $\map g A \subseteq C$.

Therefore $\map g A \in \mathcal U$.

$(2'): \quad A = C$

Then $\map g A = \map g C$ and so $\map g C \subseteq \map g A$.

Therefore $\map g A \in \mathcal U$.

$(3'): \quad \map g C \subseteq A$

Then $\map g C \subseteq \map g A$

Therefore $\map g A \in \mathcal U$.

Hence condition $(2)$ is satisfied.


From the definition of $\mathcal U$, it follows immediately that the union of a chain in $\mathcal U$ is also in $\mathcal U$.

Hence condition $(3)$ is satisfied.


The conclusion is that $\mathcal U$ is a tower such that $\mathcal U \subseteq \mathcal T_0$.

But as $\mathcal T_0$ is the smallest tower, $\mathcal T_0 \subseteq \mathcal U$.

It follows that $\mathcal U = \mathcal T_0$.


Consider some comparable set $C$, then.

From that $C$ we can form $\mathcal U$, as above.

But as $\mathcal U = \mathcal T_0$:

$A \in \mathcal T_0 \implies \paren {A \subseteq C \implies A \subseteq \map g C} \lor \map g C \subseteq A$

and so $g \left({C}\right)$ is also comparable.


We now know that:

$\O$ is comparable
the mapping $g$ maps comparable sets to comparable sets.

Since the union of a chain of comparable sets is itself comparable, it follows that the comparable sets all form a tower $\mathcal T_C$.

But by the nature of $\mathcal T_0$ it follows that $\mathcal T_0 \subseteq \mathcal T_C$.

So the elements of $\mathcal T_0$ must all be comparable.


Since $\mathcal T_0$ is a chain, the union $M$ of all the sets in $\mathcal T_0$ is itself a set in $\mathcal T_0$.

Since the union includes all the sets of $\mathcal T_0$, it follows that $\map g M \subseteq M$.

Since it is always the case that $M \subseteq \map g M$, it follows that $M = \map g M$.

The result follows.

$\blacksquare$


Proof 2

Aiming for a contradiction, suppose that for each $x \in X$ there is a $y \in X$ such that $x \prec y$.

By the Axiom of Choice, there is a mapping $f: X \to X$ such that:

$\forall x \in X: x \prec \map f x$

Let $\mathcal C$ be the set of all chains in $X$.

By the premise, each element of $\mathcal C$ has an upper bound in $X$.

Thus by the Axiom of Choice, there is a mapping $g: \mathcal C \to X$ such that for each $C \in \mathcal C$, $\map g C$ is an upper bound of $C$.

Let $p$ be an arbitrary element of $X$.

Define a mapping $h: \operatorname {Ord} \to X$ by transfinite recursion thus:

\(\displaystyle \map h 0\) \(=\) \(\displaystyle p\)
\(\displaystyle \map h {\alpha^+}\) \(=\) \(\displaystyle \map f {\map h \alpha }\)
\(\displaystyle \map h \lambda\) \(=\) \(\displaystyle \map f {\map g {f \sqbrk \lambda} }\) if $\lambda$ is a limit ordinal



Then $h$ is strictly increasing, and thus injective.



Let $h'$ be the restriction of $h$ to $\operatorname {On} \times \map h {\operatorname{On} }$.

Then ${h'}^{-1}$ is a surjection from $\map h {\operatorname{On} } \subseteq X$ onto $\operatorname{On}$.

By the Axiom of Replacement, $\operatorname{On}$ is a set.

By Burali-Forti Paradox, this is a contradiction.

Thus we conclude that some element of $X$ has no strict successor, and is thus maximal.

$\blacksquare$