Chapter 5 Infinite Sets104
Lemma 5.2.3. LetAbe a set andb...A. IfAis infinite, then there is a bijection
fromA[fbgtoA.Proof.Here’s how to define the bijection: 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 toa 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 the way, we conclude that there is an infinite
sequencea 0 ;a 1 ;a 2 ;:::;an;:::of different elements ofA. Now we can define a
bijectionf WA[fbg!A:f.b/WWDa 0 ;
f.an/WWDanC 1 forn 2 N;
f.a/WWDa fora 2 A fa 0 ;a 1 ;:::g:(b)Use the proof of Lemma 5.2.3 to show that ifAis an infinite set, thenAsurjN,
that is, every infinite set is “as big as” the set of nonnegative integers.
Problem 5.4.
LetRWA!Bbe a binary relation. Use an arrow counting argument to prove the
following generalization of the Mapping Rule 1.
Lemma.IfRis a function, andXA, then
jXjjR.X/j:Problem 5.5.
The rational numbers fill the space between integers, so a first thought is that there
must be more of them than the integers, but it’s not true. In this problem you’ll
show that there are the same number of positive rationals as positive integers. That
is, the positive rationals are countable.
(a)Define a bijection between the set,ZC, of positive integers, and the set,.ZC