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!

Help with function mapping

  1. Jul 5, 2009 #1
    Let B={s|s is a function mapping the set of natural numbers to {0,1}}. Is B a countable set-that is, is it possible to find a function [tex]\Phi[/tex]() mapping the set of natural numbers onto B-?


    I know that it has to do with infinite binary sequences, but the countability part confuses me. Can someone explain that and give me a first step to answering this?

    Thanks
     
  2. jcsd
  3. Jul 5, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Every mapping in B is an infinite binary sequence (sequences of 0 and 1), as you say, and so, if we put a "." in front of it, represents a real number, written in base 2, in the interval (0,1). But the set of real numbers in that interval is not countable.
     
  4. Jul 5, 2009 #3
    That's interesting. Does saying that putting a "." in front of the sequences written in base 2 is in the interval (0,1) mean anything? If the question was if B={s|s is a function mapping the set of natural numbers to {1,2}} putting a period in front of the sequences would make them less than 1 which would make them not in the interval (1,2), but the logic of them being real numbers and that real numbers aren't countable is still solid. Correct?
     
  5. Jul 5, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Halls is suggesting a shortcut. No, putting a 'dot' in front really doesn't prove anything unless you understand the shortcut. But you can always use the Cantor diagonal argument directly. I'd suggest you look that up and understand it, since it's fundamental to the proof that there are uncountable sets.
     
  6. Jul 6, 2009 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    My point is this: suppose one such sequence is "11001010010101100...". "Putting a '.' in front of it" means writing .11001010010101100..., a number between 0 and 1, written in binary. Further, any real number, between 0 and 1, is such a sequence so there is a one-to-one correspondence. Every such sequence corresponds to a number between 0 and 1.

    You ask about "if B={s|s is a function mapping the set of natural numbers to {1,2}} putting a period in front of the sequences would make them less than 1 which would make them not in the interval (1,2)". Why would you want it in (1, 2)? The notation {1, 2} means every value must be either 1 or 2 and does not have anything to do with the interval (1, 2). Frankly, if I were given the problem of showing that the set of all functions from the natural numbers to {1, 2} were uncountable, I would immediately observe that there is an obvious correspondence between {1, 2} and {0,1} and start talking about binary numerals again!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help with function mapping
  1. Mapping of functions (Replies: 15)

  2. Function and Mapping (Replies: 9)

  3. Mapping Functions (Replies: 6)

Loading...