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,
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search