Problem 1 For each of the following sets, state whether it is finite, countably infinite or uncountably infinite. Prove your claim.

(a) The set P(ℕ) ∩ P({2^{−i} | i ∈ ℕ}).

(b) The set of Θ(1) functions from ℕ to ℕ.

(c) The set of O(1/n) functions from ℕ to ℕ.

(d) The set of sequences of rational numbers which converge to zero.

(e) The set of functions {R_{f} : ℕ → ℕ | f : ℕ → ℕ}, where

R_{f}(n) = \{ \begin{matrix}f(R_{f}(n − 1)), & for n ≠ 0 \\ 0, & for n = 0 \end{matrix}

Problem 2 Let S = \{n ∈ ℕ^{+} | \{n\sqrt{2}\} < 0.01\}. (Note: \{x\} = x − ⌊x⌋)

(a) Use the pigeonhole principle to show that S is nonempty.

(b) Show that S is infinite. Problem 3 Let s = s_{1}s_{2} … s_{2n} be a string of 0s and 1s. The reverse of s is the string R(s) = s_{2n}s_{2n−1} … s_{1}.

(a) A string that is equal to its reverse is called a palindrome. How many palindromes of length 2n are there?

(b) How many strings of length 2n have exactly 2r bits in common with their reverse?

(c) A string s is 1-derful if all the common bits of s and R(s) are 1 bits. How many of the strings from part (b) are 1-derful?

(d) What is the total number of 1-derful strings of length 2n?