diagonalisation argument

Question

Let $$ B = \{f:\Bbb N\to \{0,1\}\mid \forall k,m.f(2^k) = f(2^m)\} $$ Prove using diagonalisation argument that $B$ is not a countable set.

Thanks!

Answer 1

Let $X := \{2^n \mid n \in \Bbb N\}$ be the set of powers of two.

Let $\varphi : \Bbb N \to (\Bbb N \setminus X)$ be an enumeration of the numbers that are not powers of two.

Let $\varphi^{-1}$ be its inverse.

---

If the set were countable, then there would be an enumeration $\psi : \Bbb N \to B$.

Now, construct a function $f: n \mapsto \begin{cases} 0 & n \in X \\ 1-\psi(\varphi^{-1}(n))(n) & n \notin X \end{cases}$

If $\psi$ were surjective, we would have $N$ such that $\psi(N) = f$, since $f \in B$.

Consider $\psi(N)(\varphi(N))$ and $f(\varphi(N))$.

By deifnition of $f$, $f(\varphi(N)) = 1-\psi(\varphi^{-1}(\varphi(N)))(\varphi(N)) = 1-\psi(N)(\varphi(N))$, which cannot be equal to $\psi(N)(\varphi(N))$.

---

The motivation is to diagonalize against the indices that are not powers of two:

If our enumeration of $B$ looks like:

• $f_0 : \color{red}0, \color{red}0, \color{red}0, \color{blue}1, \color{red}0, 1, 0, 1, \color{red}0, 1, 0, 0, 1, 1, 0, 1, \color{red}0, \cdots$
• $f_1 : \color{red}1, \color{red}1, \color{red}1, 1, \color{red}1, \color{blue}0, 1, 1, \color{red}1, 0, 0, 1, 0, 1, 0, 0, \color{red}1, \cdots$
• $f_2 : \color{red}1, \color{red}1, \color{red}1, 1, \color{red}1, 0, \color{blue}0, 1, \color{red}1, 0, 1, 0, 0, 0, 0, 1, \color{red}1, \cdots$
• $f_3 : \color{red}0, \color{red}0, \color{red}0, 1, \color{red}0, 0, 0, \color{blue}1, \color{red}0, 0, 0, 0, 0, 0, 0, 1, \color{red}0, \cdots$
• $f_4 : \color{red}0, \color{red}0, \color{red}0, 1, \color{red}0, 1, 0, 0, \color{red}0, \color{blue}0, 0, 1, 1, 1, 0, 1, \color{red}0, \cdots$
• $f_5 : \color{red}0, \color{red}0, \color{red}0, 1, \color{red}0, 0, 1, 0, \color{red}0, 1, \color{blue}0, 1, 0, 1, 0, 1, \color{red}0, \cdots$
• $f_6 : \color{red}1, \color{red}1, \color{red}1, 1, \color{red}1, 1, 1, 0, \color{red}1, 1, 1, \color{blue}0, 0, 1, 0, 1, \color{red}1, \cdots$
• $f_7 : \color{red}0, \color{red}0, \color{red}0, 1, \color{red}0, 1, 0, 1, \color{red}0, 1, 0, 1, \color{blue}1, 0, 1, 1, \color{red}0, \cdots$
• $f_8 : \color{red}0, \color{red}0, \color{red}0, 1, \color{red}0, 0, 0, 0, \color{red}0, 0, 1, 1, 0, \color{blue}0, 1, 1, \color{red}0, \cdots$
• $f_9 : \color{red}1, \color{red}1, \color{red}1, 1, \color{red}1, 1, 0, 1, \color{red}1, 1, 0, 1, 1, 0, \color{blue}1, 0, \color{red}1, \cdots$
• $f_{10} : \color{red}1, \color{red}1, \color{red}1, 1, \color{red}1, 1, 1, 0, \color{red}1, 1, 0, 1, 0, 0, 1, \color{blue}1, \color{red}1, \cdots$
• $\vdots$

Then our constructed function would be:

• $f : \color{red}0, \color{red}0, \color{red}0, \color{blue}0, \color{red}0, \color{blue}1, \color{blue}1, \color{blue}0, \color{red}0, \color{blue}1, \color{blue}1, \color{blue}1, \color{blue}0, \color{blue}1, \color{blue}0, \color{blue}0, \color{red}0, \cdots$

This would ensure that our constructed function differs from every function on the list in at least one place.