Countability and Cantor's diagonal argument
Warm-upHumanThe zigzag lists the integers as What is ?
The zigzag lists the integers as What is ?
Compute Cantor's pairing for , .
Which pair has ?
Which of these sets are countable? (Choose all that apply.)
A list begins , , . Using the lesson's rule (digit of is if digit of is , and otherwise), how does begin?
After seeing the diagonal argument, Kofi says: “Fine, the list missed . So put at the front of the list — now nothing is missing.” What is the best reply?
Let and define by , , . List the elements of Cantor's diagonal set .
How many elements does have?
Which Lean statement expresses Cantor's theorem for a type α?
Write pair(m, n) computing Cantor's , and its inverse unpair(k), which returns the pair (m, n) with pair(m, n) == k. (Hint: find the diagonal as the largest with .)