Well-Ordering Theorem implies Hausdorff Maximal Principle

From ProofWiki
Jump to: navigation, search

Theorem

Let the Well-Ordering Theorem hold.


Then the Hausdorff Maximal Principle holds.


Proof

Let $X$ be a non-empty set.

Let $X$ contain at least two elements; otherwise, any non-empty ordering on $X$ is trivially a maximal chain.

By the Well-Ordering Theorem, $X$ can be well-ordered. Fix such a well-ordering.


Let $\le$ be any ordering on $X$.

Let $P\left({a,Y}\right)$ be the predicate:

$a$ is $\le$-comparable to every $y \in Y$.

(Here $a$ and $Y$ are bound variables.)

That is, $P\left({a,Y}\right)$ holds if, for every $y \in Y$, $a \le y$ or $y \le a$.

Define the mapping:

$\rho\left({f: S_x \to \mathcal P(X) }\right) = \begin{cases} f[S_x] \cup \{ x \} & P(x,S_x) \\ f[S_x] & \text{ otherwise } \end{cases}$

where $S_x$ is the initial segment in $X$ defined by $x$, and $f[\,\cdot\,]$ denotes an image set.

Using the Principle of Recursive Definition for Well-Ordered Sets, we can use $\rho$ to uniquely define:

$h: X \to \mathcal P(X)$:
$h(\alpha) = \rho\left({ h {\restriction_{S_\alpha}} }\right) = \begin{cases} h[S_\alpha] \cup \{\alpha\} & P(\alpha,S_\alpha) \\ h[S_\alpha] & \text{ otherwise } \end{cases}$

Then $h(\alpha)$ is a $\le$-totally ordered set, by virtue of the construction of $h$ in terms of the predicate $P$.

Similarly, $h[S_\alpha]$ is totally ordered, for the same reason.

Then the union:

$Z = \displaystyle \bigcup_{\alpha \mathop \in X} h(\alpha)$

admits an ordered sum in terms of $\le$ imposed on each $h(\alpha)$.

By Ordered Sum of Tosets is Totally Ordered Set, this is a totally ordered set.

In particular, it is a chain of $\left({X,\le}\right)$.

We claim this chain is maximal.

To see this, consider $\displaystyle x_0 \notin \displaystyle \bigcup_{\alpha \mathop \in X} h(\alpha)$.

Then $x_0$ is not $\le$-comparable to the elements of $Z$, because $\neg P\left({x,Z}\right)$.

That is, there are no proper supersets of $Z$ that are totally ordered.

Therefore the ordered sum on $Z$ is a maximal chain in $\left({X,\le}\right)$.

$\blacksquare$


Also see


Sources