Show that $| \mathbb N_0 | < | \{ 0,1\}^{\mathbb N_0} |$ Show that $| \mathbb N_0 | < | \{ 0,1\}^{\mathbb N_0} |$ where ${{{\{ 0,1\} }^{{\mathbb{N}_0}}}}$ is the set of all functions $f:{\mathbb{N}_0} \to \{ 0,1\} $ in the following way:
a) Construct an injection: ${\mathbb{N}_0} \to {{{\{ 0,1\} }^{{\mathbb{N}_0}}}}$.
b) Show that there is no surjection $h:{\mathbb{N}_0} \to {{{\{ 0,1\} }^{{\mathbb{N}_0}}}}$.
My attempt:
For part a) it is obvious that there are many of such functions $f:{\mathbb{N}_0} \to \{ 0,1\}$. In fact all such functions should satisfy $f(a) = 0,\,\,f(b) = 1,\,\,a \ne b$. I'm trying to understand, if i want to demonstate one of such functions should it be so that $\mathbb{N}_0$ must contain only two distinct elements that map into $\{ 0,1\} $? Otherwise if $\mathbb{N}_0$ has more than $2$ elements and $\{ 0,1\} $ has only $2$ elements by Dirichlet principles we will have at least $2$ pre-images with the same image and the function will be no more injective. So what is exactly meant by "construct an injection"? If there are many injections we cannot construct them all right?
I know that part b) should be done using a proof by contradiction, but i don't have any ideas at the moment...
 A: It's not an injection into $\{0,1\}$ that you are asked to construct; it's an injection into $\{0,1\}^{\mathbb N_0}$.  For example: \begin{align} 0 & \mapsto (1,0,0,0,0,\ldots) \\ 1 & \mapsto (0,1,0,0,0,\ldots) \\ 2 & \mapsto (0,0,1,0,0,\ldots) \\ & {}\ \ \vdots \end{align} That is an injection.  However, I don't think the "construct an injection" step is worth much here.  Merely proving that the one injection you've constructed fails to be a surjection won't do it.  You need to show that ALL injections, not just one, fail to be surjections.
This problem is more than just an excercise unless you've already seen similar proofs. Here is one standard way to show that every mapping $f$ from $\mathbb N_0$ into $\{0,1\}^{\mathbb N_0}$ fails to be surjective:
Let $y \in \{0,1\}^{\mathbb N_0}$ be defined by $y_n= 1 - (f(n))_n$.
Then $y_0 = 1 - (f(0))_0 \ne (f(0))_0$, so $y\ne f(0)$.
And $y_1 = 1 - (f(1))_1 \ne (f(1))_1$, so $y\ne f(1)$.
And $y_2 = 1 - (f(2))_2 \ne (f(2))_2$, so $y\ne f(2)$.
And $y_3 = 1 - (f(3))_3 \ne (f(3))_3$, so $y\ne f(3)$.
And so on.
So $y \in \{0,1\}^{\mathbb N_0}$ differs from $f(0), f(1), f(2), \ldots\,{}$.  Thus $f$ is not surjective.
