In order to pass this assignment you have to get at least two of the following four exercises right. (Minor mistakes may be accepted.)
State and give a brief explanation of the Church-Turing thesis.
Give an example of a function on the natural numbers (from ℕ to ℕ) that is:
Injective but not surjective.
Bijective.
Is ℕ × Bool countable? Provide a proof. (Bool is a set with two elements, true and false.)
[BN] Is ℕ → Bool countable? Provide a proof.
(Exercises marked with [BN] are based on exercises from a previous version of this course, given by Bengt Nordström.)