Uncountable Sets: Proving N to N Bijections Are Uncountable

[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 f_i(2i)=2i
2i , if f_i(2i)not equal to =2i }Not very sure what I'm going to do.

Please help me.

 

[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...

 

[HallsofIvy]

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?

 

[sha sam]

Not really sure how to do that.

Can you please help me out?

 

[VeeEight]

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

 

[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.