Hausdorff Maximal Principle implies Well-Ordering Theorem

From ProofWiki
Jump to: navigation, search

Theorem

Let the Hausdorff Maximal Principle hold.


Then the Well-Ordering Theorem holds.


Proof

Let $X$ be a non-empty set.

Let $X$ contain at least two elements; otherwise, $X$ can be trivially well-ordered.

We use the Hausdorff Maximal Principle to construct a well-ordering on $X$.

We note that there exists at least the following strict well-orderings on subsets of $X$:

For any singleton $\{x\}$, $x$ is vacuously well-ordered with respect to every other element in the subset, of which there are none.

Any doubleton $\left\{ { y,z } \right\}$ can be strictly well-ordered by defining $x < y$ and $y \not < x$.


Let $\mathcal A$ be the set of all ordered pairs $\left({A,<}\right)$ such that $A$ is a subset of $X$ and $<$ is a strict well-ordering of $A$.

Define $\prec$ as:

$\left({A,<}\right) \prec \left({A',<'}\right)$

if and only if

$\left({A,<}\right)$ equals an initial segment of $\left({A',<'}\right)$.

Let $\mathcal B$ be a set of ordered pairs in $\mathcal A$ such that $\mathcal B$ is ordered by $\prec$.

Let $B'$ be the union of the sets $B$ for all $\left({B,<}\right) \in \mathcal B$.

Let $<'$ be the union of the relations $<$ for all $\left({B,<}\right)$.

By the lemma, $\left({B',<'}\right)$ is strictly well-ordered set.

By the Hausdorff Maximal Principle, there exists a maximal chain defined by $<'$ imposed on a maximal subset of $X$.

We claim that this maximal chain is imposed on the entirety of $X$.

Aiming for a contradiction, suppose that $\left({B',<'}\right)$ is a maximal chain but $B' \ne X$.

Then consider $B' \cup \{ x \}$., with $x \in X \setminus B'$, with the extension of $<'$ such that:

$\forall a \in B': a <' x$.

Then $B' = S_x$, the initial segment in $B' \cup \{x\}$ determined by $x$.

But by the definition of $\prec$, we then have:

$ \left({B'\cup \{x\},\text{extension of }<'}\right) \prec \left({B',<'}\right)$

But then by the definition of $B'$, we would have $B' \cup \{x\} \subseteq B'$, contrary to the assumption that $x \in X \setminus B'$.

From this contradiction infer that $B' = X$.

That is, all of $X$ can be well-ordered.

$\blacksquare$

Also see


Sources