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