The Lumenary · Grades 9–12

Countability and Cantor's diagonal argument

Name: ______________________

Date: ______________________

You will learn to

Define when two sets have the same cardinality, and when a set is countable or uncountable
Show that $\Z$ , $\N \times \N$ and $\Q$ are countable by constructing explicit enumerations or bijections
Define the power set $\mathcal{P}(A)$ and prove Cantor's theorem that no function $A \to \mathcal{P}(A)$ is surjective
Reproduce Cantor's diagonal argument that $[0, 1)$ is uncountable, handling numbers with two decimal expansions
Explain why transcendental numbers must exist, and what is known about sizes between $\N$ and $\R$

1.
The zigzag $z : \N \to \Z$ lists the integers as $z(0), z(1), z(2), \dots = 0, -1, 1, -2, 2, \dots$ What is $z(7)$ ?
2.
Compute Cantor's pairing $\pi(2, 3) = \dfrac{(m + n)(m + n + 1)}{2} + n$ for $m = 2$ , $n = 3$ .
3.
Which pair $(m, n)$ has $\pi(m, n) = 12$ ?
- A. $(2, 2)$
- B. $(3, 1)$
- C. $(1, 3)$
- D. $(0, 4)$
4.
Which of these sets are countable? (Choose all that apply.)
- A. $\Z$
- B. $\Q$
- C. $\N \times \N$
- D.the algebraic numbers
- E. $\R$
- F. $\mathcal{P}(\N)$
- G.the irrational numbers
5.
A list begins $r_1 = 0.5123\ldots$ , $r_2 = 0.3456\ldots$ , $r_3 = 0.9995\ldots$ . Using the lesson's rule (digit $n$ of $x$ is $4$ if digit $n$ of $r_n$ is $5$ , and $5$ otherwise), how does $x$ begin?
- A. $0.455\ldots$
- B. $0.544\ldots$
- C. $0.555\ldots$
- D. $0.459\ldots$
6.
After seeing the diagonal argument, Kofi says: “Fine, the list missed $x$ . So put $x$ at the front of the list — now nothing is missing.” What is the best reply?
- A.The new list has its own diagonal number, which is missing from it. The argument shows that every list misses a number.
- B.You are not allowed to change the list.
- C.The list is infinite, so there is no front to put it at.
- D.Kofi is right; the argument only shows that some lists are incomplete.
7.
Let $A = \{1, 2, 3\}$ and define $f : A \to \mathcal{P}(A)$ by $f(1) = \{1, 2\}$ , $f(2) = \{3\}$ , $f(3) = \{1, 3\}$ . List the elements of Cantor's diagonal set $D = \{a \in A : a \notin f(a)\}$ .
8.
How many elements does $\mathcal{P}(\mathcal{P}(\{1, 2\}))$ have?
9.
Which Lean statement expresses 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.Bijective f
10.
Write pair(m, n) computing Cantor's $\pi(m, n) = (m+n)(m+n+1)/2 + n$ , and its inverse unpair(k), which returns the pair (m, n) with pair(m, n) == k. (Hint: find the diagonal $d = m + n$ as the largest $d$ with $d(d+1)/2 \le k$ .)
Computational — Practice

Answer key — Countability and Cantor's diagonal argument

1.
Since $7$ is odd, $z(7) = -(7 + 1)/2 = -4$ . Indeed the list is $0, -1, 1, -2, 2, -3, 3, -4, \dots$ , and position $7$ (counting from $0$ ) holds $-4$ .
2.
$m + n = 5$ , so $\pi(2, 3) = \frac{5 \cdot 6}{2} + 3 = 15 + 3 = 18$ . The pair lies on diagonal $5$ , which starts at $T(5) = 15$ , and is the point with $n = 3$ along it.
3.
$T(4) = 10 \le 12 < 15 = T(5)$ , so $(m, n)$ lies on diagonal $d = 4$ , at position $n = 12 - 10 = 2$ ; hence $m = 4 - 2 = 2$ . Check: $\pi(2, 2) = \frac{4 \cdot 5}{2} + 2 = 12$ .
4.
Countable: $\Z$ , $\Q$ , $\N \times \N$ and the algebraic numbers. Uncountable: $\R$ (diagonal argument), $\mathcal{P}(\N)$ (Cantor's theorem) and the irrationals — if they were countable, $\R$ would be the union of two countable sets and hence countable.
5.
The diagonal digits are $5$ (first digit of $r_1$ ), $4$ (second digit of $r_2$ ) and $9$ (third digit of $r_3$ ). The rule turns them into $4, 5, 5$ , so $x = 0.455\ldots$ , which differs from $r_n$ in digit $n$ for $n = 1, 2, 3$ — and, continued for ever, from every number on the list.
6.
Adding $x$ produces a new list, and the diagonal construction applied to it produces a new number $x'$ missing from it. Since the proof works for any list, no list of real numbers is complete — which is exactly what “uncountable” means.
7.
$1 \in f(1)$ and $3 \in f(3)$ , but $2 \notin f(2) = \{3\}$ . So $D = \{2\}$ . As Cantor's theorem promises, $D$ is not among the values $\{1, 2\}, \{3\}, \{1, 3\}$ of $f$ : it differs from $f(a)$ exactly at the element $a$ .
8.
$\mathcal{P}(\{1, 2\}) = \{\varnothing, \{1\}, \{2\}, \{1, 2\}\}$ has $4$ elements, so its power set has $2^4 = 16$ elements. In general $n < 2^n < 2^{2^n}$ , the finite shadow of Cantor's theorem.
9.
Cantor's theorem is ∀ f : α → Set α, ¬ Function.Surjective f: no function from α hits every subset of α. The diagonal set {x | x ∉ f x} is always missed.
10.
```
def pair(m, n):
    d = m + n
    return d * (d + 1) // 2 + n

def unpair(k):
    d = 0
    while (d + 1) * (d + 2) // 2 <= k:
        d += 1
    n = k - d * (d + 1) // 2
    return (d - n, n)
```
The tests check the two functions are inverse on a finite range; Theorem 4 proves it for all values. (A faster unpair uses math.isqrt: $d = \lfloor(\sqrt{8k + 1} - 1)/2\rfloor$ .)