The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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,

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   
Associated Topics:
College Analysis
High School Analysis

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.