The following is the proof of the Hausdorff Maximality theorem in Rudin's real and complex analysis:

Hausdorff's Maximality Theorem Every nonempty partially ordered set $P$ contains a maximal totally ordered subset.

PROOF Let $\mathcal{F}$ be the collection of all totally ordered subsets of $P$. Since every subset of $P$ which consists of a single element is totally ordered, $\mathcal{F}$ is not empty. Note that if the union of any chain of totally ordered sets is totally ordered.
Let $f$ be a choice function for $P$. If $A \in \mathcal{F}$, let $A^*$ be the set of all $x$ in the complement of $A$ such that $A \cup \{x\} \in \mathcal{F}$. If $A^* \neq \emptyset$, put $$g(A) = A \cup \{ f (A^*) \}.$$ If $A^*=\emptyset$, put $g(A) = A$.

I'm having some trouble understanding what the collection of all totally ordered subsets of $P$ means, and what the union of chain of totally ordered sets means. More specifically, as an example, let $$P = \{ \{\phi_1, \phi_2\}, \{\phi_1, \phi_2, \phi_3\}, \{\phi_1, \phi_2, \phi_3, \dots\}, \dots, \{\psi_1, \psi_1\}, \{\psi_1, \psi_2, \psi_3\}, \{\psi_1, \psi_2, \psi_3, \dots\}, \dots \}$$ where $P$ contains $(\phi_n)_n$ and $(\psi_n)_n$ for all $n\in \mathbb{N}$. Clearly, $P$ is a partially ordered set by set inclusion. Then if $\mathcal{F}$ is the collection of all totally ordered subsets of $P$, does it mean that $\mathcal{F}$ is $$\mathcal{F} = \Big\{ \{ \{\phi_1, \phi_2\}\}, \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_2, \phi_3\}\}, \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_2, \phi_3\}, ...\}, \dots, \{\{\psi_1, \psi_2\} \}, \{\{\psi_1, \psi_2\}, \{\psi_1, \psi_2, \psi_3\} \}, \{\{\psi_1, \psi_2\}, \{\psi_1, \psi_2, \psi_3\}, \dots \}, \dots \Big\} ?$$ Also what does it mean when it says the union of any chain of totally ordered sets is totally ordered? Does it mean a union of two chains of totally ordered sets (e.g. union of $\{ \{\phi_1, \phi_2\}\}, \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_2, \phi_3\}\}$ and $\{\{\psi_1, \psi_2\} \}, \{\{\psi_1, \psi_2\}, \{\psi_1, \psi_2, \psi_3\} \}$)? Or is it a union of all the members of the chain of totally ordered sets? I took it as the latter since the former doesn't makes sense.

However, I don't understand why it is necessary to define it in such a way. For instance, $\{\{\phi_1, \phi_2, \phi_3, \dots\}\}$ is totally ordered since the union of the chain $\{ \{\phi_1, \phi_2\}\}, \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_2, \phi_3\}\}, \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_2, \phi_3\}, ...\}$ is $\{\{\phi_1, \phi_2, \phi_3, \dots\}\}$. However, isn't $\{\{\phi_1, \phi_2, \phi_3, \dots\}\}$ always totally ordered since it is a subset of a single element?

  • $\begingroup$ No, a chain of subsets of P is not a totally ordered subset of P. $\endgroup$ Jun 29 '21 at 2:43
  • $\begingroup$ isn't chain, by definition, totally ordered? or is that a subchain? $\endgroup$
    – MoneyBall
    Jun 29 '21 at 3:11
  • $\begingroup$ They are synonyms. $\endgroup$ Jun 29 '21 at 8:55
  • $\begingroup$ some small comments. (1) Your $P$ is missing $\{\phi_1\}$ and $\{\psi_1\}$. (2) Your $\mathcal F$ is missing a lot of elements, see my answer below (in fact $\mathcal F$ is uncountable, and thus cannot be written down with "..."). (3) You don't take the union of two chains, but the union of a single chain that consists of totally ordered sets. (4) In your last paragraph, the union is $\{\{\phi_1,\phi_2\},\{\phi_1,\phi_2,\phi_3\},\dots\}$, not $\{\{\phi_1,\phi_2,\dots\}\}$ (the latter would be like taking the union of the union, and then putting the result in a singleton set). $\endgroup$
    – Vsotvep
    Jun 29 '21 at 13:11

I assume that $\Bbb N=\{1,2,\dots\}$, and thus does not include $0$.

Your example $P$ is essentially the disjoint union of two copies of $\Bbb N$. I believe it will be helpful to rename the sets $\{\phi_1,\dots,\phi_n\}$ so that you do not get lost in nested sets. We can name $a_n=\{\phi_1,\dots,\phi_n\}$ and $b_n=\{\psi_1,\dots,\psi_n\}$ for each $n\in\Bbb N$, then $P=\{a_n\mid n\in\Bbb N\}\cup \{b_n\mid n\in\Bbb N\}$. Let $\preceq$ be the partial order, i.e.

\begin{align} a_n\preceq a_m \quad\text{ iff }\quad n\leq m\quad\text{ iff }\quad\{\phi_1,\dots,\phi_n\}\subseteq\{\phi_1,\dots,\phi_m\},\end{align}

and similarly

\begin{align} b_n\preceq b_m \quad\text{ iff }\quad n\leq m\quad\text{ iff }\quad\{\psi_1,\dots,\psi_n\}\subseteq\{\psi_1,\dots,\psi_m\}, \end{align}

while we also have $a_n\mathbin{\not{\!\!\preceq}} b_m$ for any $n,m\in\Bbb N$.

What does the collection of all totally ordered subsets of $P$ mean? We'll denote this set with $\mathcal F$. Usually we don't have to write out $\mathcal F$ explicitly, but for your example this is easy: if $x,x'\in P$ and $x\mathbin{\not{\!\!\preceq}}x'$ and $x'\mathbin{\not{\!\!\preceq}}x$, then we know that $x=a_n$ and $x'=b_m$ for some $n,m$, or vice versa.

Hence, a set of elements of $P$ is totally ordered if and only if it is empty, exclusively contains elements of the form $a_n$ or exclusively contains elements of the form $b_n$. More formally, $Y\in \mathcal F$ if and only if there exists some $X\subseteq\Bbb N$ such that $Y=\{a_n\mid n\in X\}$ or $Y=\{b_n\mid n\in X\}$.

For example, $\{a_{12},a_{1},a_{2748},a_{52}\}\in\mathcal F$, since $a_1\preceq a_{12}\preceq a_{52}\preceq a_{2748}$, but $\{a_4,b_{26},a_5\}\notin \mathcal F$, since $a_4\mathbin{\not{\!\!\preceq}}b_{26}$ and $b_{26}\mathbin{\not{\!\!\preceq}}a_4$. Note that $\mathcal F$ may also contain infinite sets, such as $\{a_n\mid n\text{ is even}\}$.

In general, for any partially ordered $P$ we may simply define $\mathcal F$ without knowing what its elements are. A subset $X\subseteq P$ either is totally ordered, or it is not. If $X$ is totally ordered, then $X\in \mathcal F$, and if $X$ is not totally ordered, then $X\notin \mathcal F$.

Finally we have the claim that the union of a $\subseteq$-chain in $\mathcal F$ is totally ordered by $\preceq$. Let $(I,\leq)$ be some totally ordered set of indices, and let $\{X_{i}\mid i\in I\}\subseteq \mathcal F$ be a $\subseteq$-chain of members of $\mathcal F$. In other words, each $X_i\subset P$ is totally ordered by $\preceq$ and for any $i,j\in I$ we have $X_i\subseteq X_j$ iff $i\leq j$. Then we need to show $\bigcup_{i\in I}X_i$ is totally ordered by $\preceq$.

It's easy to see that $\preceq$ is a partial order on $\bigcup_{i\in I} X_i$, since $\bigcup_{i\in I} X_i\subseteq P$ and subsets of partial orders are partially ordered. Thus we only need to check that $\preceq$ is total.

Let $x,x'\in\bigcup_{i\in I}X_i$, then there are $i,j\in I$ such that $x\in X_i$ and $x'\in X_j$. Without loss of generality $i\leq j$, which implies $X_i\subseteq X_j$ and thus $x,x'\in X_j$. Now, since $X_j$ is totally ordered by $\preceq$, we have that $x\preceq x'$ or $x'\preceq x$. Therefore for any $x,x'\in\bigcup_{i\in I}X_i$ we have $x\preceq x'$ or $x'\preceq x$, which means $\preceq$ is indeed total on $\bigcup_{i\in I}X_i$.

  • $\begingroup$ Thank you for the detailed answer, took me a while but now I think I understand it! $\endgroup$
    – MoneyBall
    Jul 1 '21 at 4:45

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.