Applications

Two sets A and B are said to have the same cardinality, and then we write A  B, if
there exists a bijection from A onto B. Obviously, having the same cardinality is an
equivalence relation; it is
1. reflexive: A  A,
2. symmetric: A  B ) B  A,
3. transitive: A  B and B  C ) A  C.
A set is said to be finite if it is empty or has the same cardinality as {1, 2, . . . , n} for
some n in N; in the former case it has 0 elements, in the latter exactly n. It is said to
be countable if it is finite or has the same cardinality as N; in the latter case it is said to
have a countable infinity of elements.
In particular, N is countable. So are Z, N × N in view of exercises 2.3 and 2.4.
Note that an infinite set can have the same cardinality as one of its proper subsets. For
instance, Z  N, R+  (0, 1], R  R+  (0, 1); see exercise 2.2 for the latter.
Incidentally, R+, R, etc. are uncountable, as we shall show shortly.
A set is countable if and only if it can be injected into N, or equivalently, if and
only if there is a surjection from N onto it. Thus, a set A is countable if and only if
there is a sequence (xn) whose range is A. The following lemma follows easily from
these remarks.
3. COUNTABILITY 7
3.1 LEMMA. If A can be injected into B and B is countable, then A is countable. If
A is countable and there is a surjection from A onto B, then B is countable.
3.2 THEOREM. The product of two countable sets is countable.
PROOF. Let A and B be countable. If one of them is empty, then A×B is empty and
there is nothing to prove. Suppose that neither is empty. Then, there exist injections
f : A 7! N and g : B 7! N. For each pair (x, y) in A × B, let h(x, y) = (f(x), g(y));
then h is an injection from A × B into N × N. Since N × N is countab