An Uncountable Set

Date: 09/28/98 at 09:48:51
From: Claudia Celenti
Subject: Uncountable sets

I have to prove using diagonalization that the set of functions from N 
to N is uncountable, but I'm not familiar enough with this proof.

If you have a chance, please help me to put this issue to rest.

Best regards,
Claudia

Date: 10/06/98 at 02:24:49
From: Doctor Jaime
Subject: Re: Uncountable sets

Hello Claudia,

Let the set of functions f: N -> N be F. To show that the set F is 
uncountable you have to show that, being infinite, it cannot be put in 
a 1-1 correspondence with the set N.

The proof is made by contradiction, that is, we suppose that there is 
a 1-1 correspondence between N and F and we arrive at a contradiction, 
thus proving that there is no such correspondence.

Let's suppose then that we have a 1-1 correspondence between N and F:

   (*)
   1 -> f1
   2 -> f2
   3 -> f3
   ...

If the correspondence is 1-1 for every f in F there must be some n in 
N such that:

   n -> fn = f

To arrive at a contradiction we have just to build a certain f in F 
that cannot be an fn. How? Here we arrive at the key of the 
diagonalization process. Since f is a function from N to N, we know:

   1 -> f(1)
   2 -> f(2)
   3 -> f(3)
   ...

What we want is to make sure that we are able to choose such an f that 
is different from all the list of functions above in (*) namely:

   f1, f2, f3, ..., fn,...

How is it done? Well we choose f(1) such that it is different from 
f1(1) and so the functions f and f1 are different (because they differ 
on at least one point of their domain). We now choose f(2) such that 
it is different from f2(2) and so the functions f and f2 are different. 
We do the same for f3, f4, ..., fn,... all the fn. So f is built such 
that it is different from all fn. This means that the correspondence 
(*) cannot be 1-1. 

Is it clear? Can you see why it is called diagonalization?

If something is not clear to you, feel free to write us back.

- Doctor Jaime, The Math Forum
  http://mathforum.org/dr.math/