Correspodance between infinite sets

[SW VandeCarr]

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.

 

[JSuarez]

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.

 

[CRGreathouse]

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?

You're right. This shows that the set of positive integers plus 0 is Dedekind-infinite.

 

[SW VandeCarr]

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.

 

[CRGreathouse]

I knew he was wrong

Yes, he was wrong.

I was thinking that perhaps the term "proper subset" does to not apply to infinite sets.

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.