# properties of well-ordered sets

The purpose of this entry is to collect properties of well-ordered sets. We denote all orderings uniformly by $\leq$. If you are interested in history, have a look at [C].

The following properties are easy to see:

• If $A$ is a totally ordered set such that for every subset $B\subseteq A$ the set of all elements of $A$ strictly greater than the elements of $B$,

 $B_{>}:=\{a\in A\setminus B\mid b\leq a\text{ for all }b\in B\},$

is either empty or has a least element, then $A$ is well-ordered.

• Every subset of a well-ordered set is well-ordered.

• If $A$ is well-ordered and $B$ is a poset such that there is a bijective order morphism $\varphi\colon A\to B$, then $B$ is well-ordered.

Now we define an important ingredient for understanding the structure of well-ordered sets.

###### Definition 1 (section).

Let $A$ be well-ordered. Then for every $a\in A$ we define the section of $a$:

 $\widehat{a}:=\{b\in A\mid b\leq a\}.$

A section is also known as an initial segment. We denote the set of all sections of $A$ by $\widehat{A}$. This set is ordered by inclusion.

###### Theorem 1.

Let $A$ be a well-ordered set. Then the mapping $\widehat{\cdot}\colon A\to\widehat{A}$ defined by $a\mapsto\widehat{a}$ is a bijective order morphism. In particular, $\widehat{A}$ is well-ordered.

###### Proof.

Let $a,b\in A$ with $a\leq b$. Then $\widehat{a}\subseteq\widehat{b}$, so $\widehat{\cdot}$ is an order morphism. Now assume that $\widehat{a}=\widehat{b}$. If $a$ didn’t equal $b$, we would have $b\notin\widehat{a}$, leading to a contradiction. Therefore $\widehat{\cdot}$ is injective. Now let $C\in\widehat{A}$, then there exists a $c\in A$ such that $\widehat{c}=C$, so $\widehat{\cdot}$ is surjective. ∎

###### Theorem 2.

Let $A$ and $B$ be well-ordered sets and $\varphi\colon A\to B$ a bijective order morphism. Then there exists a bijective order morphism $\widehat{\varphi}\colon\widehat{A}\to\widehat{B}$ such that for all $a\in A$

 $\widehat{\varphi}(\widehat{a})=\widehat{\varphi(a)}.$
###### Proof.

Setting $\widehat{\varphi}(\widehat{a}):=\widehat{\varphi(a)}$ is well-defined by Theorem 1. The rest of the theorem follows since $\widehat{\cdot}$ and $\varphi$ are bijective order morphisms. ∎

###### Theorem 3.

Let $A$ be a well-ordered set and $a\in A$ such that there is an injective order morphism $\varphi\colon A\to\widehat{a}$. Then $A=\widehat{a}$.

###### Proof.

The image of a section of $A$ under $\varphi$ has a maximal element which in turn defines a smaller section of $A$. We may therefore define the following two monotonically decreasing sequences of sets:

 $\displaystyle B_{0}$ $\displaystyle:=\varphi(\widehat{a}),$ $\displaystyle A_{0}$ $\displaystyle:=\text{section defined by maximal element of }B_{0},$ $\displaystyle B_{n}$ $\displaystyle:=\varphi(A_{n-1}),$ $\displaystyle A_{n}$ $\displaystyle:=\text{section defined by maximal element of }B_{n}.$

Now $\widehat{A}$ is well-ordered, so the set defined by the elements of the sequence $(A_{n})$ has a minimal element, that is $A_{N}=A_{N+1}$ and hence $B_{N}=B_{N+1}$ for some sufficiently large $N$. Applying $\varphi^{-1}$ $N+1$ times to the latter equation yields $\widehat{a}=A_{0}$, that is $a$ is the maximal element of $B$, and thus of $A$. ∎

###### Theorem 4.

Let $A$ and $B$ be well-ordered sets. Then there exists at most one bijective order morphism $\varphi\colon A\to B$.

###### Proof.

