[Math] Equinumerosity of infinite sets

elementary-set-theoryinfinity

Key issue: For infinite sets, does the existence of a bijection mean they have the same number of elements?

For example, does the set of natural numbers N = {1,2,3,4…} have the same number of elements as the set of positive even integers E = {2,4,6,8…}? There is a one-to-one correspondence between these sets:

1 -> 2
2 -> 4
3 -> 6
...

However, depending on how you look at it, there is also an injective function (one-to-one but not onto) between E and N:

  -> 1
2 -> 2
  -> 3
4 -> 4
  -> 5
6 -> 6
...

In this way, all of the elements in E are in N, but not all of the elements in N are in E. Does this "prove", in some way, that N and E are not equinumerous? If not, does this mean that while E is a proper subset of N, it still has the same number of members as N – something that is true for infinite sets but not true of finite sets?

A second example:

What about the following sets:

A: {a1,a2,a3,…}
B: {b1,b2,b3,…}

A has one-to-one correspondence (bijection) with B:

a1 -> b1
a2 -> b2
a3 -> b3
…

If this, bijection from A to B, shows that A and B have the same number of elements, what happens if we shift A up so that there is an injective function (one-to-one but not onto) between A and B, e.g.

?  -> b1
a1 -> b2
a2 -> b3
a3 -> b4
…

Does this show that A and B do not necessarily have the same number of elements, after all – despite having bijection between them in one arrangement – since we can arrange them in such a way that there is a one-to-one function, but not onto?

Best Answer

For infinite sets, we define equinumerous as there being a bijection. For finite sets, you cannot have both a bijection and a non-surjective injection, but as you have shown, that is possible for infinite sets. To prove there is a different number of elements for infinite sets, you have to show that there is no bijection, not just that there is a non-surjective injection (or non-injective sujection).

Related Question