Existence of Minimal Uncountable Well-Ordered Set/Proof Without Using Choice

From ProofWiki
Jump to: navigation, search


There exists a minimal uncountable well-ordered set.

That is, there exists an uncountable well-ordered set $\Omega$ with the property that every initial segment in $\Omega$ is countable.


By the axiom of powers, there exists the power set $\mathcal P \left({\N}\right)$, where $\N$ is the set of natural numbers.

By Power Set of Natural Numbers is not Countable, this set is uncountable.

Consider the set of ordered pairs:

$\mathcal A = \left\{ { \left({A,\prec}\right) : A \in\mathcal P(\N) }\right\}$


the first coordinate is a (possibly empty) subset of $\N$
the second coordinate is a strict well-ordering on $A$.

There is at least one pair of this form for each $A \subseteq \N$, taking $\prec$ to be the usual (strict) ordering of the natural numbers.

The usual ordering is a well-ordering, from the Well-Ordering Principle.

Define the relation:

$(A, \prec) \sim (A',\prec')$

if and only if:

$(A, \prec)$ is order isomorphic to $(A',\prec')$.

By Order Isomorphism is Equivalence Relation, $\sim$ is an equivalence relation.

Let $E$ be the set of all equivalence classes $\left[\!\left[{\left({A,\prec}\right)}\right]\!\right]$ defined by $\sim$ imposed on $\mathcal P(\N)$

Define the relation:

$\left[\!\left[{\left({A,\prec_A}\right)}\right]\!\right] \ll \left[\!\left[{\left({B,\prec_B}\right)}\right]\!\right]$

if and only if

$(A, \prec_A)$ is order isomorphic to an initial segment $S_b$ of $(B,\prec_B)$.

We claim that $\left({E,\ll}\right) = \Omega$.

To see that $\ll$ is well-defined, we use a commutative diagram:

$ \xymatrix{ \left({A,\prec_A}\right) \ar[d]^f \ar[r]^{g_1} &S_b(B)\[email protected]{-->}[d]^{g_2 \circ f}\\ \left({C,\prec_C}\right) \ar[r]^{g_2} &S_d(B)} $

where $f$ is a mapping defining $\sim$, and $g_1,g_2$ are mappings defining $\ll$.

From No Isomorphism from Woset to Initial Segment, no equivalence class $\left[\!\left[{\left({A,\prec_A}\right)}\right]\!\right]$ can bear $\ll$ to itself.

From Wosets are Isomorphic to Each Other or Initial Segments, $\ll$ is connected.

From the definition of an order isomorphism, $\ll$ is an ordering.

Thus $\ll$ is a strict total ordering.

The empty set $\varnothing$ contains no elements that could define an initial segment in it.

Consider the empty mapping: $\nu: \varnothing \to \varnothing$.

Such a mapping $\nu$ is bijective, by Empty Mapping to Empty Set is Bijective.

But $\varnothing$ is itself an initial segment of any non-empty set, from Initial Segment Determined by Smallest Element is Empty.

Thus there is an order-isomorphism from $\varnothing$ to an initial segment in any non empty $A$, as $\nu$ is vacuously order-preserving.

Thus $\left[\!\left[{\left({\varnothing,\varnothing}\right)}\right]\!\right]$ is the smallest element of $E$.

Let $\alpha = \left[\!\left[{\left({A,\prec}\right)}\right]\!\right]$ be an element of $E$.

We claim that $\left({A,\prec}\right)$ is order isomorphic to $S_\alpha(E)$, the initial segment of $E$ determined by $\alpha$.

To see this, define the mapping:

$f_\alpha: A \to E$:
$f_\alpha(x) = \left[\!\left[{\left({S_x(A),{\prec \restriction_{S_x(A)}}}\right)}\right]\!\right]$

where ${\restriction}$ denotes restriction.

This is a strict ordering for each $\prec \restriction_{S_x(A)}$, from Restriction of Strict Well-Ordering is Strict Well-Ordering.

Suppose $x \prec y$ in $A$.

Then $S_x$ is an initial segment of $S_y$.

From No Order Isomorphism Between Distinct Initial Segments of Woset, $S_x \ne S_y$.

Thus $f_\alpha(x) \ll f_\alpha(y)$.

Conclude that $f_\alpha$ is strictly increasing.

From Strictly Monotone Mapping with Totally Ordered Domain is Injective, $f_\alpha$ is therefore an injection.

For all $x \in A$, $f_\alpha(x)$ is an element of $E$.

Thus it is an element of $S_\alpha(E)$, by the construction of $f_\alpha$.

By the definition of an image set:

$f[A] = S_\alpha(E)$

From Injection to Image is Bijection, there is a bijection from $A$ to $f[A]$.

That is, from $A$ to $S_\alpha(E)$.

As $f_\alpha$ was shown to be (strictly) increasing, there is an order isomorphism between $\left({A,\prec}\right)$ and $S_\alpha(E)$.

Recall that $E$ has a smallest element $\left[\!\left[{\left({\varnothing,\varnothing}\right)}\right]\!\right]$.

Let $F$ be any non-empty proper subset of $E$

As it is non-empty, $F$ has some element in it. Call the element $a$.

If such an $a$ precedes all elements in $F$, then $a$ is the smallest element of $F$.

Suppose $a$ is not the smallest element in $F$.

Then $F$ has at least two elements.

Then $a \in S_a(E) \cap F$.

From Inverse of Order Isomorphism is Order Isomorphism, $f^{-1}$ is also an isomorphism.

That means that $a$ is isomorphic to some $(A,\prec) \in \mathcal A$

But $A$ has a minimal element, by the definition of $\mathcal A$.

From Order Isomorphism on Well-Ordered Set preserves Well-Ordering, $S_a(E) \cap F$ is a well-ordered set.

Thus it has a smallest element.

The smallest element in $S_a(E)$ is the smallest element of $E$, by the definition of initial segment.

We assumed that $a$ is not the smallest element in $F$, so the smallest element of $S_a(E) \cap F$ is the smallest element of $F$.

As $F$ was arbitrary, we can conclude that every non-empty subset of $E$ has a smallest element.

So $E$ is well ordered.

It remains to be proven that $E$ is uncountable and every initial segment of $E$ is countable.

Aiming for a contradiction, suppose that $E$ is countable.

Then there is a bijection:

$h: E \leftrightarrow \N$.

From Order Isomorphism on Well-Ordered Set preserves Well-Ordering, we can define the strict ordering:

$f(x) \prec f(y)$ in $\N$

if and only if

$x \ll y$ in $E$.

From Composite of Order Isomorphisms is Order Isomorphism, we can consider the isomorphism $f_\alpha \circ h$, where $f_\alpha$ is the above isomorphism to some $S_\alpha(E)$ in $E$, which is isomorphic to some $(A,\prec) \in \mathcal A$.

Then $h^{-1}[\N]$ is order isomorphic to all of $\mathcal A$.

Then there is a bijection between $\mathcal P(\N)$ and $\N$, contradicting Power Set of Natural Numbers is not Countable.

From this contradiction, $E$ cannot be countable.

Consider any initial segment $S_\alpha(E)$

We have shown that $S_\alpha(E)$ is order isomorphic to some $(A,\prec) \in \mathcal A$.

But $A$ is a subset of the natural numbers.

From Subset of Countably Infinite Set is Countable, $A$ is countable.

We have shown that $\left({E,\ll}\right)$ is an uncountable well-ordered set, every initial segment of which is countable.