# Tao, Analysis I: Exercise 8.5.14. Prove Zorn's Lemma.

Proposition(Zorn's Lemma): Let $X\neq\emptyset$ be of partial order with the property that $\forall Y\subseteq X$ such that $Y$ is of total-order then $Y$ has an upperbound, then $X$ contains a maximal element.

Proof: Case 1: $B\neq\emptyset$ such that $B$=$\{$$b\in X: b has an undefined order relation with all elements in X$$\}$. Thus, $\forall b\in B$, $b$ is maximal since there is no $x\in X$ where $b<x$.

Case 2: $B=\emptyset$; Let $I_1$ be some index set and let $Y_\alpha,\forall\alpha\in X_1$ denote all the totally-ordered sets in $X$. Consider that $\cup_{\alpha\in I_1}Y_\alpha$ is either a poset or a totally-ordered set in $X$. If $\cup_{\alpha\in I_1}Y_\alpha$ is totally ordered, then, by the premise of the lemma, $\cup_{\alpha\in I_1}Y_\alpha$ has an upperbound $\hat{y}$. Since $\hat{y}$ would then be an upperbound of all totally-ordered subsets of $X$, then no $x\in X$ satisfies $\hat{y}<x$. Hence, $\hat{y}$ is a maximal element in $X$. If $\cup_{\alpha\in I_1}Y_\alpha$ is a poset, then $\exists y_1,y_2\in\cup_{\alpha\in I_1}Y_\alpha$ such that the order relation $y_1$ and $y_2$ is undefined. In order to resolve this issue(of being unable to "compare"), we construct a set $\mathscr{T}$ of totally-ordered sets $\Bbb{T}(y)$ where $\forall\overline{y}\in\cup_{\alpha\in I_1}Y_\alpha$, we let \begin{align}\Bbb{T}(\overline{y})=\{y\in\cup_{\alpha\in I_1}Y_\alpha:y\leq_X\overline{y}\quad \lor\quad \overline{y}\leq_X y\}\end{align} Note that the correspondence of each $\overline{y}\in\cup_{\alpha\in I_1}Y_\alpha$ to a set $\Bbb{T}(\overline{y})$ is not one-to-one. Nevertheless, we have a collection $\mathscr{T}=\{\Bbb{T}(y):y\in\cup_{\alpha\in I_1}Y_\alpha\}=\{\Bbb{T}(y):y\in X\}$. Each $\Bbb{T}(y)$ is constructed in such a way so that $\forall\alpha\in I_1, \exists\Bbb{T}(y)\in\mathscr{T}$ such that $Y_\alpha\subseteq\Bbb{T}(y)$. Moreover, since $B=\emptyset$ and $\forall y\in\cup_{\alpha\in I_1}Y_\alpha$, $\Bbb{T}(y)$ contains the maximum number of elements from $X$ while remaining totally-ordered, then $\forall x_i\in X$ where $x_i\notin\Bbb{T}(y)$, it must be that $x_i\in\Bbb{T}(y')$ where $y$ and $y'$ have an undefined order-relation. Lastly, since we know that $\forall y\in X, \Bbb{T}(y)\subseteq X$ and is totally-ordered, then, by our premise, $\Bbb{T}(y)$ has an upperbound $\tau$ which I think is some maximal of $X$ because all upperbounds of each distinct $\Bbb{T}(y^*)\in\mathscr{T}$ are pair-wise undefined order relation(or incomparable). So for all upperbound $\tau$ in some $\Bbb{T}(y)$ there does not exist $x\in X$ such that $\tau <x$.

• There are several questions on the site with proofs of Zorn's Lemma. How about you look at those, and then try to figure out what you did wrong? May 31 '18 at 10:18
• there are so many of them. where should i start looking? May 31 '18 at 10:19
• If you're not even sure what kind of choice assumptions you are making, this exercise is not suited for you. May 31 '18 at 10:39
• (1) If you're interested in set theory, try a different source (e.g. Enderton's book). If you're interested in analysis, you can probably skip the set theory for now and use it as a black box instrument wherever it appears in the proofs. (2) Toiling for nothing is not a waste of time. May 31 '18 at 11:16
• @AsafKaragila In praise of failure is a good point to make and illustrates the priorities of an undergrad student. I did discrete math in grad school, since I didn't have it in undergrad. Of course I criticise some of the exercises, which is justified. But it's because I have understood mathematical logic (just because you learn in it in discrete math doesn't mean you'll understand it the same semester). Without logic, independent thought in mathematics is difficult if not nigh impossible :o May 31 '18 at 12:23

Case1. Assume $X$ is itself totally ordered.
You write: thus for a fixed element $b\in B$, $b$ is maximal.

Well, of course, you assumed $B=\emptyset$. What ever you claim for an element of $B$ is vacuously true, since there are no elements to check the condition against. No further justification is required.

We are still short a maximal element, however.

Case2. Do point out that $X$ does contain totally ordered subsets. For instance, since $X\neq\emptyset$, every singleton subset is totally ordered.

If we observe the union of all totally ordered subsets: $\bigcup Y_j \subseteq X$ and assume this is totally ordered, then we have assumed $X$ is totally ordered. Back to Case1.

The set $\mathbb T(y)$ is a chain in $X$ generated by $y$. $\mathbb T(x) = \mathbb T(y)$ iff $x,y$ are comparable i.e they are situated in the same chain. By premise of ZL the set $\mathbb T(y), y\in X$ is bounded. No maximal element in sight.

Your assumptions are too weak.

An alternative, is to assume the Axiom of Choice and proceed by this proof : AC implies ZL. Study proof 2, for it is far less involved.

Reading your post, I also get the feeling you mis-understand something about ZL. It doesn't say how many maximal elements there are. It certainly doesn't tell you the upper bound itself is a maximal element!

• Thank you for your time. Why wouldn't all other upperbounds not be in $\cup Y_j\subseteq X$? I was thinking that if $\beta$ is some other upperbound which was not included in $\cup Y_j\subseteq X$ and knowing that $\beta$ is an upperbound means there exist $x_0\in X$ such that $x_0<\beta$? So $\{x_0,\beta\}$ is a totally-ordered subset and must be in $\cup Y_j\subseteq X$. What am I missing here? Thank you again! May 31 '18 at 11:19
• Your example with $S=\bigcup_{P\in\cal P}P$ is odd. Every member of $X$ is a member of a chain. So $S=X$. So your argument shows that $X$ is totally ordered. Of course, this is not true, just look at $\{0,1\}$ with the identity order. May 31 '18 at 11:24
• @AsafKaragila uhh, right. I will remind myself of the correct construction. May 31 '18 at 11:26
• There is no way to "construct" this, you have to appeal to some magical witchcraft theorem that produces some intangible object. If you could construct the maximal objects, you could have proved the axiom of choice from ZF. May 31 '18 at 11:28
• @AsafKaragila Yeah, now I remember the witchcraft. Its results are completely different compared to the expectations of the OP. May 31 '18 at 11:44