| Version 3 |
Version 2 |
|
Let $X$ be a set partially ordered by $<$ such that each chain has an upper bound. Define $p(x)=\{y\in X\mid x< y\}\in P(X)$.
|
Let $X$ be a set partially ordered by $<$ such that each chain has an upper bound. Equate each $x\in X$ with $p(x)=\{y\in X\mid x< y\}\subseteq P(X)$.
|
| Let $p(X)=\{p(x)\mid x\in X\}$. If $p(x)=\emptyset$ then it follows that $x$ is maximal. |
Let $p(X)=\{p(x)\mid x\in X\}$. If $p(x)=\emptyset$ then it follows that $x$ is maximal. |
|
|
|
Suppose no $p(x)=\emptyset$. Then by the axiom of choice there is a choice function $f$ on $p(X)$, and since for each $p(x)$ we have $f(p(x))\in p(x)$, it follows that $x<f(p(x))$. Define $f_\alpha(p(x))$ for all ordinals $\alpha$ by transfinite induction:
|
Suppose no $p(x)=\emptyset$. Then by the axiom of choice there is a choice function $f$ on $p(X)$, and since for each $p(x)$ we have $f(p(x))\in p(x)$, it follows that $p(x)<f(p(x))$. Define $f_\alpha(p(x))$ for all ordinals $i$ by transfinite induction:
|
|
|
|
$f_0(p(x))=x$
|
$f_0(p(x))=p(x)$
|
|
|
|
$f_{\alpha+1}(p(x))=f(p(f_\alpha(x)))$
|
$f_{\alpha+1}(p(x))=f(p(x))$
|
|
|
| And for a limit ordinal $\alpha$, let $f_\alpha(p(x))$ be the upper bound of $f_i(p(x))$ for $i<\alpha$. |
And for a limit ordinal $\alpha$, let $f_\alpha(p(x))$ be the upper bound of $f_i(p(x))$ for $i<\alpha$. |
|
|
| This construction can go on forever, for any ordinal. Then we can easily construct a surjective function from $X$ to $Ord$ by $g(\alpha)=f_\alpha(x)$. But that requires that $X$ be a proper class, in contradiction to the fact that it is a set. So there can be no such choice function, and there must be a maximal element of $X$. |
This construction can go on forever, for any ordinal. Then we can easily construct a surjective function from $X$ to $Ord$ by $g(\alpha)=f_\alpha(x)$. But that requires that $X$ be a proper class, in contradiction to the fact that it is a set. So there can be no such choice function, and there must be a maximal element of $X$. |
|
|
| For the reverse, assume Zorn's lemma and let $C$ be any set of non-empty sets. Consider the set of functions $F=\{f\mid \forall a\in\operatorname{dom}(f) (a\in C \wedge f(a)\in a)\}$ partially ordered by inclusion. Then the union of any chain in $F$ is also a member of $F$ (since the union of a chain of functions is always a function). By Zorn's lemma, $F$ has a maximal element $f$, and since any function with domain smaller than $C$ can be easily expanded, $\operatorname{dom}(f)=C$, and so $f$ is a choice function $C$. |
For the reverse, assume Zorn's lemma and let $C$ be any set of non-empty sets. Consider the set of functions $F=\{f\mid \forall a\in\operatorname{dom}(f) (a\in C \wedge f(a)\in a)\}$ partially ordered by inclusion. Then the union of any chain in $F$ is also a member of $F$ (since the union of a chain of functions is always a function). By Zorn's lemma, $F$ has a maximal element $f$, and since any function with domain smaller than $C$ can be easily expanded, $\operatorname{dom}(f)=C$, and so $f$ is a choice function $C$. |
