Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
Thank you! ${}{}{}{}{}$ –  Pedro Tamaroff Jul 5 '13 at 2:57
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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