3.9 Well ordering [1YQ]

[222]The theory of well orderings is very much linked to the theory of ordinals, of which we have given a few hints in Sec. ??. We just say that every ordinal is the standard representative of a type of well ordering. Using standard ordinal theory (due to Von Neumann) many of the subsequent exercises can be reformulated and simplified.

E104

[07W]If \((X,≤)\) is a well-ordered set and \(Y⊆ X\) is a subset, then \(Y\) (with the restriction of the ordering) \(≤\) is a well-ordered set.

E104

[07X] Prerequisites:134.(Solved on 2023-01-17) (Proposed on 2022-12) Let \(X\) be totally ordered set. Show that these are equivalent:

1. \(X\) is well ordered;

2. there are no strictly decreasing functions \(f:ℕ→ X\).

(This is a special case of 11)

E104

[22F]Prerequisites:72,64,69,2.Difficulty:*.Note:exercise 2 written exam on 29 January 2021.(Solved on 2022-10-13
in part)

Let be given \((X,≤_ X )\) where \(X\) is an infinite set and \(≤_ X\) is a well ordering.

• If \(X\) has no maximum, then there exists \((Y,≤_ Y )\) such that setting \(Z=Y× ℕ\) with \(≤_ Z\) the lexicographical order, then \((X,≤_ X)\) and \((Z,≤_ Z)\) have the same type of order.

• If instead \(X\) has maximum, then there exist \((Y,≤_ Y )\) and \(k∈ℕ\) such that, setting \(Z\) be the concatenation of \(Y× ℕ\) and \(\{ 0,\ldots k\} \) (where \(Y×ℕ\) has the lexicographical order, as above), then \((X,≤_ X)\) and \((Z,≤_ Z)\) have the same type of order.

• Show that, in the previous cases, \(Y\) is well ordered.

Hidden solution: [UNACCESSIBLE UUID ’22G’]

E104

[0DQ]Difficulty:*.(Proposed on 2022-12) Let the ordered set \((X,≤)\) be given; we define

\[ P_ x {\stackrel{.}{=}}\{ w∈ X: w {\lt} x\} \quad . \]

Suppose \((X,≤)\) meets these two requirements:

• \[ ∀ x,y∈ X~ ,~ P_ x = P_ y ⇒ x=y \]

• every non-empty set \(A⊆ X\) contains at least one minimal element, i.e.

  \[ ∃ a∈ A, ∀ b∈ A ¬(b{\lt}a)\quad ; \]

then \((X,≤)\) is well ordered.

Hidden solution: [UNACCESSIBLE UUID ’26R’]

Successor

E105

[1Z1]Prerequisites:105. (Proposed on 2023-01-17)

Suppose \(X\) has no maximum; let \(S\) be defined as in 105; show that is an injective function

\[ S:X→ X\quad , \]

and that \(S(x)≠ 0_ X\), for every \(x\) (that is, \(0_ X\) is not successor of any element).

Hidden solution: [UNACCESSIBLE UUID ’223’]

We note that in general \(S\) will not be surjective, as a function \(S: X→ X⧵ \{ 0_ X\} \): there may be elements \(y∈ S, y≠ 0_ X\) that are not successors of an element. If, however, for a given \(y∈ X\), there exists \(x∈ X\) such that \(y=S(x)\), we will say that \(x\) is the predecessor of \(y\).

E105

[22H]Prerequisites:105,1.If \(x≤ y≤ S(x)\) then \(y=x∨ y=S(x)\).

Hidden solution: [UNACCESSIBLE UUID ’22J’]

(The meaning of this result is that \(S(x)\) is the immediate successor of \(x\), there is nothing in between...).

Segments and well orderings

In the following \((X,\le _ X)\) will be a well-ordered set.

E106

[07Z] Show that the initial segment union is an initial segment.

E106

[080] (Solved on 2023-01-17) If \(S⊆ X\) is an initial segment and \(S≠ X\), show that \(s∈ X⧵ S\) exists and is unique (\(s\) is called the next item to \(S\)) which extends \(S\), i.e. such that \(S ∪ \{ s\} \) is an initial segment. Hidden solution: [UNACCESSIBLE UUID ’081’] (Note that there are similarities with the concept of "successor" seen in 105... We could say that \(s\) is the successor of the segment \(S\)).

E106

[082] Prerequisites: 67, 68, 4.(Solved on 2023-01-17) Let \(X\) be a well-ordered set. Show that if \(I⊆ X\) is an interval then \(I=[a,b)\) or \(I=[a,b]\) or \(I=[a,∞)\) with \(a,b∈ X\). (The reverse is obviously true).

In particular, an initial segment is \([0_ X,b)\) or \([0_ X,b]\) or all \(X\). Hidden solution: [UNACCESSIBLE UUID ’083’]

E106

[084] Let \((X,≤_ X),(Y,≤_ Y)\) be totally ordered non-empty sets. Let \(f:X→ Y\) be a strictly increasing bijective function. Then for each \(S⊆ X\) initial segment we have that \(f(S)\) is an initial segment of \(Y\); and vice versa. Hidden solution: [UNACCESSIBLE UUID ’085’]

E106

[086] Prerequisites:2,134,69.

Let \((X,≤_ X)\) be a well-ordered non-empty set. Show that if \(S⊆ X\) is an initial segment and \((X,≤_ X)\) and \((S,≤_ X)\) are equiordinate from the map \(f:S→ X\) then \(X=S\) and \(f\) is the identity.

Hidden solution: [UNACCESSIBLE UUID ’087’][UNACCESSIBLE UUID ’088’]

(Note the difference with cardinality theory: An infinite set is in one-to-one correspondence with some of its proper subsets, cf 2 and 2. Moreover, if two sets have the same cardinality then there are many bijections between them.)

E106

[089](Solved on 2023-01-17) Give an example of a totally ordered set \((X,≤_ X)\) which has minimum, and of an initial segment \(S\) such that \((X,≤_ X)\) and \((S,≤_ X)\) are equiordinate. Hidden solution: [UNACCESSIBLE UUID ’08B’]

E106

[08C]Prerequisites:5.(Proposed on 2022-12) Let \((X,≤_ X)\) and \((Y,≤_ Y)\) be well ordered; suppose there exists a bijective function \(f:X→ T\) strictly increasing  where \(T\) an initial segment of \(Y\); then \(f\) is unique (and unique is \(T\)). Hidden solution: [UNACCESSIBLE UUID ’08D’]

E106

[08F]Prerequisites:17, 1, 4, 2, 7.

Let be given two well-ordered non-empty sets \((X,≤_ X)\) and \((Y,≤_ Y)\). Show that

1. there is an initial segment \(S\) of \(X\) and a strictly increasing monotonic bijective function \(g:S→ Y\); or ²

2. there is an initial segment \(T\) of \(Y\) and a bijective strictly increasing monotonic function \(g:X→ T\).

In the first case we will write that \((Y,≤_ Y)⪯ (X,≤_ X)\), in the second that \((X,≤_ X)⪯ (Y,≤_ Y)\). (Note that in the first case you have \(|Y|≤ |X|\) and in the second \(|X|≤ |Y|\)). By the previous exercise, the map \(g\) and its segment are unique.

Hidden solution: [UNACCESSIBLE UUID ’08G’]

E106

[08H]Prerequisites:8.Show that if \((X,≤_ X)⪯ (Y,≤_ Y)\) and also \((Y,≤_ Y)⪯ (X,≤_ X)\), then they are equiordinate.

Hidden solution: [UNACCESSIBLE UUID ’08J’]

The relation \(⪯\) is therefore a total order between types of well-orderings.

Examples

E106

[08K] Prerequisites:3.The type of well ordering of \(ℕ\) is called \(𝜔\). Given \(k≥ 2\) natural, \(ℕ^ k\) endowed with the lexicographical order is a well-ordered set (for 3), and the type of ordering is called  \(𝜔^ k\). Show that \(𝜔^ k⪯𝜔^ h \) for \(h{\gt}k\), and that \(𝜔^ k,𝜔^ h \) do not have the same type of order.

E106

[08M] Difficulty:*.Build a well ordering on a countable set \(X\) such that \(X=⋃_{n=1}^∞ S_ n\) where \(S_ n\) are initial segments, each with order type \(𝜔^ n\). The order so built on \(X\) is indicated by  \(𝜔^𝜔\). Hidden solution: [UNACCESSIBLE UUID ’08N’]

E106

[08P]Difficulty:*.Build a strictly increasing map between \(𝜔^𝜔\) and \(ℝ\). Hidden solution: [UNACCESSIBLE UUID ’08Q’]

[UNACCESSIBLE UUID ’08R’]

[UNACCESSIBLE UUID ’08S’]