properties of well-ordered sets

The purpose of this entry is to collect properties of well-orderedsets. We denote all orderings uniformly by $\le$. If you areinterested 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 thanthe elements of $B$,

  $$B_{>}:=\{a\in A\setminus B\mid b\le 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 abijective order morphism $\phi :A\to B$, then $B$ iswell-ordered.

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

Definition 1 (section).

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

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

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

Theorem 1.

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

Proof.

Let $a,b\in A$ with $a\le 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 acontradiction. 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 $\phi \mathrm{:}A\mathrm{\to }B$ abijective order morphism. Then there exists a bijective order morphism$\widehat{\phi }\mathrm{:}\widehat{A}\mathrm{\to }\widehat{B}$ such that for all $a\mathrm{\in }A$

$$\widehat{\phi }(\widehat{a})=\widehat{\phi (a)}.$$

Proof.

Setting $\widehat{\phi }(\widehat{a}):=\widehat{\phi (a)}$ is well-defined byTheorem 1. The rest of the theorem followssince $\widehat{\cdot }$ and $\phi$ are bijective order morphisms.∎

Theorem 3.

Let $A$ be a well-ordered set and $a\mathrm{\in }A$ such that there is aninjective order morphism $\phi \mathrm{:}A\mathrm{\to }\widehat{a}$. Then $A\mathrm{=}\widehat{a}$.

Proof.

The image of a section of $A$ under $\phi$ has a maximal elementwhich in turn defines a smaller section of $A$. We may thereforedefine the following two monotonically decreasing sequences of sets:

$B_0$$:=\phi (\widehat{a}),$$A_0$$:=\text{section defined by maximal element of }{B}_0,$

$B_n$$:=\phi (A_{n-1}),$$A_n$$:=\text{section defined by maximal elementof }{B}_n.$

Now $\widehat{A}$ is well-ordered, so the set defined by the elements of thesequence $(A_n)$ has a minimal element, that is $A_N=A_{N+1}$ andhence $B_N=B_{N+1}$ for some sufficiently large $N$. Applying${\phi }^{-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 onebijective order morphism $\phi \mathrm{:}A\mathrm{\to }B$.

Proof.

Let $\phi ,\psi :A\to B$ be two bijective order morphisms. Let$a\in A$ and set $b:=\phi (a)$ and $c:=\psi (a)$. Then therestrictions ${\phi |}_{\widehat{a}}:\widehat{a}\to \widehat{b}$ and${\psi |}_{\widehat{a}}:\widehat{a}\to \widehat{c}$ are bijective ordermorphisms, so the restriction of $\psi {\phi }^{-1}$ to $\widehat{b}$ is abijective 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 $\phi =\psi$.∎

Theorem 5.

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

Proof.

Let $a\in A$ and let $\widehat{b}\in \widehat{B}$ be a section such that there is abijective order morphism ${\psi }_a:\widehat{a}\to \widehat{b}$. ByTheorem 3, $\widehat{b}$ is unique, and so is${\psi }_a$ by Theorem 4. Defining$\phi :A\to B$ by setting $\phi (a)=b$ gives therefore awell-defined (by Theorem 1) and injective ordermorphism. But $\phi$ is also surjective, since any $b\in B$ mapsuniquely to $A$ via $\widehat{b}\to \widehat{a}$, and back again by $\phi$.∎

Theorem 6.

Let $A$ and $B$ be well-ordered sets. Then there is an injective ordermorphism $\iota \mathrm{:}A\mathrm{\to }B$ or $\iota \mathrm{:}B\mathrm{\to }A$. If $\iota$cannot be chosen bijective, then it can at least be chosen such thatits image is a section.

Proof.

Let ${\widehat{A}}_0$ be the set of sections of $A$ from which there is aninjective 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. Otherwisethe 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${\phi }_a:\widehat{a}\to B$ for every element $a\in A$ which isstrictly 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$ forwhich there is no injective order morphism ${\widehat{b}}_0\to A$. Surely,$b_0$ is greater than all the elements from the images of thefunctions ${\phi }_a$, but then there is a bijective ordermorphism from ${\widehat{a}}_0$ to ${\widehat{b}}_0$ byTheorem 5 which is acontradiction. Therefore, all sections of $B$ and $B$ itselfmap injectively and order-preserving to $A$.∎

Theorem 7.

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

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 doesnot exist. Then, by virtue of Theorem 6, there isan injective but not surjective order morphism $\iota :A\to B$ whoseimage is a section $\widehat{b}\in \widehat{B}$. The element $b$ defines a sectionin $\widehat{A}$ which is identical to $A$ byTheorem 3. Thus $\iota$ is surjective which isa contradiction.∎