Set Theory: Ordered Sets and Ordinal Numbers

Definitions of partial ordering, partially ordered (reflexive, transitive, antisymmetric), maximal, minimal.

A bijective function \(f\) is order-preserving if \(a \leq b \Rightarrow f(a) \leq f(b)\). An order-preserving function \(f\) is an isomorphism if \(f(a) \leq f(b) \Leftrightarrow a \leq b\). Two partially ordered sets are isomorphic if there exists an isomorphism between them.

Noncomparable if neither \(a \leq b\) nor \(b \leq a\). A set is ordered if it contains no noncomparable elements. Two isomorphic sets have the same (order) type. Order of \(\mathbb{N}\) (in the normal manner) is \(\omega\). The power \(\aleph_0\) corresponds to the order type \(\omega\).

Definition 1 An ordered set \(M\) is well-ordered if every nonempty subset \(A\) of \(M\) has a smallest (or “​first​”) element, i.e., an element \(\mu\) such that \(\mu \leq a\) for every \(a \in A\).

Definition 2 The order type of a well-ordered set is an ordinal number or simply an ordinal. If the set is infinite, the ordinal is transfinite.

Theorem 1

The ordered sum of a finite number of well-ordered sets \(M_1, M_2, \ldots, M_n\) is itself a well-ordered set.

Proof

Let \(M\) be an arbitrary subset of the ordered sum \(M_1+M_2+\ldots+M_n\), and let \(M_k\) be the first set containing elements of \(M\). Then \(M \cap M_k\) is a subset of the well-ordered set \(M_k\), and therefore has a smallest element \(\mu\). Clearly \(\mu\) is also the smallest element of \(M\).

Need to check whether this holds for the sum of countably many well-ordered sets, and why?

Corollary

The ordered sum of a finite number of ordinal numbers is itself an ordinal number.

Theorem 2

The ordered product of two well-ordered sets \(M_1\) and \(M_2\) is well-ordered.

Proof

Let \(M\) be an arbitrary subset of \(M_1 \cdot M_2\), with \((a, b)\) such that \(a \in M_1\), \(b \in M_2\). The set of all second elements \(b\) in \(M\) is a subset of \(M_2\), and therefore has a least element \(b_1\) since \(M_2\) is well-ordered. Then look at all \((a, b_1)\). Again, the set of all first elements \(a\) is a subset of \(M_1\), hence has a smallest element \(a_1\) since \(M_1\) is well-ordered. \((a_1, b_1)\) is clearly the smallest element of \(M\).

Corollary 1

The ordered product of a finite number of well-ordered sets is itself a well-ordered set.

Corollary 2

The ordered product of a finite number of ordinal numbers is itself an ordinal number.

Every element of a well-ordered set \(M\) determines an (initial) section \(P\), the set of all \(x \in M\) such that \(x < a\), and a remainder \(Q\), the set of all \(x \in M\) such that \(x \geq a\). Given two well-ordered sets \(M\) and \(N\) of order type \(\alpha\) and \(\beta\) respectively, then:

  1. \(\alpha = \beta\) if \(M\) and \(N\) are isomorphic.

  2. \(\alpha < \beta\) if \(M\) is isomorphic to some section of \(N\).

  3. \(\alpha > \beta\) if \(N\) is isomorphic to some section of \(M\).

Lemma

Let \(f\) be an isomorphism of a well-ordered set \(A\) onto some subset \(B \subseteq A\). Then \(f(a) \geq a\) for all \(a \in A\).

Proof

If there exists \(a \in A\) such that \(f(a) < a\), then there is a least such element \(a_0\) since \(A\) is well-ordered. Let \(b_0 = f(a_0)\), then \(b_0 < a_0\), and \(f(b_0) < f(a_0) = b_0\) since \(f\) is an isomorphism. But then \(a_0\) is not the smallest element such that \(f(a) < a\). Contradiction.

Theorem 3

Two given ordinal numbers \(\alpha\) and \(\beta\) satisfy one and only one of the relations \(\alpha < \beta\), \(\alpha = \beta\), \(\alpha > \beta\).

Proof

Let \(W(\alpha)\) be the set of all ordinals \(<\alpha\). Any two numbers \(\gamma\) and \(\gamma^{\prime}\) in \(W(\alpha)\) are comparable and the corresponding ordering of \(W(\alpha)\) makes it a well-ordered set of type \(\alpha\). If a set \(A\) is of type \(\alpha\), then by definition, the ordinals less than \(\alpha\) are the types of well-ordered sets isomorphic to sections of \(A\). Hence, the ordinals are in one-to-one correspondence with the elements of \(A\).

Let \(\alpha\), \(\beta\) be two ordinals, then \(W(\alpha)\), \(W(\beta)\) are well-ordered sets of type \(\alpha\), \(\beta\) respectively. Let \(C = A \cap B\). Then \(C\) is well-ordered, of type \(\gamma\), say. We now show \(\gamma \leq \alpha\). If \(C = A\), then obviously \(\gamma = \alpha\). Otherwise, if \(C \neq A\), then \(C\) is a section of \(A\) and hence \(\gamma < \alpha\).

[Let \(\xi \in C\), \(\eta \in A - C\). Then \(\xi\), \(\eta\) are comparable, i.e., either \(\xi < \eta\) or \(\xi > \eta\). But \(\eta < \xi < \alpha\) is impossible, since then \(\eta \in C\). Therefore \(\xi < \eta\) and hence \(C\) is a section of \(A\), which implies \(\gamma < \alpha\). Moreover, \(\gamma\) is the first element of \(A-C\).]

Thus \(\gamma \leq \alpha\). Similarly \(\gamma \leq \beta\). The case \(\gamma < \alpha\), \(\gamma < \beta\) is impossible, since then \(\gamma \in A-C\), \(\gamma \in B-C\). But then \(\gamma \notin C\) on the one hand and \(\gamma \in A \cap B = C\) on the other hand.

It follows that there are only three possibilities:

\[\gamma = \alpha, \gamma = \beta, \alpha = \beta\] \[\gamma = \alpha, \gamma < \beta, \alpha < \beta\] \[\gamma < \alpha, \gamma = \beta, \alpha > \beta\]

i.e., \(\alpha\) and \(\beta\) are comparable.

Theorem 4

Let \(A\) and \(B\) be well-ordered sets. Then either \(A\) is equivalent to \(B\) or one of the sets is of greater power than the other, i.e., the powers of \(A\) and \(B\) are comparable.

Proof

A definite power corresponds to each ordinal. As ordinals are comparable, so are the corresponding powers.

Well-ordering theorem

Every set can be well-ordered.

Axiom of choice

Given any set \(M\), there is a “choice function” \(f\) such that \(f(A)\) is an element of \(A\) for every nonempty subset \(A \subseteq M\).

Definition 3 Let \(M\) be a partially ordered set, and let \(A\) be any subset of \(M\) such that \(a\) and \(b\) are comparable for every \(a\), \(b \in A\). Then \(A\) is a chain (in \(M\)). A chain \(C\) is maximal if there is no other chain \(C^{\prime}\) in \(M\) containing \(C\) as a proper subset.

Definiton 4 An element \(a\) of a partially ordered set \(M\) is an upper bound of a subset \(M^{\prime} \subseteq M\) if \(a^{\prime} \leq a\) for every \(a^{\prime} \in M^{\prime}\).

The below two assertions are equivalent to the axiom of choice.

Hausdorff’s maximal principle

Every chain in a partially ordered set \(M\) is contained in a maximal chain in \(M\).

Zorn’s Lemma

If every chain in a partially ordered set \(M\) has an upper bound, then \(M\) contains a maximal element.

Theorem 5 (Mathematical induction)

Given a proposition \(P(n)\) formulated fo every positive integer \(n\), suppose that

  1. \(P(1)\) is true.

  2. The validity of \(P(k)\) for all \(k \leq n\) implies the validity of \(P(n+1)\).

Then \(P(n)\) is true for all \(n = 1, 2, \ldots\)

Proof

Suppose \(P(n)\) fails to be true for all \(n = 1, 2, \ldots\) Let \(n_1\) be the smallest integer for which \(P(n)\) is false (\(n_1\) exists due to the well-ordering of the positive integers). Clearly \(n_1 > 1\), so \(n_1 - 1\) is a positive integer. Therefore \(P(n)\) is valid for all \(k \leq n_1 -1\), but not for \(n_1\). Contradiction.

Theorem 5’ (Transfinite induction)

Given a well-ordered set \(A\), let \(P(a)\) be a proposition formulated for every element \(a \in A\). Suppose that

  1. \(P(a)\) is true for the smallest element of \(A\).

  2. The validity of \(P(a)\) for all \(a < a^*\) implies the validity of \(P(a^*)\).

Then \(P(a)\) is true for all \(a \in A\).

Proof

