# Uncountable sets

1. Sep 6, 2009

### sha sam

1. The problem statement

Need to prove that the set of bijections from N to N is uncountable.

2. The attempt at a solution

I'm not really sure how to proceed here but what I did so far is this....

f(2i) = { 2i+1, if fi(2i)=2i
2i , if fi(2i)not equal to =2i }

Not very sure what I'm going to do.

2. Sep 7, 2009

### lanedance

you could try to start by representing each biejction as an infinite sequence of un-repeating integers (similar to a permutation)

The problem then becomes showing the uncountability of the set of infinite sequences...

if you have been shown the uncountabilty of the reals, you may be able to use a similar argument...

3. Sep 7, 2009

### HallsofIvy

Staff Emeritus
For each bijection, you can construct a real number by .0.f(1)f(2)f(3)... . Can you show that that set of real numbers is uncountable?

4. Sep 7, 2009

### sha sam

Not really sure how to do that.

5. Sep 7, 2009

### VeeEight

Are you familiar with Cantor's argument to show the reals are uncountable?

6. Sep 7, 2009

### sha sam

Is this proof on real numbers correct? Then how do I proceed from here to show the bijection from N to N is uncountable?

Let A be a set of Real numbers between numbers 0 and 1.

Suppose x0, x1, x2, ... is any sequence of elements of A, there is an element xεA that is not in the sequence for every i>=0 and x≠xi .

X0 -> 0.x0,0 x0,1 x0,2 …
X1 -> 0.x1,0 x1,1 x1,2 …
|
|
|

Assume the element not in A is X -> 0.x0 x1 x2…

Then xi=xi,i and the sequence of x0 x1 x2 doesnot end with .99999…….
The xi= 1 if xi,i≠1 and xi= 0 if xi,i=1

As the real numbers between 0 and 1 are uncountable and it’s a subset of the total real numbers, the set of real numbers are uncountable.