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!

Proof about infinite subsets

  1. Jan 6, 2013 #1
    1. The problem statement, all variables and given/known data
    Let X be a set and let f be a one-to-one mapping of X into itself such that
    [itex] f[X] \subset X [/itex] Then X is infinite.
    3. The attempt at a solution
    Lets assume for the sake of contradiction that X is finite and there is an f such that it maps all of the elements of X to a proper subset of X called Y. And this function also preserves the 1-to-1 mapping. If Y is a proper subset then |Y|<|X| and if X is finite then
    Y is also finite, but there is a problem with the one to one mapping, if Y has less elements then X then there is no 1-to-1 mapping. So this is a contradiction of our original assumption therefore X is infinite.
     
  2. jcsd
  3. Jan 6, 2013 #2
    The reasoning is correct in general, but perhaps somewhat informal. Formally, you could recall that a one-to-one mapping of two sets implies that the two sets have equal cardinality. And for finite sets, cardinality is simply the number of their elements.
     
  4. Jan 6, 2013 #3
    I think you are thinking of mappings that are both one-to-one and onto. If the mapping is only one to one, then the cardinalities don't need to be equal -- there for example certainly is a one to one mapping from N to R, f(x) = x.
     
  5. Jan 6, 2013 #4
    No, what I mean is that the cardinality of the image of X (where f is onto) must be equal to that of X. Invoking the finiteness of X completes the proof.
     
  6. Jan 6, 2013 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "
    But nothing is said about f being "onto".
     
  7. Jan 6, 2013 #6
    Any map is "onto" its image.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook