Skip to content
The Lumenary

Practice · Grades 9–12

Countability and Cantor's diagonal argument

Countability and Cantor's diagonal argument

Warm-upHuman

The zigzag z:N→Zz : \N \to \Z lists the integers as z(0),z(1),z(2),⋯=0,−1,1,−2,2,…z(0), z(1), z(2), \dots = 0, -1, 1, -2, 2, \dots What is z(7)z(7)?

Countability and Cantor's diagonal argument

Warm-upHuman

Compute Cantor's pairing π(2,3)=(m+n)(m+n+1)2+n\pi(2, 3) = \dfrac{(m + n)(m + n + 1)}{2} + n for m=2m = 2, n=3n = 3.

Countability and Cantor's diagonal argument

CoreHuman

Which pair (m,n)(m, n) has π(m,n)=12\pi(m, n) = 12?

Choose one

Countability and Cantor's diagonal argument

CoreHuman

Which of these sets are countable? (Choose all that apply.)

Choose all that apply

Countability and Cantor's diagonal argument

CoreHuman

A list begins r1=0.5123…r_1 = 0.5123\ldots, r2=0.3456…r_2 = 0.3456\ldots, r3=0.9995…r_3 = 0.9995\ldots. Using the lesson's rule (digit nn of xx is 44 if digit nn of rnr_n is 55, and 55 otherwise), how does xx begin?

Choose one

Countability and Cantor's diagonal argument

CoreHuman

After seeing the diagonal argument, Kofi says: “Fine, the list missed xx. So put xx at the front of the list — now nothing is missing.” What is the best reply?

Choose one

Countability and Cantor's diagonal argument

CoreHuman

Let A={1,2,3}A = \{1, 2, 3\} and define f:A→P(A)f : A \to \mathcal{P}(A) by f(1)={1,2}f(1) = \{1, 2\}, f(2)={3}f(2) = \{3\}, f(3)={1,3}f(3) = \{1, 3\}. List the elements of Cantor's diagonal set D={a∈A:a∉f(a)}D = \{a \in A : a \notin f(a)\}.

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

Countability and Cantor's diagonal argument

Warm-upHuman

How many elements does P(P({1,2}))\mathcal{P}(\mathcal{P}(\{1, 2\})) have?

Countability and Cantor's diagonal argument

CoreFormal

Which Lean statement expresses Cantor's theorem for a type α?

Choose one

Countability and Cantor's diagonal argument

StretchComputational

Write pair(m, n) computing Cantor's π(m,n)=(m+n)(m+n+1)/2+n\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+nd = m + n as the largest dd with d(d+1)/2≤kd(d+1)/2 \le k.)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.