Uncountable sets

  • Thread starter sha sam
  • Start date
  • #1
3
0
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.

Please help me.
 

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
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
HallsofIvy
Science Advisor
Homework Helper
41,833
956
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
3
0
Not really sure how to do that.

Can you please help me out?
 
  • #5
614
0
Are you familiar with Cantor's argument to show the reals are uncountable?
 
  • #6
3
0
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.
 

Related Threads on Uncountable sets

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
12
Views
9K
Replies
1
Views
2K
  • Last Post
Replies
4
Views
4K
Replies
5
Views
2K
Replies
1
Views
912
Replies
3
Views
3K
Top