Hausdorff Maximal Principle implies Well-Ordering Theorem

From ProofWiki
Jump to navigation Jump to 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 $\set x$, $x$ is vacuously well-ordered with respect to every other element in the subset, of which there are none.



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



Let $\AA$ be the set of all ordered pairs $\struct {A, <}$ such that $A$ is a subset of $X$ and $<$ is a strict well-ordering of $A$.

Define $\prec$ as:

$\struct {A, <} \prec \struct {A', <'}$

if and only if

$\struct {A, <}$ equals an initial segment of $\struct {A', <'}$.

Let $\BB$ be a set of ordered pairs in $\AA$ such that $\BB$ is ordered by $\prec$.

Let $B'$ be the union of the sets $B$ for all $\struct {B, <} \in \BB$.

Let $<'$ be the union of the relations $<$ for all $\struct {B, <}$.

By Equality to Initial Segment Imposes Well-Ordering, $\struct {B', <'}$ 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 $\struct {B', <'}$ is a maximal chain but $B' \ne X$.

Then consider $B' \cup \set 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 \set x$ determined by $x$.

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

$\struct {B' \cup \set x, \text {extension of } <'} \prec \struct {B', <'}$

But then by the definition of $B'$, we would have $B' \cup \set 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