uncountable diagnol argument

• Oct 26th 2008, 06:03 AM
Louise
uncountable diagnol argument
I need to prove that there are uncountably many functions from N to N using a diagonal argument.

I begin by saying, suppose there are countably many function from N to N.
Therefore they can be listed....

However i'm not sure how to build a function which leads to a contradiction.

Help would be greatly appreciated. Thanks.
• Oct 26th 2008, 09:16 AM
Plato
Make a countable list of all functions $\left\{ {f_1 ,f_2 , \cdots f_n , \cdots } \right\}\,,\,\left( {\forall n} \right)\left[ {f_n :N \mapsto N} \right]$.
Define a function $\left[ {g:N \mapsto N} \right]$ by $g(n) = \left\{ {\begin{array}{rl} {2,} & {f_n (n) = 1} \\ {1,} & {f_n (n) \ne 1} \\
\end{array} } \right.$
.
But $\left( {\exists K} \right)\left[ {g = f_K } \right]$.
Is that possible?