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?
Show that the function $f: \mathbb{N}\to \{0,1\}^\mathbb{N}$ is not surjective
elementary-set-theory
Related Solutions
Diagonalization is a common method in mathematics. Essentially it means "write it in an infinite matrix and then walk along a coordinate line which approaches infinity on both axes".
The "Cantor diagonal argument" says write the numbers in a matrix, and take the $n$-th number's $n$-th digit, and change it.
The Cantor theorem is a form of diagonalization because what you actually do is write the function in matrix form:
$$\begin{array}{|c|c|c|c|c} &x_1 & x_2 & x_3 & \ldots\\ \hline f(x_1)\\ \hline f(x_2)\\ \hline f(x_3)\\ \hline \vdots \end{array}$$
Now we write $1$ into the blank cells if $x_i\in f(x_j)$, and $0$ otherwise. The proof takes the set of all $x\in X$ such that $x\notin f(x)$, That is walk along the diagonal and take the coordinates which give $0$. This defines a subset of $X$ which is not in the range of $f$, much like the diagonal argument gives a number which is not in the enumeration.
Similar, but different arguments are given when showing the real numbers can be defined as Cauchy sequences of rationals up to some equivalence, and that this is a complete space. We take a Cauchy sequence of Cauchy sequences and we take the $k$-th element of the $k$-th sequence.
Of course this is not exactly what we do, but it is close enough. We need to toy with $\epsilon-\delta$ and define the diagonal we are going to walk on (for the $k$-th element we want to take some $x^k_j$ for $j$ large enough so and so...)
Here is an idea for how to use the diagonalization method after all.
Suppose $f_n$ is a list of surjections. We define $g$ in the following way:
$$g(k)=\begin{cases}\frac k2 & k\text{ is even}\\1+\sum_{m\leq k}f_m(k) &\text{otherwise}\end{cases}$$
So $g$ is clearly surjective (its restriction to the even numbers is surjective). To see that $g$ is not one of the $f_n$'s, we need to show that whenever $n\in\Bbb N$ there is some $k$ such that $f_n(k)\neq g(k)$.
Let $n\in\Bbb N$, and let $k$ be any odd number such that $n\leq k$, then we have that $$f_n(k)\leq\sum_{m\leq k}f_m(k)<1+\sum_{m\leq k}f_m(k)=g(k).$$
Therefore $f_n(k)\neq g(k)$ so $f_n\neq g$, and so we have that $g$ is not on the list.
If you are willing to use something other than diagonalization then we can give the following argument:
For every infinite subset of $\Bbb N$, we can write the following surjection:
$$f_A(n) =|\{a\in A\mid a<n\}|$$
Then $f_A$ is surjective because $A$ is infinite, so for every $n$ we can find $k$ such that $f_A(n)=k$.
Note that if $A\neq B$ then $f_A\neq f_B$: if $n=\min A\triangle B$, and suppose that $n\in A$, then $f_A(n+1)>f_B(n+1)$.
Therefore there are at least $2^{\aleph_0}$ surjections. Moreover all of them are non-decreasing!
Best Answer
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)$ ...