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: 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

    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

    If n is odd, then
  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


    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