Cantor theorem use

Question

I decided to use Cantor's theorem to demonstrate by contradiction but I'm not entirely sure if what I did is correct (since I had a lot of trouble understanding it). Can you tell me if what I did is correct?

My answer is the following: "Assume it is possible to enumerate the set C (of increasing functions). If so, then it is possible to generate a matrix in which each row corresponds to a function (the set of values obtained from it) and each element on each line is a value obtained from the function on that line.

That matrix can be illustrated as follows: $$ \begin{matrix} 1 \\ 2 \\ 3 \\ \vdots \end{matrix} \begin{bmatrix} a_{00} & a_{01} & a_{02} & \dots\\ a_{10} & a_{11} & a_{12} & \dots\\ a_{20} & a_{21} & a_{22} & \dots\\ \vdots & \vdots & \vdots & \ddots\\ \end{bmatrix} $$ Assume each row on the matrix is placed in a way that the elements on the diagonal are always bigger than the previous element of the diagonal (this is, $a_{00}< a_{11},\ a_{11} < a_{22}$ and so on).\newline Assume we take each element of the diagonal of the matrix ($a_{00}, a_{11}, a_{22}$, etc), and that we add 1 to each of them. And then, we form a new strictly increasing function that contains all of these elements: $a_{00}+1,\ a_{11}+1,\ a_{22}+1, \dots$

Let's remember that we defined the set was enumerable. From that, then we should be able to find the new function on one of the rows os the matrix.

The problem is that, since we changed every element of the matrix (by adding 1 to each of them), then there's no row on the matrix that can possibly be the function just defined. And with thart, we meet a contradiction and further more, we can say that it is possible to find infinite rows that are not on the matrix. And, with that, it is demonstrated that the set C is not enumerable."

Thank you for your help!

Answer 1

You have shown that there is no enumeration with the given restriction on the diagonal. Unfortunately, you have said nothing about other enumerations.

This can be salvaged if you instead of the functions themselves, record the successive increases $f_n(x+1)-f_n(x)$ in each row. Then you can use the diagonal argument to show that there is some sequence of successive increases that isn't on the list, which represents a whole family of functions that aren't on the list (one for each possible function value at $0$).

Answer 2

Other direction

If you know that the set $S$ of maps from $\mathbb N$ into $\mathbb N$ is uncountable, it is easy to prove that $C$ is also uncountable as you can build an injection $\varphi$ from $S$ into $C$ by defining

$$\varphi(f)(n)=\begin{cases} f(1) & \text{ for } n = 1\\ f(n) + f(n-1) & \text{ for } n > 1\\ \end{cases}$$