# Uncountable sets

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.

Related Calculus and Beyond Homework Help News on Phys.org
lanedance
Homework Helper
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
Homework Helper
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?

Not really sure how to do that.

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

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.