Set Theory HT25, Well-ordered sets

In a strict order, no element is related to itself. In a non-strict order, every element is related to itself.

A totally ordered set which is well-founded, i.e. every nonempty subset $Y \subseteq X$ has a least element.

• An initial segment $S \subseteq X$ is a subset which is downwards closed in $X$, i.e. for all $y \in S$ and for all $x \in X$, $x < y$ implies $x \in S$.
• $X _ {<a} := \lbrace x \in X \mid x < a\rbrace$.
• $S = X _ {<\min(X \setminus S)}$

A strictly monotone function $\phi : X \to Y$, so that

\[x < x' \implies \phi(x) < _ \ast \phi(x')\]

for all $x, x’ \in X$

$(X, <) \cong (Y, < _ \ast)$ if there exists a surjective embedding.

\[\phi(x) \ge x\]

for all $x \in X$.

Suppose it were not. Then

\[a := \min\lbrace x \in X : \phi(x) < x\rbrace\]

exists. But then $\phi(a) < a$, so $\phi(\phi(a)) < \phi(a)$ since $\phi$ is an embedding, contradicting the minimality of $a$.

Suppose $\sigma : X \to X _ {<x}$ is an isomorphism. Then $\sigma(x) < x$, but this contradicts the result that says

If:

• $(X, <)$ is a well-order
• $\phi : (X, <) \to (X, <)$ is an embedding

Then:

• $\phi(x) \ge x$

Hence no such isomorphism exists.

For (1), note that if $\sigma : X \to X$ is an isomorphism, then so is $\sigma^{-1}$. Hence by the result that says

If:

• $(X, <)$ is a well-order
• $\phi : (X, <) \to (X, <)$ is an embedding

Then:

• $\phi(x) \ge x$

it follows that for all $x \in X$, we have $\sigma(x) \le x$ and $\sigma^{-1}(x) \le x$, and hence $x \le \sigma(x) \le x$, so $\sigma(x) = x$.

For (2), note that if $\sigma, \tau : X \to Y$ are isomorphism, then $\tau^{-1} \circ \sigma$ must be the identity by (1). Hence $\sigma = \tau$.

Either $(X, <)$ is isomorphic to an initial segment of $(Y, < _ \ast)$ or $(Y, < _ \ast)$ is isomorphic to an initial segment of $(X, <)$.

Overall idea: Consider the set of pairs $\langle x, y\rangle$ such that $X _ {<x}$ is isomorphic to some initial segment of $Y$, say $Y _ {< _ \ast y}$. This actually forms a function, say $\sigma$ (Why? If there multiple pairs $\langle x, y\rangle$ and $\langle x, y’ \rangle$, you could chain isomorphisms to show that there was a well-ordered set isomorphic to one its proper initial segments). You can then show that $\mathrm{dom}(\sigma)$ and $\mathrm{ran}(\sigma)$ are actually initial segments of $X$ and $Y$ respectively, and that either $X \cong \text{ran}(\sigma)$ or $Y \cong \text{dom}(\sigma)$.

---

Define

\[\sigma := \lbrace \langle x, y \rangle \in X \times Y : (X _ {<x}, <) \cong (Y _ {< _ \ast y}, < _ \ast)\rbrace\]

Then $\sigma$ is a function, since if $\langle x, y \rangle, \langle x, y’\rangle \in \sigma$, then $(Y _ {<y}, <) \cong (Y _ {<y’}, <)$, so $y = y’$ by the result that says well-orders are not isomorphic to any of their proper initial segments. Symmetrically, $\sigma$ is injective.

Let $X’ := \text{dom}(\sigma)$ and $Y’ := \text{ran}(\sigma)$. We aim to show that $X’$ and $Y’$ are both downwards closed, so that they are initial segments of $X$ and $Y$.

Pick some $\langle x, y \rangle \in \sigma$ and let $\tau : X _ {< x} \to Y _ {< _ \ast y}$ be the corresponding isomorphism.

If $x’ < x$, then $\tau \vert _ {X _ {<x’ } } : X _ {<x’} \to Y _ {< _ \ast \tau(x’)}$ is an isomorphism, so $\langle x’, \tau(x’)\rangle \in \sigma$. If $y’ < y$, then there is some $x’$ such that $\sigma(x’) = y’$. Hence $\langle x’, y’\rangle \in \sigma$.

Note also that $\sigma : X’ \to Y’$ is an isomorphism, since $\sigma(x’) = \tau(x’) < _ \ast y = \sigma(x)$. Therefore $X’ \cong Y’$.

Suppose that $X’$ and $Y’$ were both proper initial segments, i.e. $X’ = X _ {<x}$ and $Y’ = Y _ {< _ \ast y}$. But then $\langle x, y \rangle \in \sigma$, contradicting $X’ = \text{dom}(\sigma)$ (since otherwise you could add $\langle x, y\rangle$ to the domain). Therefore, either $X’ = X$ or $Y’ = Y$, as required.

Suppose:

• $X \subseteq \mathbb R$
• $(X, < _ \mathbb R)$ is well-ordered

Then:

• $X$ is countable

---

Show that all elements $x \in X$ are either the greatest element in $X$ or have immediate successors, then use this to form an ordering.

Suppose $X$ is infinite and let $R$ be a double well-order on $X$. Then $X$ is order-isomorphic to some $\alpha$ where $\alpha \ge \omega$. Consider $\lbrace f(n) \mid n \in \omega \rbrace \subseteq X$. But then this set has no upper bound, a contradiction.

@example~ @exam~