Let $\varphi,\psi\colon A\to B$ be two bijective order morphisms. Let $a\in A$ and set $b:=\varphi(a)$ and $c:=\psi(a)$. Then the restrictions $\left.\varphi\right|_{\widehat{a}}\colon\widehat{a}\to\widehat{b}$ and $\left.\psi\right|_{\widehat{a}}\colon\widehat{a}\to\widehat{c}$ are bijective order morphisms, so the restriction of $\psi\varphi^{-1}$ to $\widehat{b}$ is a bijective order morphism to $\widehat{c}$. Now either $\widehat{b}\subseteq\widehat{c}$ or $\widehat{c}\subseteq\widehat{b}$, so by Theorem 3 $\widehat{b}=\widehat{c}$, hence $b=c$ and thus $\varphi=\psi$. ∎

###### Theorem 5.

Let $A$ and $B$ be well-ordered sets such that for every section $\widehat{a}\in\widehat{A}$ there is a bijective order morphism to a section $\widehat{b}\in\widehat{B}$ and vice-versa, then there is a bijective order morphism $\varphi\colon A\to B$.

###### Proof.

Let $a\in A$ and let $\widehat{b}\in\widehat{B}$ be a section such that there is a bijective order morphism $\psi_{a}\colon\widehat{a}\to\widehat{b}$. By Theorem 3, $\widehat{b}$ is unique, and so is $\psi_{a}$ by Theorem 4. Defining $\varphi\colon A\to B$ by setting $\varphi(a)=b$ gives therefore a well-defined (by Theorem 1) and injective order morphism. But $\varphi$ is also surjective, since any $b\in B$ maps uniquely to $A$ via $\widehat{b}\to\widehat{a}$, and back again by $\varphi$. ∎

###### Theorem 6.

Let $A$ and $B$ be well-ordered sets. Then there is an injective order morphism $\iota\colon A\to B$ or $\iota\colon B\to A$. If $\iota$ cannot be chosen bijective, then it can at least be chosen such that its image is a section.

###### Proof.

Let $\widehat{A}_{0}$ be the set of sections of $A$ from which there is an injective order morphism to $B$. If $\widehat{A}_{0}$ is the empty set, then $B$ must be empty, since otherwise we could map the least element of $A$ to $B$. If $\widehat{A}_{0}$ is not empty, we may consider the set $A_{0}:=\cap\widehat{A}_{0}$. If $A_{0}=A$, nothing remains to be shown. Otherwise the set $A\setminus A_{0}$ is nonempty an hence has a least element $a_{0}\in A$. By construction, there is no injective order morphism from $\widehat{a}_{0}$ to $B$, but there is an injective order morphism from $\varphi_{a}\colon\widehat{a}\to B$ for every element $a\in A$ which is strictly smaller than $a_{0}$. Now assume there is an element $b\in B$ such that there is no injective order morphism from $\widehat{b}\to A$. Then we can similarly construct a least element $b_{0}\in B$ for which there is no injective order morphism $\widehat{b}_{0}\to A$. Surely, $b_{0}$ is greater than all the elements from the images of the functions $\varphi_{a}$, but then there is a bijective order morphism from $\widehat{a}_{0}$ to $\widehat{b}_{0}$ by Theorem 5 which is a contradiction. Therefore, all sections of $B$ and $B$ itself map injectively and order-preserving to $A$. ∎

###### Theorem 7.

Let $A$ be a well-ordered set and $B\subseteq A$ a nonempty subset. Then there is a bijective order morphism from $B$ to one of the sets in $\widehat{A}\cup\{A\}$.

###### Proof.

The set $B$ is well-ordered with respect to the order induced by $A$. Assume a bijective order morphism as stated by the theorem does not exist. Then, by virtue of Theorem 6, there is an injective but not surjective order morphism $\iota\colon A\to B$ whose image is a section $\widehat{b}\in\widehat{B}$. The element $b$ defines a section in $\widehat{A}$ which is identical to $A$ by Theorem 3. Thus $\iota$ is surjective which is a contradiction. ∎

## References

• C G. Cantor, Beiträge zur Begründung der transfiniten Mengenlehre (Zweiter Artikel), Math. Ann. 49, 207–246 (1897).
Title properties of well-ordered sets PropertiesOfWellorderedSets 2013-03-22 15:23:42 2013-03-22 15:23:42 GrafZahl (9234) GrafZahl (9234) 10 GrafZahl (9234) Theorem msc 06A05 initial segment section