Notes - Set Theory HT25, Well-ordered sets

[[Course - Set Theory HT25]]^U
- [[Notes - Set Theory HT25, Ordinals]]^U

Flashcards

@Define a well-ordered set $X$.

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

Suppose $(X, <)$ is a well-ordered set. @Define:

An initial segment $S$ of $X$
The notation $X _ {<a}$
For any initial proper segment $S$ of $X$, write it using the notation $X _ {<a}$.

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} := \{x \in X \mid x < a\}$.
$S = X _ {<\min(X \setminus S)}$

@Define an embedding of a totally ordered set $(X, <)$ in a totally ordered set $(Y, <’)$, and define what it means for $(X, <) \cong (Y, <’)$.

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

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

for all $x, x’ \in X$

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

Suppose $(X, <)$ is a well-order. @State a result that restricts the types of possible embeddings $\phi : (X, <) \to (X, <)$.

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

for all $x \in X$.

@Prove that if:

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

then:

$\phi(x) \ge x$

Suppose it were not. Then

\[a := \min\\{x \in X : \phi(x) < x\\}\]

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

@Prove that a well-order is not isomorphic to any of its proper initial segments.

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.

@Prove that if $(X, <)$ is a well-order then:

The only isomorphism $X \to X$ is the identity
If $(X, <) \cong (Y, <’)$, then there is a unique isomorphism $X \to Y$

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$.

Suppose $(X, <)$ and $(Y, <’)$ are well-orders. @State a result about comparing $X$ and $Y$.

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

@Prove that if:

$(X, <)$ is a well-order
$(Y, <’)$ is a well-order

then either:

$(X, <)$ is isomorphic to an initial segment of $(Y, <’)$, or
$(Y, <’)$ is isomorphic to an initial segment of $(X, <)$.

Define

\[\sigma := \\{\langle x, y \rangle \in X \times Y : (X_{<x}, x) \cong (Y_{<'y}, Y')\\}\]

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 $\langle x, y \rangle \in \sigma$, so say $\tau : X _ {< x} \to Y _ {<’ y}$ is the corresponding isomorphism.

If $x’ < x$, then $\tau \vert _ {X<x’} : X _ {<x’} \to Y _ {<’ \tau(x’)}$ is an isomorphism, so $\langle x’, \tau(x’)\rangle \in \sigma$.

Hence $X’ := \text{dom}(\sigma) \subseteq X$ is an initial segment of $X$, and symmetrically $Y’ := \text{ran}(\sigma) \subseteq Y$ is an initial segment of $Y$, and $\sigma : X’ \to Y’$ is an isomorphism, since $\sigma(x’) = \tau(x’) <’ y = \sigma(x)$.

So $X’ \cong Y’$. If $X’$ and $Y’$ are proper initial segments, say $X’ = X _ {<x}$ and $Y’ = Y _ {<’ y}$, then $\langle x, y \rangle \in \sigma$, contradicting $X’ = \text{dom}(\sigma)$. So either $X’ = X$ or $Y’ = Y$, as required.

Flashcards

Related posts