§l. Set Theory
27
(3) The cartesian product X x Y of two countable sets X and Y is countable. We have essentially proved this in showing above that Q is countable:
one writes the ordered pairs of whole numbers (p, q) "diagonally":
(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ....
(4) The union of a finite or countable family of finite or countable sets is
finite or countable. Indeed, let (Xi)iEI be such a family, where I is finite or
countable like the Xi' For each i choose a surjective map Ii : N -----t Xi and
define a map f of the cartesian product N x I onto the union X of the Xi as
follows:
f((n,i)) = hen)
for n E N and i E I. For every x E X there exists an i E I such that x E Xi,
so an n E N such that x = fi (n). The map f is thus surjective, and since the
product N x I is countable, so is X finite or countable too.
(5) Every infinite set contains a countable set. If X is infinite there is a
bijection f from X onto a set Y c X distinct from X. Choose a E Y - X
and put
Xo = a, Xl = f(xo), X2 = f(Xl), ....
If one had xp = Xq for a pair of integers such that p < q, one could deduce
that Xp-l = Xq-l since f is injective, whence, continuing this argument,
Xo = x q_p = f(Xq-p-l), which is impossible since Xo i Y = f(X).
(6) Let X and D c X be two sets; suppose D that is countable and X - D
is infinite; then X and X - D are equipotent. From the preceding result,
X - D contains a countable set D' and one has
X = Y U (D U D'), X - D = Y U D'
where Y = X -(DUD') is disjoint from D and D'. It is not hard to construct
a bijection 9 of Y onto itself; since D and D' are countable, so is DUD'; thus
there is also a bijection h of DUD' onto D'. Then one obtains a bijection
f of X onto X - D by putting f(x) = g(x) [for example f(x) = x] for all
x E Y and f(x) = hex) for all xED U D'; f is clearly injective and
f(X) = flY U (D U D')] = fey) U feD U D') = Y U D' = X-D.
(7) The set of finite subsets of a countable set X is countable. From point
(4) above it is enough to show that, for a given n, the n-element subsets
of a countable set X form a countable subset Pn of P(X). Now consider
the cartesian product xn, the set of systems (Xl. ... ,xn ) of elements of X,
and the map f : xn -----t P(X) which transforms (Xl. ... , xn) into the set
{x!, ... , Xn} eX. Its image clearly contains Pn; and it is countable since xn
is, by (2) and (3); thus Pn is too, since Pn is clearly not finite.
27
(3) The cartesian product X x Y of two countable sets X and Y is countable. We have essentially proved this in showing above that Q is countable:
one writes the ordered pairs of whole numbers (p, q) "diagonally":
(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ....
(4) The union of a finite or countable family of finite or countable sets is
finite or countable. Indeed, let (Xi)iEI be such a family, where I is finite or
countable like the Xi' For each i choose a surjective map Ii : N -----t Xi and
define a map f of the cartesian product N x I onto the union X of the Xi as
follows:
f((n,i)) = hen)
for n E N and i E I. For every x E X there exists an i E I such that x E Xi,
so an n E N such that x = fi (n). The map f is thus surjective, and since the
product N x I is countable, so is X finite or countable too.
(5) Every infinite set contains a countable set. If X is infinite there is a
bijection f from X onto a set Y c X distinct from X. Choose a E Y - X
and put
Xo = a, Xl = f(xo), X2 = f(Xl), ....
If one had xp = Xq for a pair of integers such that p < q, one could deduce
that Xp-l = Xq-l since f is injective, whence, continuing this argument,
Xo = x q_p = f(Xq-p-l), which is impossible since Xo i Y = f(X).
(6) Let X and D c X be two sets; suppose D that is countable and X - D
is infinite; then X and X - D are equipotent. From the preceding result,
X - D contains a countable set D' and one has
X = Y U (D U D'), X - D = Y U D'
where Y = X -(DUD') is disjoint from D and D'. It is not hard to construct
a bijection 9 of Y onto itself; since D and D' are countable, so is DUD'; thus
there is also a bijection h of DUD' onto D'. Then one obtains a bijection
f of X onto X - D by putting f(x) = g(x) [for example f(x) = x] for all
x E Y and f(x) = hex) for all xED U D'; f is clearly injective and
f(X) = flY U (D U D')] = fey) U feD U D') = Y U D' = X-D.
(7) The set of finite subsets of a countable set X is countable. From point
(4) above it is enough to show that, for a given n, the n-element subsets
of a countable set X form a countable subset Pn of P(X). Now consider
the cartesian product xn, the set of systems (Xl. ... ,xn ) of elements of X,
and the map f : xn -----t P(X) which transforms (Xl. ... , xn) into the set
{x!, ... , Xn} eX. Its image clearly contains Pn; and it is countable since xn
is, by (2) and (3); thus Pn is too, since Pn is clearly not finite.