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

Correspodance between infinite sets

  1. Jan 5, 2010 #1
    Take the set of positive integers plus 0 and the subset of all positive integers ending in, say 5. I see no reason why there can't be a one to one correspondence between the subset and the set. Am I wrong? (I have been challenged on this assertion.)

    EDIT: The challenge was: The subset is a proper subset and a proper subset cannot have a one to one mapping to its set. I agree this would be true for finite sets.
     
    Last edited: Jan 5, 2010
  2. jcsd
  3. Jan 5, 2010 #2
    Re: Correspondance between infinite sets

    The set of natural numbers ending in 5 is an infinite subset of the multiples of 5, and has the same cardinality as [tex]\mathbb N[/tex], so the only difficulty is the practical one of explicitly constructing the said bijection.

    There's nothing wrong with a bijection from [tex]\mathbb N[/tex] to one of its infinite subsets, because they have the same cardinality (simpler bijections than yours are, for example, [tex]n\rightarrow n+1[/tex] or [tex]n\rightarrow 2n)[/tex]).

    On the other hand, it's impossible to have a bijection between [tex]\mathbb N[/tex] and one of its finite subsets.

    Edit: just saw your edit, and it's correct; if the sets have the same cardinality, there is always a bijection (in fact, this is part of the definition of cardinality), and proper subsets of infinite sets can be infinite and have the same cardinality of the superset.
     
  4. Jan 5, 2010 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    You're right. This shows that the set of positive integers plus 0 is Dedekind-infinite.
     
    Last edited: Jan 5, 2010
  5. Jan 5, 2010 #4
    Thanks GR and JSuarez. My challenger asserted that by definition a proper subset cannot include all members of its set, deduced that a bijection was impossible and that this must apply to all sets. Therefore, there could not be a bijection in the case I described. I knew he was wrong but I was thinking that perhaps the term "proper subset" does to not apply to infinite sets.

    However I looked up the definition of "Dedekind-infinite" and saw it contains the term "proper subset" so I could see how this might lead to some confusion if one doesn't distinguish between finite and infinite sets.
     
  6. Jan 5, 2010 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, he was wrong.

    No, it certainly applies. But for infinite sets it is usual for their to be a bijection between the set and a proper subset. In fact, if we assume AC (a technical axiom assumed by most mathematicians), all infinite sets have a bijection between the set itself and some proper subset of the set.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Correspodance between infinite sets
  1. Infinite sets? (Replies: 2)

Loading...