properties of well-ordered sets

The purpose of this entry is to collect properties of well-ordered sets. We denote all orderings uniformly by $\le$. 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\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 a bijective order morphism $\phi :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\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 is ordered 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 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 $\phi \mathrm{:}A\mathrm{\to }B$ a bijective 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 by Theorem 1. The rest of the theorem follows since $\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 an injective 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 element which in turn defines a smaller section of $A$. We may therefore define 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 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 ${\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 one bijective 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 the restrictions ${\phi |}_{\widehat{a}}:\widehat{a}\to \widehat{b}$ and ${\psi |}_{\widehat{a}}:\widehat{a}\to \widehat{c}$ are bijective order morphisms, so the restriction of $\psi {\phi }^{-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 $\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 order morphism $\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 a bijective order morphism ${\psi }_a:\widehat{a}\to \widehat{b}$. By Theorem 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 a well-defined (by Theorem 1) and injective order morphism. But $\phi$ is also surjective, since any $b\in B$ maps uniquely 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 order morphism $\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 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 ${\phi }_a:\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 ${\phi }_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\mathrm{\subseteq }A$ a nonempty subset. Then there is a bijective order morphism from $B$ to one of the 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 does not exist. Then, by virtue of Theorem 6, there is an injective but not surjective order morphism $\iota :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. ∎

Title	properties of well-ordered sets
Canonical name	PropertiesOfWellorderedSets
Date of creation	2013-03-22 15:23:42
Last modified on	2013-03-22 15:23:42
Owner	GrafZahl (9234)
Last modified by	GrafZahl (9234)
Numerical id	10
Author	GrafZahl (9234)
Entry type	Theorem
Classification	msc 06A05
Synonym	initial segment
Defines	section