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: Countably infinite set: odd integers

  1. Feb 25, 2012 #1
    1. The problem statement, all variables and given/known data
    Using the definitions, prove that the set of odd integers is countably infinite.


    2. Relevant equations
    Definition: The set A is countably infinite if its elements can be put in a 1-1 correspondence with the set of positive integers.


    3. The attempt at a solution
    I am trying to think of a function that maps the positive integers into the odd integers.

    The function I am coming up with is piecewise defined.
    I am unsure how to type it, but...
    f(n) =
    n-2 when n is odd and n>2
    -n-1 when n is even
    -n when n=1

    Testing some values, I got this
    f(1)=-1
    f(2)=-3
    f(3)=1
    f(4)=-5
    f(5)=3

    It looks like this works, but I am unsure how to show a piecewise defined function is 1-1 and onto. I think I am missing something.
     
  2. jcsd
  3. Feb 25, 2012 #2
    You're fine. Actually, you can define the same function in two pieces: n - 2 for odd n and -n - 1 for even n. Furthermore, n for odd n and -n + 1 for even n works as well.

    Same way you should show 1-1 and onto for any other function. Show f(n) = f(m) implies n = m. Then show for every odd integer i, there is a natural number n such that f(n) = i.
     
  4. Feb 25, 2012 #3
    Thank you for the response!

    Running with your suggestion, showing onto is simply stating that:

    Let m be an element of the odd integers.

    If n is odd, since the sum of an odd and even is odd, then n+(-2)=m for all odd n in the positive integers.

    If n is even, since an odd number is defined by 2x-1 for all x in Z, where n=2x, then -n-1=m for all even n in the positive integers.

    Is this a satisfactory proof of why f(n) is onto?
     
  5. Feb 25, 2012 #4
    I'm not convinced. It doesn't say why m must equal f(n) for some n, but just that it could.

    Consider using n for odd n and -n + 1 for even n as your f. It will lead to a simpler proof.

    A strategy for examining piecewise functions can be to look at the pieces of the domain where the function is defined separately. For odd n, where does f map n? What about for even n? Is m guaranteed to achieve either of these types of values, and if so, why?
     
  6. Feb 26, 2012 #5
    How is this:
    Let m be an element in the set of odd integers.

    If n is even, then there is a m such that f(n)=m.

    Since m is an odd integer, then there exists an element -m+1=n.

    Then f(-m+1)=-(-m+1)+1=m

    If n is odd, then m=n for all odd n in the set of positive integers.
     
  7. Feb 26, 2012 #6
    Yep you showed that f is onto correctly.

    Can you show that f is 1-1, or that f(m)=f(n) implies m=n?
     
  8. Feb 26, 2012 #7
    I think so.

    Assume f(m)=f(n)

    If n is even, then
    -n+1=-m+1
    -n=-m
    n=m

    If n is odd, then
    n=m
     
  9. Feb 26, 2012 #8
    How do you know that m is even when n is even? Likewise, how do you know m is odd when n is odd?
     
  10. Feb 26, 2012 #9
    I am still assuming that f(n) is piecewise defined. When n is even, f(n)=-n+1 and when n is odd, then f(n)=n

    Showing that f(n)=f(m) for both functions is not enough?
     
  11. Feb 26, 2012 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Your function will work just fine, but it's a little complicated.

    Consider a function, g(k), going from the odd integers to the positive integers.

    You already have f(n) = -n, for n=1, i.e. f(1) = -1. So g(-1)=1, i.e. g(k)=-k, when k=-1. Why not define g(k) = -k for all the negative odd integers. Where would you then map the positive odd integers?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook