[BN] Is ℕ → {*} countable? (Here {*} is a set with one element.) Provide a proof.
[BN] The set of partial functions from A to B, A ⇀ B, consists of functions f that, given an input x ∈ A, either give a result in B, or fail to give a result. Is ℕ ⇀ {*} countable? Provide a proof.
[BN] Can you "go straight down" instead of diagonally in a diagonalisation argument? What about "straight to the right"? What about "two down and one to the right"? What about "one down and two to the right"?
Are the real numbers countable? Consider infinite decimal expansions. Note that, for instance, 1.2399999… = 1.2400000….
[BN] Spot an error in the following "proof" showing that the natural numbers are not countable:
Assume for a contradiction that the natural numbers are countable. We know that there is at least one natural number, so we get a surjection s : ℕ → ℕ. Now compose this surjection with a function binary : ℕ → List {0, 1} mapping each natural number to its binary representation. We get a surjection s′ = binary ∘ s : ℕ → List {0, 1}.
Let us now construct a list of bits bs by letting bit n, bsₙ, be not ((s′ n)ₙ). By surjectivity of s′ we get that there is some i for which s′ i = bs. We get
(s′ i)ᵢ = bsᵢ = not ((s′ i)ᵢ),
which is a contradiction.
[BN] Prove that a subset of a countable set is countable.
[BN] In Enumerable sets and Hilbert's hotel there are two enumerations of ℕ × ℕ. Explain why the sparse one is correct.
(Exercises marked with [BN] are based on exercises from a previous version of this course, given by Bengt Nordström.)