Suppose \(P(a)\) fails to be true for all \(a \in A\). Then \(P(a)\) is false for all \(a\) in some nonempty subset \(A^* \subseteq A\). By well-ordering, \(A^*\) has a smallest element \(a^*\). Therefore \(P(a)\) is valid for all \(a< a^*\) but not for \(a^*\). Contradiction.

Problems

  1. Exhibit both a partial ordering and a simple ordering of the set of all complex numbers.

    Partial ordering: only order reals. Simple: order reals, then complex.

  2. What is the minimal element of the set of all subsets of a given set \(X\), partially ordered by set inclusion? What is the maximal element?

    \(\emptyset\) and \(X\).

  3. A partially ordered set \(M\) is a directed set if, given any two element \(a\), \(b \in M\), there is an element \(c \in M\) such that \(a \leq c\), \(b \leq c\). Are the partially ordered sets in Examples 1-4, Section 3.1 all directed sets?

    No, yes, yes, yes.

  4. The greatest lower bound of two elements \(a\) and \(b\) of a partially ordered set \(M\) is \(c \in M\) such that \(c \leq a\), \(c \leq b\) and there is no element \(d \in M\) such that \(c < d \leq a\), \(d \leq b\). Define least upper bound similarly. A lattice is a partially ordered set with both a greatest lower bound and a least upper bound. Prove that the set of all subsets of a given set \(X\), partially ordered by set inclusion, is a lattice. What is the set-theoretic meaning of the greatest lower bound and least upper bound of two elements of this set?

    Same as 2.

  5. Prove that an order-preserving mapping of one ordered set onto another is automatically an isomorphism.

    All order-mapping preserving mappings are bijective. Hence an inverse exists. Need to show how the inverse also preserves order. Hence isomorphism.

  6. Prove that ordered sums and products of ordered sets are associative.

    Just step through to show that they are the same.

  7. Construct well-ordered sets with ordinals \(\omega + n\), … Show that the sets are all countable.

    \(\mathbb{N} + \{a_1, \ldots, a_n\}\), … Line each one up on a row, and zigzag up and down.

  8. Construct well-ordered sets with ordinals \(\omega \cdot n\), … Show that the sets are all countable.

    \(\mathbb{N} \cdot \{a_1, \ldots, a_n\}\), … Similar proof to countability of the rationals.

  9. Show that \(\omega + \omega = \omega \cdot 2\).

    Let \(f\) send \(a \in \mathbb{N}_1 + \mathbb{N}_2\) to \((a, 1)\) if \(a \in \mathbb{N}_1\) and to \((a, 2)\) if \(a \in \mathbb{N}_2\). Evidently bijective, and order-preserving, hence isomorphic, and hence they have equivalent ordinals too.

  10. Prove that the set \(W(\alpha)\) of all ordinals less than a given ordinal \(\alpha\) is well-ordered.

    Each ordinal less than \(\alpha\) corresponds to a section of \(A\). There is a least section of \(A\), the empty set, as all other sections of \(A\) are greater than or equal to it. Hence the corresponding ordinal to the empty set is the least element of \(W(\alpha)\) and we also know that ordinals are comparable. Therefore \(W(\alpha)\) is well-ordered.

  11. Prove that any nonempty set of ordinals is well-ordered.

    \(A\) subset. Nonempty and ordinals are comparable so exists \(\mu \in A\) such that \(\mu \leq a\) for all \(a \in A\). Therefore well-ordered.

  12. Prove that the set \(M\) of all ordinals corresponding to a countable set is itself countable.

    Line them up. Then use Cantor diagonal argument.

  13. Let \(\aleph_1\) be the power of the set \(M\) in the preceding problem. Prove that there is no power \(m\) such that \(\aleph_0 < m < \aleph_1\).

    Impossible as there is no set which is strictly bigger than countable and yet strictly smaller than uncountable.

Open ends

  1. Why do Theorems 1 and 2 hold for just finitely many? Do they also hold for countably many? If not, why not?

  2. What well-ordered set has ordinal \(\omega^{\omega}\)?

    I found this link https://en.wikipedia.org/wiki/Ordinal_analysis#Theories_with_proof-theoretic_ordinal_%CF%89%CF%89 but it still leaves me none the wiser. This link https://math.stackexchange.com/questions/1412153/let-omega-be-the-ordinal-of-the-well-ordered-set-mathbbn-what-does-mean is a tiny bit clearer.

  3. For Problem 5, how is it shown that the inverse preserves order?

  4. Is the proof for Problem 13 correct?

I would greatly appreciate any help.

Christian Christiansen