An Uncountable SetDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/