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: Cardinality of the set of all functions from N to N

  1. Mar 14, 2012 #1
    1. The problem statement, all variables and given/known data
    Let NN be the set of all functions from N to N. Prove that |NN|=c

    2. Relevant equations

    3. The attempt at a solution

    I can prove that the set of all functions from N to {0,1} has cardinality of the continuum, but i can't generalise it. Any help would be appreciated.
  2. jcsd
  3. Mar 14, 2012 #2


    User Avatar
    Science Advisor

    Let f be a function from N to N. Construct a number, x, by writing a decimal point, then 0.f(1)f(2)f(3)... so that each function is mapped to the number, between 0 and 1, having the values of f as digits. That maps each function to a number. What numbers?
  4. Mar 14, 2012 #3
    Thanks, I had thought of your argument when I was trying to prove |P(N)|=c but it didn't work out...I can't believe that it works for this question lol. Anyway thanks for your help.
  5. Mar 14, 2012 #4
    Is the map injective? Because I could have f(2n-1)=12,f(2n)=3 or f(2n-1)=1,f(2n)=23 and both of these functions would give me 0.123123...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook