PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] properties of well-ordered sets (Theorem)

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:

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$:
$\displaystyle \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. $ \qedsymbol$
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$
$\displaystyle \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. $ \qedsymbol$
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 :=$section defined by maximal element of $\displaystyle B_0,$    
$\displaystyle B_n$ $\displaystyle :=\varphi(A_{n-1}),$ $\displaystyle A_n$ $\displaystyle :=$section defined by maximal element of $\displaystyle 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$. $ \qedsymbol$
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\vert _{\widehat {a}}\colon\widehat {a}\to\widehat {b}$ and $ \left.\psi\right\vert _{\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$. $ \qedsymbol$
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 [*]) 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$. $ \qedsymbol$
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$. $ \qedsymbol$
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. $ \qedsymbol$

Bibliography

C
G. CANTOR, Beiträge zur Begründung der transfiniten Mengenlehre (Zweiter Artikel), Math. Ann. 49, 207-246 (1897).



Anyone with an account can edit this entry. Please help improve it!

"properties of well-ordered sets" is owned by GrafZahl. [ full author list (4) ]
(view preamble)

View style:

Other names:  initial segment
Also defines:  section

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: functions, empty set, maps, restrictions, equation, minimal element, sequences, monotonically decreasing, maximal element, image, well-defined, surjective, injective, contradiction, mapping, inclusion, structure, order morphism, bijective, poset, well-ordered, least element, strictly, subset, totally ordered set, easy to see, properties, orderings
There are 6 references to this entry.

This is version 6 of properties of well-ordered sets, born on 2005-07-16, modified 2008-04-30.
Object id is 7231, canonical name is PropertiesOfWellOrderedSets.
Accessed 3266 times total.

Classification:
AMS MSC06A05 (Order, lattices, ordered algebraic structures :: Ordered sets :: Total order)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)