# Equinumerosity of infinite sets

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:

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?

-
What do you mean by "the same number of elements" if not "there is a bijection"? –  Zev Chonoles Jul 10 '13 at 4:33
"For infinite sets, does the existence of a bijection mean they have the same number of elements?" That is usually the definition. –  Pedro Tamaroff Jul 10 '13 at 4:34
Answer of your first question is no. Equinumerosity is defined by existence of bijective function, and we find bijection from N to E (namely $n\mapsto 2n$). –  tetori Jul 10 '13 at 4:36
See Cardinality –  Aang Jul 10 '13 at 4:39

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

-
Thank you. As mentioned above, someone has said that the possibility of bijection is not enough to declare that two sets have the same number of elements - since they can have by some arrangement non-surjective injection they do not "necessarily" have the same number of elements. You settle this in saying that one must show that there is no bijection. –  morosoph Jul 10 '13 at 5:02

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.

-
Someone that I have been discussing this with says that cardinality does not mean "number of elements" (at least not for infinite sets). They say that the possibility of bijection is not enough to declare that two sets have the same number of elements - As in the examples given, infinite sets, while they can have bijection, they can have by some arrangement non-surjective injection, and therefore, 2 infinite sets do not "necessarily" have the same number of elements. So then, the mere possibility of a bijection between them shows that they have the same number of elements? –  morosoph Jul 10 '13 at 4:51
@morosoph: One doesn’t normally talk about the number of elements of an infinite set: one talks about the cardinality of the set, and ‘$A$ and $B$ have the same cardinality’ means by definition that there is a bijection between $A$ and $B$. I have no idea what this other person means by the number of elements of an infinite set: as I said, it’s not standard terminology when you’re talking about infinite sets. –  Brian M. Scott Jul 10 '13 at 5:02
That is part of the issue, since it is not correct terminology to talk about the number of elements for infinite sets, can it be said that 2 infinite sets are equinumerous (have the same number of elements) or not? And is the existence of a bijection sufficient to show that they are equinumerous? Since cardinality, to this person, means "existence of bijection", and not "number of elements", to say that they have the same cardinality does not mean they have the same number of elements. Confusing. –  morosoph Jul 10 '13 at 5:11
@morosoph: Unlike have the same number of elements, the expressions are equinumerous and are equipollent are occasionally used, though I consider them both a bit old-fashioned. They are exactly synonymous with have the same cardinality, however: all mean that there is a bijection between the two sets. This person is simply wrong. –  Brian M. Scott Jul 10 '13 at 5:21

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.

-