properties of well-ordered sets


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

The following properties are easy to see:

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

    B>:={aABba for all bB},

    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 bijectiveMathworldPlanetmathPlanetmath order morphism φ:AB, then B is well-ordered.

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

Definition 1 (section).

Let A be well-ordered. Then for every aA we define the sectionPlanetmathPlanetmathPlanetmath of a:

a^:={bAba}.

A section is also known as an initial segment. We denote the set of all sections of A by A^. This set is ordered by inclusion.

Theorem 1.

Let A be a well-ordered set. Then the mapping ^:AA^ defined by aa^ is a bijective order morphism. In particular, A^ is well-ordered.

Proof.

Let a,bA with ab. Then a^b^, so ^ is an order morphism. Now assume that a^=b^. If a didn’t equal b, we would have ba^, leading to a contradictionMathworldPlanetmathPlanetmath. Therefore ^ is injectivePlanetmathPlanetmath. Now let CA^, then there exists a cA such that c^=C, so ^ is surjective. ∎

Theorem 2.

Let A and B be well-ordered sets and φ:AB a bijective order morphism. Then there exists a bijective order morphism φ^:A^B^ such that for all aA

φ^(a^)=φ(a)^.
Proof.

Setting φ^(a^):=φ(a)^ is well-defined by TheoremMathworldPlanetmath 1. The rest of the theorem follows since ^ and φ are bijective order morphisms. ∎

Theorem 3.

Let A be a well-ordered set and aA such that there is an injective order morphism φ:Aa^. Then A=a^.

Proof.

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

B0 :=φ(a^), A0 :=section defined by maximal element of B0,
Bn :=φ(An-1), An :=section defined by maximal element of Bn.

Now A^ is well-ordered, so the set defined by the elements of the sequence (An) has a minimal element, that is AN=AN+1 and hence BN=BN+1 for some sufficiently large N. Applying φ-1 N+1 times to the latter equation yields a^=A0, 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 φ:AB.

Proof.

Let φ,ψ:AB be two bijective order morphisms. Let aA and set b:=φ(a) and c:=ψ(a). Then the restrictionsPlanetmathPlanetmath φ|a^:a^b^ and ψ|a^:a^c^ are bijective order morphisms, so the restriction of ψφ-1 to b^ is a bijective order morphism to c^. Now either b^c^ or c^b^, so by Theorem 3 b^=c^, hence b=c and thus φ=ψ. ∎

Theorem 5.

Let A and B be well-ordered sets such that for every section a^A^ there is a bijective order morphism to a section b^B^ and vice-versa, then there is a bijective order morphism φ:AB.

Proof.

Let aA and let b^B^ be a section such that there is a bijective order morphism ψa:a^b^. By Theorem 3, b^ is unique, and so is ψa by Theorem 4. Defining φ:AB by setting φ(a)=b gives therefore a well-defined (by Theorem 1) and injective order morphism. But φ is also surjective, since any bB maps uniquely to A via b^a^, and back again by φ. ∎

Theorem 6.

Let A and B be well-ordered sets. Then there is an injective order morphism ι:AB or ι:BA. If ι cannot be chosen bijective, then it can at least be chosen such that its image is a section.

Proof.

Let A^0 be the set of sections of A from which there is an injective order morphism to B. If A^0 is the empty setMathworldPlanetmath, then B must be empty, since otherwise we could map the least element of A to B. If A^0 is not empty, we may consider the set A0:=A^0. If A0=A, nothing remains to be shown. Otherwise the set AA0 is nonempty an hence has a least element a0A. By construction, there is no injective order morphism from a^0 to B, but there is an injective order morphism from φa:a^B for every element aA which is strictly smaller than a0. Now assume there is an element bB such that there is no injective order morphism from b^A. Then we can similarly construct a least element b0B for which there is no injective order morphism b^0A. Surely, b0 is greater than all the elements from the images of the functions φa, but then there is a bijective order morphism from a^0 to 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 BA a nonempty subset. Then there is a bijective order morphism from B to one of the sets in A^{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 ι:AB whose image is a section b^B^. The element b defines a section in A^ which is identical to A by Theorem 3. Thus ι 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
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