Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Yes or No? Injection into the Naturals finite?

  1. May 5, 2012 #1
    For any set S, the natural numbers N and function f, if f : S → N is injective but not surjective, is S finite?
  2. jcsd
  3. May 5, 2012 #2


  4. May 5, 2012 #3
    Sorry, I'm not sure what that tells me. I have VERY little mathematics training, but ended up taking a math-logic course heavy on notation and dependent on higher-math knowledge.

    It seems to me what you are saying, though I am probably dead wrong, is that the set of odd naturals is in a bijection with the naturals. And thus, they have the same cardinality. But, I'm asking about a case in which S is not surjective.
  5. May 5, 2012 #4
    You map each odd number in the set of odd numbers, to the same number in the set of natural numbers. So 1 goes to 1, 3 goes to 3, 5 goes to 5, etc.

    This is an injection, right?

    But it's not a surjection, because (for example) 6 doesn't get hit.

    So this is an example of an injection into N that's not a surjection, but the domain is not finite.
  6. May 6, 2012 #5
    Wow. I see where I went wrong. What I meant to ask, while trying to get the notation down, was: if you have a set A that doesn't have a bijection with a set S such that |S| = |N|, then is A finite? It seems to me it would be (by definition, really).
  7. May 6, 2012 #6
    *A doesn't have a bijection with S because f : A → S is not surjective, while it is injective.
  8. May 6, 2012 #7

    No. S could be, say the set of all real numbers, which cannot mapped bijectively with the naturals...

    And "by definition" of what?

  9. May 6, 2012 #8
    I was referring to the following definition: for a set S and the set of naturals N, if |S| < |N|, then is S finite. I see where I went wrong. I am just trying to define a finite set using the terms "bijection," "surjection," and "injection."

    Might this be right: if for every mapping f between S and N, f : S → N is not surjective, then S is finite.
  10. May 6, 2012 #9

    I guess that could work, but why do you seem to enjoy making things messy? Go to the following definition:

    "A set S is finite iff EVERY proper subset of S has a cardinality strictly smaller than that of S".


  11. May 6, 2012 #10
    Haha...I'm just trying to make connections. This "mess" has helped me understand the definition of cardinality better: sets A, B have the same cardinality iff a bijection exists between A, B. I had no previous knowledge of bijection, injection, and surjection, so I was just trying to get to know the terms. I appreciate the patience.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook