# totally ordered sets and union of totally ordered sets

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?

• No, a chain of subsets of P is not a totally ordered subset of P. Jun 29 '21 at 2:43
• isn't chain, by definition, totally ordered? or is that a subchain? Jun 29 '21 at 3:11
• They are synonyms. Jun 29 '21 at 8:55
• 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). 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$$.

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