1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Uncountable sets

  1. Sep 6, 2009 #1
    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.
  2. jcsd
  3. Sep 7, 2009 #2


    User Avatar
    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...
  4. Sep 7, 2009 #3


    User Avatar
    Science Advisor

    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?
  5. Sep 7, 2009 #4
    Not really sure how to do that.

    Can you please help me out?
  6. Sep 7, 2009 #5
    Are you familiar with Cantor's argument to show the reals are uncountable?
  7. Sep 7, 2009 #6
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook