Well-Ordering Theorem implies Hausdorff Maximal Principle

From ProofWiki
Jump to navigation Jump to 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 $\map P {a, Y}$ be the predicate:

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

Here, $a$ and $Y$ are bound variables.

That is, $\map P {a, Y}$ holds if, for every $y \in Y$, $a \le y$ or $y \le a$.

Define the mapping:

$\map \rho {f: S_x \to \powerset X} = \begin {cases} f \sqbrk {S_x} \cup \set x & : \map P {x, S_x} \\ f \sqbrk {S_x} & : \text {otherwise} \end{cases}$

where $S_x$ is the initial segment in $X$ defined by $x$, and $\map 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 \powerset X$:
$\map h \alpha = \map \rho {h {\restriction_{S_\alpha} } } = \begin {cases} h \sqbrk {S_\alpha} \cup \set \alpha & : \map P {\alpha, S_\alpha} \\ h \sqbrk {S_\alpha} & : \text {otherwise} \end{cases}$

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

Similarly, $h \sqbrk {S_\alpha}$ is totally ordered, for the same reason.

Then the union:

$Z = \ds \bigcup_{\alpha \mathop \in X} \map h \alpha$

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

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

In particular, it is a chain of $\struct {X, \le}$.

We claim this chain is maximal.

To see this, consider $x_0 \notin \ds \bigcup_{\alpha \mathop \in X} \map h \alpha$.

Then $x_0$ is not $\le$-comparable with the elements of $Z$, because $\neg \map P {x, Z}$.

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

Therefore the ordered sum on $Z$ is a maximal chain in $\struct {X, \le}$.

$\blacksquare$


Also see


Sources