1. Not finding help here? Sign up for a free 30min 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!

Infinite sets onto and one-to-one

  1. Apr 6, 2008 #1
    1. The problem statement, all variables and given/known data
    N is the set of natural numbers, Z is the set of all integers
    Construct a function a : N -> Z that is both one to one and onto.
    Construct a function b : Z -> N that is one to one but not onto.

    3. The attempt at a solution
    The only attempts have been very wrong - not even sure where to start since in both cases it doesn't seem that a solution is possible.
     
  2. jcsd
  3. Apr 6, 2008 #2
    If your friend from Mars who doesn't know our strange number system, were to ask you to list all integers, so that she can see what kind of numbers we use on Earth.

    Maybe you would start with zero because it lies somewhere in the middle, then you might go on to tell her about 1 and -1 because they are pretty nearby and often used...how could you continue?

    When you've told her about ALL integers you will have found a function N-->Z. Do you see why this is one-to-one and onto?
     
  4. Apr 6, 2008 #3
    I'm sorry I am having problems understanding how we have found a function once we have told her about all integers. Maybe I've been looking at the problem wrong for so long I'm not picking up the obvious...
     
  5. Apr 6, 2008 #4
    We're looking for a function f: N-->Z. this means for each natural number n, f(n) must give an integer. f being one-to-one means, two different natural numbers give you different integers

    [tex]
    m\neq n \Rightarrow f(n)\neq f(m)
    [/tex]

    f being "onto" means for each integer z you have some natural number n such that f(n)=z.

    So let's define the function by

    f(n) = the n.th integer you told you friend about.

    :smile:

    What would be f(1), f(2), f(3), f(4), f(5) ...?
     
  6. Apr 6, 2008 #5
    How can the function be onto? There are not enough natural numbers for there to be a unique solution for all f(n) = z
     
  7. Apr 6, 2008 #6
    well this is a very good point. there are infintely many natural numbers and there are also infinetly many integers. I agree that intuitively it seems that there should be twice as many integers as natural numbers. This is not the case. The very fact there indeed IS a function N-->Z which is "onto" shows that you can count the integers, hence the name countable set.

    Are you familar with the term "countable"?

    Do you agree that the function f as I defined it, is onto? What are the first few values of this function f?
     
  8. Apr 6, 2008 #7
    As you have defined it f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 2, f(5) = -2, etc etc.
    Is this correct?

    Edit: I know I must seem dense, thank you for your help
     
    Last edited: Apr 6, 2008
  9. Apr 6, 2008 #8
    This is indeed one - and most likely the most common - way to define a function f:N-->Z

    Now it would be good to write down a general formula for this function because "etc" doesn't look good:smile:.
    And you should convnce yourself that it is onto.
    That means somebody picks an integer, say 3456, will there be a natural number n such that f(n)=3456?
     
  10. Apr 6, 2008 #9
    Now things make sense and I do see why this function is onto.

    So then f(n) = ceiling(-n/2) when n is odd, and f(n) = (n/2) when n is even.
     
  11. Apr 7, 2008 #10
    Any help on "Construct a function b : Z -> N that is one to one but not onto."?
     
  12. Apr 7, 2008 #11

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Take any subclass of N, like the even natural numbers for instance. Can you split this into two subclasses? Say, the ones that are divisible by 4, and the ones that aren't...
     
  13. Apr 7, 2008 #12
    I'm waaay too tired tonight. Can you be a little more specific?
     
  14. Apr 7, 2008 #13

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    The most natural one-to-one function that maps Z into N is the one that sends the positive integers to the positive even natural numbers, the negative integers to the odd natural numbers, and 0 to 0. The problem is, this map is also onto. So my post was hinting at the idea of mapping Z to a suitable proper subset of N, one in which we can do something like the even-odd map again.
     
  15. Apr 15, 2008 #14
    Sorry it took a while to get back. Thanks a lot for your help, I solved the problems.
     
  16. Apr 30, 2008 #15
    I ended up getting this problem wrong and I was hoping you could give me another hint on: mapping Z to a suitable proper subset of N, one in which we can do something like the even-odd map again?

    My teacher won't help me find the answer and I will probably need to understand this for the final.
     
  17. Apr 30, 2008 #16
    What was your answer? Make sure that in addition to being not onto, your function is one-to-one. To show that a function f is one-to-one, you can show that either

    [tex]m\neq n \Rightarrow f(n)\neq f(m) \quad \text{ or } \quad f(m) = f(n) \Rightarrow m = n[/tex]

    Pere mentioned the first option above.
     
  18. Apr 30, 2008 #17
    My post was in response to morphism's post.
    ==================
    The most natural one-to-one function that maps Z into N is the one that sends the positive integers to the positive even natural numbers, the negative integers to the odd natural numbers, and 0 to 0. The problem is, this map is also onto. So my post was hinting at the idea of mapping Z to a suitable proper subset of N, one in which we can do something like the even-odd map again.
    ==================

    I'm not sure how to map Z to a proper subset of N that does something like the even-odd map again.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?