Show that the function $f: \mathbb{N}\to \{0,1\}^\mathbb{N}$ is not surjective I am having trouble showing that the function $f: \mathbb{N}\to \{0,1\}^\mathbb{N}$ is not surjective. I suppose that I have to show is that $\exists g\in \{0,1\}^\mathbb{N},\forall n\in\mathbb{N},g\neq g(n)$. However, I can't think of a way to show that $g\neq g(n)$. I know that I am supposed to use the Cantor's diagonal argument. Could you give me a hint towards the proof?
 A: Suppose that $f: \mathbb{N}\to \{0,1\}^\mathbb{N}$ is surjective, then $\{0,1\}^\mathbb{N}$ is countable: $\{0,1\}^\mathbb{N}=\{a_1,a_2,a_3,....\}$ and we can assume that $a_j \ne a_k$ for $j \ne k$.
Are you now in a position to use Cantor's diagonal argument to get a contradiction ?
A: The trick in the diagonal argument is to make sure $g$ is different from each of the $f(n)$s by constructing it such that $g(n)\ne (f(n))(n)$. Since this is the only constraint on $g(n)$ it is very easy to find a possible $g(n)$ that does not equal $f(n)(n)$ ...
A: Suppose $f: \mathbb{N} \to \{0,1\}^\mathbb{N}$ is a mapping.
On $\{0,1\}$ we have the operation of addition modulo $2$, so $0+0 = 1+1= 0$ and $0+1 = 1+0 = 1$, which makes it into a field, for convenience.
Define $h \in \{0,1\}^\mathbb{N}$ by $h(n) = F(n)(n)+1$. As $F$ is given, this is a well-defined function on $\mathbb{N}$ to $\{0,1\}$. 
Suppose there were some $m \in \mathbb{N}$ such that $F(m) = h$. This means that the two functions $F(m)$ and $h$ have the same values for all $n$, and in particular for $n=m$. But this would give: $F(m)(m) = h(m)$ while by definition $h(m) = F(m)(m)+1$. (!) This contradiction shows that no such $m$ can exist, so 
$h \notin F[\mathbb{N}]$ and $F$ is not surjective.
