(Sudkamp, exercise 18, p.34).

Show that there are uncountable number of functions from N to {0,1}

Proof.

Assume the set F of total functions from N to {0,1} is countable, and that f_1, f_2, ..., f_n, ... is an
enumeration of the sets in F.

Construct a table T with columns formed by the
enumeration of elements of N and whose rows are formed by elements of
the enumeration of F such that the ith row is labeled with f_i.
The table value T[f_i][n] is the value f_i(n), i.e., the result of applying f_i to n.

Now, consider the diagonal of this table, i.e., T[f_0][0], T[f_1][1], T[f_2][2], and so on.

Define the function f_diag as follows: f_diag(i) = f_i(i).

Clearly, f_diag is a total function from natural numbers to {0,1}.

Now define f_diag' as follows:
f_diag'[i] = 1 - f_diag[i].

f_diag' is in F (i.e., it is a total function from N to {0,1}) because f_diag is.

Hence, f_diag' must appear as a row in T, say at row r.
Hence, f_diag' = f_r. But this can't be, since f_diag'[r] = 1 - f_diag[r] is not the same as f_r[r] = f_diag[r].

Indeed, for no row in T is it the case that f_diag' is the function labeled in that row.

Hence, f_diag' is nowhere in the enumeration of elements of F, and hence no such enumeration
is possible.