# Proof of Zorn's Lemma using the Axiom of Choice. Why is $\mathscr U$ a tower?

I am reading a proof of Zorn's Lemma using the Axiom of Choice in Halmos' classical text, and I fail to see how to prove$\mathscr U$ satisfies the third condition of the definition of a tower. I will transcribe the relevant parts:

Let $X$ be any non empty set, and let $\mathscr X$ be a collection of subsets of $X$ subject to two conditions: first, every subset of a set in $\mathscr X$ is in $\mathscr X$. Second, the union of any chain in $\mathscr X$ is in $\mathscr X$.

Note that the condition "the union of any chain in $\mathscr X$ is in $\mathscr X$" is the same as saying every chain has an upper bound. We just stick to the partial order of inclusion instead of some abstract partial order. Halmos gives a justification by constructing a bijection between the elements of a poset and the weak initial segments of these elements.

Now, we take $f$ to be a choice function for $X$, and define a function $g:\mathscr X\to\mathscr X$ as follows. First, for $A\in\mathscr X$, let $\widehat A$ be the set elements of elements in $X$ such that $A\cup \{x\}$ is in $\mathscr X$. Then $\widehat A=A$ $\iff$ $A$ is maximal w.r.t. to inclusion in $\mathscr X$. Then we define $g(A)=A$ if $A=\widehat A$ ($\iff A$ is maximal) and $g(A)=A\cup\{f(\widehat A-A)\}$ otherwise.

So, the thing goes as follows now. Note that $g(A)$ contains at most one more element than $A$. We will say that a subcollection $\mathcal T$ of $\mathscr X$ is a tower if it contains the empty set, if $A\in\mathcal T$ implies $g(A)\in\mathcal T$ and if the union of any chain in $\mathcal T$ is again in $\mathcal T$.

We can consider the intersection of all towers in $\mathscr X$ since $\mathscr X$ itself is a tower (i.e. the collection is non-empty), obtaining the smallest tower $\mathcal T_0$. That this is a tower is clear. Halmos now seeks out to prove that $\mathcal T_0$ is indeed a chain. To this end, we will say that $C\in T_0$ is comparable if it is comparable to each element in $T_0$. Thus, we want to show that every $C\in T_0$ is comparable. Comparable sets exist, for example, $\varnothing$ is one.

Fix a comparable set $C$ in $T_0$, and let $A\in T_0$. We claim that $g(A)\subset C$. Since $C$ is comparable, either $g(A)\subseteq C$ or $C\subsetneq g(A)$. But in this last case we would have $A\subsetneq C\subsetneq g(A)$ which would mean $g(A)$ has two more elements than $A$; impossible.

Halmos now looks at $\mathscr U=\{A\in T_0:A\subseteq C \text{ or } g(C)\subseteq A\}$ This is a subset of the sets that are comparable to $g(C)$ in $T_0$. We want to show this is a tower, so that $T_0=\mathscr U$. I cannot see how to prove the third condition holds. The first two requierements I can see. That is, how do I show that if $\mathscr C$ is a chain in $\mathscr U$, $\bigcup \mathscr C$ is in $\mathscr U$? Halmos said it is obvious from the definition of $\mathscr U$, and that kinda put me down.

-

Either $C$ contains the union, or it does not. If it doesn't, then at least some element of the union lies outside $C$. Such an element must be contained in at least one of the sets in the chain. Let $B$ be such a set in the chain. Then $B$ does not lie in $C$, so $g(C)$ lies in $B$, so $g(C)$ lies in the union.
Thank you! ${}{}{}{}{}$ – Pedro Tamaroff Jul 5 '13 at 2:57