The Lumenary · Advanced undergraduate

Ordinals and cardinals

Name: ______________________

Date: ______________________

You will learn to

Define ordinals as transitive sets well-ordered by $\in$ , and prove that any two ordinals are comparable and that there is no set of all ordinals
Prove that every well-ordered set is isomorphic to exactly one ordinal
Use transfinite induction and transfinite recursion to prove statements about, and define operations on, the ordinals
Compute with ordinal arithmetic and explain why it is not commutative
Prove Cantor's theorem and the Schröder–Bernstein theorem, and compute cardinal sums and products using $\kappa \cdot \kappa = \kappa$
Distinguish ordinals from cardinals, and state precisely what the continuum hypothesis asserts

1.
Which of these ordinals are equal to $\omega$ ? Select all.
- A. $1 + \omega$
- B. $\omega + 1$
- C. $5 + \omega$
- D. $2 \cdot \omega$
- E. $\omega \cdot 2$
2.
Write $(\omega + 3) \cdot 2$ in the form $\omega \cdot 2 + k$ with $k$ a natural number. What is $k$ ?
3.
Write $2 \cdot (\omega + 3)$ in the form $\omega + k$ with $k$ a natural number. What is $k$ ?
4.
In the proof that a strictly increasing $f : W \to W$ on a well-order satisfies $x \le f(x)$ , we take the least $m$ with $f(m) < m$ . Why does this lead to a contradiction?
- A.Because $f(f(m)) < f(m)$ , so $f(m)$ is a smaller element with the same property
- B.Because $f$ is surjective, so $m = f(y)$ for some $y$
- C.Because $f(m) < m$ contradicts $f$ being increasing
- D.Because $W$ is finite
5.
Which of these statements are provable in ZF, without the axiom of choice? Select all.
- A.If $|A| \le |B|$ and $|B| \le |A|$ then $|A| = |B|$
- B.There is no surjection $A \to \mathcal P(A)$
- C.For every set $A$ there is an ordinal that does not inject into $A$
- D.For all sets $A, B$ : $|A| \le |B|$ or $|B| \le |A|$
- E.Every infinite set has an aleph as its cardinality
6.
What is the cardinality of $\R \times \N$ ?
- A. $2^{\aleph_0}$
- B. $\aleph_0$
- C. $2^{\aleph_0} \cdot \aleph_0$ , which is larger than $2^{\aleph_0}$
- D. $2^{2^{\aleph_0}}$
7.
Which Lean statement correctly formalises Cantor's theorem for a type α?
- A.∀ f : α → Set α, ¬ Function.Surjective f
- B.∀ f : α → Set α, ¬ Function.Injective f
- C.∀ f : Set α → α, ¬ Function.Surjective f
- D.∃ f : α → Set α, ¬ Function.Surjective f
8.
Here is a faulty argument. “(1) The map $n \mapsto n + 1$ together with $\omega \mapsto 0$ is a bijection from $\omega + 1$ to $\omega$ . (2) So $\omega + 1$ and $\omega$ have the same cardinality. (3) So $\omega + 1$ and $\omega$ are isomorphic well-orders. (4) Hence $\omega + 1 = \omega$ by uniqueness of order types.” Which step is wrong?
- A.Step (1)
- B.Step (2)
- C.Step (3)
- D.Step (4)
9.
Represent an ordinal below $\omega^\omega$ by its list of coefficients, lowest power first: [c0, c1, ..., ck] stands for $\omega^k c_k + \cdots + \omega c_1 + c_0$ (so [3, 0, 2] is $\omega^2 \cdot 2 + 3$ , and [] is $0$ ), with no trailing zeros. Write ord_add(a, b) computing the ordinal sum $a + b$ . Rule: the terms of $a$ below the leading power of $b$ are absorbed, the coefficients at the leading power of $b$ add up, and the higher terms of $a$ remain.
Computational — Practice

Answer key — Ordinals and cardinals

1.
$1 + \omega = 5 + \omega = 2 \cdot \omega = \omega$ , since in each case every point has only finitely many points before it and there is no last point. $\omega + 1$ has a last point, and in $\omega \cdot 2 = \omega + \omega$ the first point of the second copy has infinitely many predecessors; neither is isomorphic to $\omega$ .
2.
$(\omega + 3) \cdot 2 = (\omega + 3) + (\omega + 3) = \omega + (3 + \omega) + 3 = \omega + \omega + 3 = \omega \cdot 2 + 3$ . So $k = 3$ . The middle $3$ is swallowed by the $\omega$ after it; the last one is not.
3.
$2 \cdot (\omega + 3) = 2 \cdot \omega + 2 \cdot 3 = \omega + 6$ , so $k = 6$ . Compare the previous exercise: $(\omega + 3) \cdot 2 = \omega \cdot 2 + 3$ . Order matters.
4.
From $f(m) < m$ and strict monotonicity, $f(f(m)) < f(m)$ . So $f(m)$ also satisfies $f(y) < y$ , and $f(m) < m$ — contradicting the choice of $m$ as the least such element. The example $x \mapsto x - 1$ on $\Z$ shows the well-order is essential.
5.
Schröder–Bernstein, Cantor's theorem and Hartogs' theorem are theorems of ZF: their proofs define the required objects. Comparability of all cardinalities, and the statement that every set has an aleph as its cardinality, are each equivalent over ZF to the axiom of choice.
6.
$|\R \times \N| = 2^{\aleph_0} \cdot \aleph_0$ . Since $2^{\aleph_0}$ is infinite and $0 < \aleph_0 \le 2^{\aleph_0}$ , Corollary 15 gives $2^{\aleph_0} \cdot \aleph_0 = 2^{\aleph_0}$ . (Concretely: $\R \times \N$ is a countable union of copies of $\R$ , which can be fitted into $\R$ as the intervals $[n, n + 1)$ .)
7.
Cantor's theorem says that no function $A \to \mathcal P(A)$ is surjective: ∀ f : α → Set α, ¬ Function.Surjective f. Option b is false (singletons give an injection), option c is false for non-empty α, and option d is true but says almost nothing.
8.
Step (3) is wrong. A bijection shows equal cardinality; an order isomorphism must also preserve the order. In fact no isomorphism $\omega + 1 \to \omega$ exists, because $\omega + 1$ has a largest element and $\omega$ does not. This is exactly the difference between ordinals and cardinals.
9.
```
def ord_add(a, b):
    if not b:
        return list(a)
    k = len(b) - 1
    lead = b[k] + (a[k] if k < len(a) else 0)
    return list(b[:k]) + [lead] + list(a[k + 1:])
```
Why: write $a = (\text{terms of power} > k) + \omega^k a_k + (\text{lower terms})$ . The lower terms of $a$ are smaller than $\omega^k$ , and anything smaller than $\omega^k$ followed by $\omega^k$ is absorbed (just as $3 + \omega = \omega$ ). So $a + b = (\text{terms of } a \text{ of power} > k) + \omega^k (a_k + b_k) + (\text{lower terms of } b)$ .