Equinumerosity of infinite sets

Question

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?

Answer 1

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).

Answer 2

Yes: to say that sets $A$ and $B$ have the same cardinality (informally, the same ‘number of elements’) is by definition to say that there is a bijection between $A$ and $B$. For infinite sets it will in general be the case that if there is a bijection between $A$ and $B$, then there are also injections from $A$ to $B$ and from $B$ to $A$ that are not surjections. (This will always be the case if one assumes the axiom of choice; without that assumption there can be infinite sets for which it’s not the case.) In particular, it is always true that if $A$ and $B$ are countably infinite sets, then not only is there (by definition) a bijection between them, but there are also injections $f:A\to B$ and $g:B\to A$ such that $B\setminus f[A]$ and $A\setminus g[B]$ are both infinite.

Answer 3

Note also that there is a non-bijective injection from N to E: 1 -> 4, 2 -> 8, 3 -> 12, and so on. All of N is used up, but half of E is left.

Bijections are the ways that equinumerosity is defined, so without proposing a definition for a different sort of equinumerosity the question cannot be addressed.