Chapter 5 Infinite Sets92
pretty technical. Just because there is a surjective functionf WA!B—which
need not be a bijection —and a surjective functiongWB!A—which also need
not be a bijection —it’s not at all clear that there must be a bijectioneWA!B.
The idea is to constructefrom parts of bothf andg. We’ll leave the actual
construction to Problem 5.6.
5.2.1 Infinity is different
A basic property of finite sets that doesnotcarry over to infinite sets is that adding
something new makes a set bigger. That is, ifAis a finite set andb ...A, then
jA[fbgj D jAjC 1 , and soAandA[fbgare not the same size. But ifAis
infinite, then these two setsarethe same size!
Lemma 5.2.3.LetAbe a set andb...A. ThenAis infinite iffAbijA[fbg.
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 be equal to
a 0 ; call this new elementa 1. But sinceAis infinite, it has at least three elements,
one of which must not equala 0 ora 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:5.2.2 Countable Sets
A set,C, iscountableiff its elements can be listed in order, that is, the distinct
elements isCare precisely
c 0 ;c 1 ;:::;cn;::::This means that if we defined a function,f, on the nonnegative integers by the rule
thatf.i/WWDci, thenf would be a bijection fromNtoC. More formally,
Definition 5.2.4.A set,C, iscountably infiniteiffNbijC. A set iscountableiff
it is finite or countably infinite.