7.1. Infinite Cardinality 209
Proof. SinceAisnotthe same size asA[fbgwhenAis finite, we only have to
show thatA[fbgisthe same size asAwhenAis infinite.
That is, we have to find a bijection betweenA[fbgandAwhenAis infinite.
Here’s how: sinceAis infinite, it certainly has at least one element; call ita 0. But
sinceAis infinite, it has at least two elements, and one of them must not equal to
a 0 ; call this new elementa 1. But sinceAis infinite, it has at least three elements,
one of which must not equal botha 0 anda 1 ; call this new elementa 2. Continuing
in this way, we conclude that there is an infinite sequencea 0 ;a 1 ;a 2 ;:::;an;:::of
different elements ofA. Now it’s easy to define a bijectioneWA[fbg!A:
e.b/WWDa 0 ;
e.an/WWDanC 1 forn 2 N;
e.a/WWDa fora 2 A fb;a 0 ;a 1 ;:::g:7.1.2 Countable Sets
A set,C, iscountableiff its elements can be listed in order, that is, the elements in
Care precisely the elements in the sequence
c 0 ;c 1 ;:::;cn;::::Assuming no repeats in the list, saying thatCcan be listed in this way is formally
the same as saying that the function,f WN!Cdefined by the rule thatf.i/WWDci,
is a bijection.
Definition 7.1.8.A set,C, iscountably infiniteiffNbijC. A set iscountableiff
it is finite or countably infinite.
We can also make an infinite list using just a finite set of elements if we allow
repeats. For example, we can list the elements in the three-element setf2;4;6gas
2;4;6;6;6;::::This simple observation leads to an alternative characterization of countable sets
that does not make separate cases of finite and infinite sets. Namely, a setC is
countable iff there is a list
c 0 ;c 1 ;:::;cn;:::
of the elements ofC, possibly with repeats.
Lemma 7.1.9.A set,C, is countable iffNsurjC. In fact, a nonempty setC is
countable iff there is atotalsurjective functiongWN!C.