2
$\begingroup$

Well-Ordering Principle implies Zorn's Lemma

Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help!


My attempt:

Let $(A,\preccurlyeq)$ be a partially ordered set in which every chain has an upper bound.

By Well-Ordering Principle, there is a well-ordering $\preccurlyeq'$ on $A$. Let $V$ be the class of all sets and $\rm Ord$ be the class of all ordinals. First, we define function $f:\mathcal{P}(A)\setminus\{\emptyset\} \to A$ by $f(X)=\min X$ (with regard to $\preccurlyeq'$).

Next, we define function $G:V \to V$ by $G(x)=f(\{a\in A \mid \forall t\in {\rm ran}(x):t \prec a\})$ if $x$ is a function and $\{a\in A \mid \forall t\in {\rm ran}(x):t \prec a\} \neq \emptyset$, and $G(x)=A$ otherwise. By Transfinite Recursion Theorem, there is a function $F: {\rm Ord} \to V$ such that $F(\alpha)=G(F \restriction \alpha)$ for all $\alpha \in {\rm Ord}$.

It is not hard to verify (by Hartogs number) that $F(\alpha)= A$ for some ordinal $\alpha$. Let $\lambda=\min\{\alpha \in {\rm Ord} \mid F(\alpha)= A\}$. Then ${\rm ran}(F\restriction \lambda)$ is clearly a chain in $(A,\preccurlyeq)$ and has an upper bound $u \in A$. If $u \prec \bar a$ for some $\bar a\in A$, we have $\bar a\in\{a\in A \mid \forall t\in {\rm ran}(F\restriction \lambda):t \prec a\} \neq \emptyset$ and thus $F(\lambda) \in A$. This contradicts the fact that $F(\lambda)=A$. So $u$ is the maximal element of $A$.

$\endgroup$
1
  • $\begingroup$ A different approach: Let $<_W$ be well-order of $A$. For $x\in Ord,$ if $f''x=\{f(y):y\in x\}$ is a $\leq$-chain in $A,$ let $f(x)$ be the $<_W$-least of the $\leq$-upper bounds for $f''x$. Let $x_0$ be the least $x\in Ord$ such that $\exists z\in Ord\,(x\in z\land f(x)=f(z)).$ Show by Transfinite Induction that $f''x$ is a $\leq$-chain for every $x\in Ord.$ Show that $x_0$ is a $\leq$-maximal member of $A.$..... (BTW we will have $f(z)=f(x_0)$ for every ordinal $z$ greater than $x_0.$)..... Some texts use $On$ for the class of ordinals. $\endgroup$ – DanielWainfleet Dec 22 '18 at 2:43
1
+50
$\begingroup$

The proof itself is correct (oops), but saying "clearly a chain" is not a good thing to do, at least state what you are using here like you did with Hartogs number.


Let me suggest a more intuitive proof:

First, the intuition: assuming that Zorn's lemma is false, every chain is bounded but there is no maximal element. Now we create a sequence $x_\beta$ to be strictly increasing sequence. Now if we build the sequence $\langle x_\beta\mid \beta<\alpha\rangle$ the set $\{x_\beta\mid \beta<\alpha\}$ is a chain, so it has an upper bound, $y$, and because $y$ is not maximal element there is $x_\alpha$ such that $y\prec x_\alpha$, so add $x\alpha$ to the sequence, you can keep going and exhaust the ordinal like that, which is impossible.

Now, formal proof for the above:

Let $V,(A,\preccurlyeq),f$ be defined as yours, assume that $A$ doesn't have maximal element, let $x_0\in A$, and $H:V\to V$ defined as followed:

If $g$ is not order preserving function from some ordinal to $A$ then $H(g)=x_0$(the Do not care case).

If $g$ is a function from $\beta\in Ord$ to $A$ and order preserving, then $g[\beta]$ is a chain, let $U$ be the set of upper bounds of $g[\beta]$, then take $f(U)$, now let $U'$ be the set of elements in $A$ that are greater than $f(U)$(with respect to $\prec$), by assumption $U'\ne \emptyset$, so $H(g)=f(U')$.

Now, by the theorem there exists unique $F:Ord\to A$ such that $F(\beta)=H(F\restriction\beta)$.

Use induction to prove that $F\restriction \gamma:\gamma\to A$ is order preserving for all $\gamma$, so $F\restriction \gamma:\gamma\to A$ is injective, set $\gamma=\mbox{Hartogs’ number}$ and you got a contradiction.

$\endgroup$
4
  • $\begingroup$ Hi @Holo, we have $F(\emptyset)=G(F \restriction \emptyset)=G(\emptyset)=f(\{a\in A \mid \forall t\in {\rm ran}(\emptyset):t \prec a\})=f(\{a\in A \mid \forall t\in \emptyset:t \prec a\})=f(A)\in A.$ Could you please have a closer check? $\endgroup$ – LE Anh Dung Dec 22 '18 at 1:52
  • $\begingroup$ @LeAnhDung sorry, you are correct ( I need to stop answering questions at 3 am). So yes, you are correct $\endgroup$ – ℋolo Dec 22 '18 at 12:22
  • $\begingroup$ You are very welcome :) $\endgroup$ – LE Anh Dung Dec 22 '18 at 12:25
  • $\begingroup$ @LeAnhDung I edit the answer (sorry it took me some time) and added my reasoning for why my method is more intuitive $\endgroup$ – ℋolo Dec 27 '18 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.