0.6 More about Well Ordered Sets

We discuss more about Well Ordered sets.

If $X$ is well ordered and $A \subset X$, then $\cup_{x \in A} I_{x}$ is either initial segment or $X$ itself.

Let $ J = \cup_{x \in A} I_{x}$. If $J = X$, nothing more to prove. If $J \neq X$, let $b = \inf(X \setminus J)$. If $y < b$ for $y \in X$, by construction, $y \in J$. This means $I_{b} \subset J$. Now pick $y \in J$. Then $y \in I_{x}$ for some $x \in A$. If $y \not\in I_{b}$, then $y \geq b$ gives $b \leq y < x$, in turn $b \in I_{x} \implies b \in J$; contradiction. So $ y \in I_{b}$. Thus, $J = I_{b}$.

This proposition states that any union of initial segments are also an initial segment (including whole set) when the whole set is well ordered.

If $X$ and $Y$ are nonempty and well ordered, then either

1. $X$ is order isomorphic to $Y$
2. $X$ is order isomorphic to an initial segment of $Y$
3. $Y$ is order isomorphic to an initial segment of $X$

Consider the collection $\mathcal{F}$ of order isomorphisms whose domains are initial segments of $X$ or $X$ itself and whose ranges are initial segments of $Y$ or $Y$ itself. $\mathcal{F}$ is nonempty since $f: \left\{ \inf X \right\} \rightarrow \left\{ \inf Y \right\}$ is a memeber of $\mathcal{F}$. Also $\mathcal{F}$ is partially ordered by set inclusion if functions are viewed as subsets of $X \times Y$. By similar reasoning used in Section 0.4, Proposition 1-2, if $S$ is nonempty linearly ordered subset of $\mathcal{F}$, then $$ f^{\ast} = \bigcup_{f \in S} f $$ is well defined function and upper bound of $S$. By Zorn's Lemma, $\mathcal{F}$ has a maximal element; say $g$ with domain $A$ and range $B$. If $A = I_{x}$ and $B = I_{y}$ for some $x \in X$ and $y \in Y$, then we can extend $g$ by $$ \bar{g}: A \cup \left\{ x \right\} \rightarrow Y,\ \bar{g}(a) = \begin{cases} g(a) & (a \in A) \\ y & (a = x) \end{cases} $$ because $I_{x} \cup \left\{ x \right\}$, $ I_{y} \cup \left\{ y \right\}$ are again initial segments (including whole set $X$ or $Y$). This contradicts to maximality of $g$. Hence either $A = X$ or $B = Y$, and the result follows.

Well Ordering principle gives us the way to construct weird uncountable sets.

There is an uncountable well ordered set $\Omega$ such that $I_{x}$ is countable for every $x \in \Omega$. If $\Omega'$ is another set with the same properties, then $\Omega$ and $\Omega'$ are order isomorphic.

First by well ordering principle, uncountable well ordered set $\Omega_{0}$ exists. Then define $$ A = \left\{ t \in \Omega_{0}: I_{t} \text{ is uncountable } \right\} $$ If $\Omega_{0}$ satisfies the desired property, then nothing more to prove. If not, $A$ has minimal element $a$ by well ordering principle. Then the set $\Omega = I_{a}$ would be the desired set, because for any $x \in \Omega$, $x \not\in A$, so that $I_{x}$ is countable. Any other $\Omega'$ satisfying this property is order isomorphic to $\Omega$ itself, because any initial segments of $\Omega$ and $\Omega'$ are countable. (See Proposition 2).

Every nonempty countable subset of $\Omega$ has an upper bound.

Let $A \subset \Omega$ be countable and nonempty. $\cup_{x \in A} I_{x}$ is countable union of countable sets, so it is countable. By Proposition 1, it should be equal to $I_{y}$ for some $y \in \Omega$. Then for any $a \in A$, $$ I_{a} \subset I_{y} \implies a \leq y $$ which is equivalent to saying $y$ is an upper bound of $A$.

The set $\Omega$ is called a set of countable ordinals. We usually define $\Omega^{\ast} = \Omega \cup \left\{ \omega_{1} \right\}$ and extend the well ordering by declaring $$ x < \omega_{1},\ (\forall x \in \Omega) $$ $\omega_{1}$ is called the first uncountable ordinal. We won't get further deep into theory of ordinals.