When do two sets have the same size? For finite sets we can count; in general, we compare sets by means of maps between them.
Definition 1.7.1 (Cardinality). Sets and have the same cardinality, written , if there exists a bijection . We write if there exists an injection , and if and .
These are relations between sets; we do not define as an object in its own right, except for finite sets. A set is finite if for some (where ); this is unique, since an induction on shows that there is no injection , and we write , the number of elements of . A set with is countably infinite; a set that is finite or countably infinite is countable; any other set is uncountable.
Having the same cardinality behaves like an equivalence relation: is a bijection, the inverse of a bijection is a bijection, and a composite of bijections is a bijection (Propositions 1.5.5 and 1.5.6). Likewise , and implies , since a composite of injections is injective. If , the inclusion map shows that . The notation is justified by the following theorem, which lets us relate cardinality and maps between sets.
Theorem 1.7.2 (Schröder–Bernstein). If there exist injections and , then .
Proof. We build a bijection that uses on part of and the inverse of on the rest. Since is injective, every is for exactly one , which we denote .
Define subsets of by and , and let . Every lies outside , so . Hence defines a function .
The map is injective. Let . If both lie in , then . If neither does, then and are distinct, since sends them to and . Suppose and , say . If , then , so , a contradiction.
The map is surjective. Let . If , then . If , then , because ; so for some , and there is an with . Since is injective, . ∎
Note. The set has a simple description. Start from a point that is not in the image of and follow the chain ; then consists of the points of reached by such chains. On these points follows forward, and everywhere else follows backward.
Several sets that look larger than turn out to have the same cardinality.
Proposition 1.7.3 (The integers are countable). The map given by is a bijection. Hence .
Proof. The map sends the nonnegative integers to the even natural numbers and the negative integers to the odd ones (, , and so on). The map given by for even and for odd satisfies and , so is a bijection by Proposition 1.5.5. ∎
Proposition 1.7.4 (Pairs of natural numbers). The map , , is a bijection. Consequently for every .
Proof. Every positive integer can be written as with in exactly one way: must be the largest power of dividing , and the odd number . So is a bijection from onto the positive integers, and the additional shifts the positive integers onto ; for instance, .
For the second statement we induct on , the case being trivial. Sending to is a bijection . If is a bijection, then is a bijection , with inverse , and the first part finishes the induction. ∎
Proposition 1.7.5 (The rationals are countable). . More generally, and are countably infinite for every .
Proof. For , let be the smallest positive integer such that , and send to the pair . This is injective, since is recovered as . Composing with the bijection , , where is the bijection of Proposition 1.7.3, and then with the bijection of Proposition 1.7.4, gives an injection . The inclusion gives an injection the other way, and the Schröder–Bernstein theorem gives .
If is a bijection, then is a bijection , and by Proposition 1.7.4. The same argument applies to . ∎
Not every infinite set is countable. To show this for we use decimal expansions, and one fact about them from analysis: every has exactly one decimal expansion that does not end in an infinite string of s (we exclude, for instance, , which equals ); and every digit sequence that does not end in an infinite string of s is the expansion of some . We call this expansion the decimal expansion of .
Theorem 1.7.6 (Cantor’s diagonal argument). No map is surjective. Hence , and is uncountable.
Proof. We first show that no map is surjective. Write the decimal expansions of its values one below the other, and go down the diagonal: let if and if , and let . All digits of are s and s, so and this is its decimal expansion. For each , the decimal expansions of and differ in the th digit, so by uniqueness of decimal expansions. Thus is not in the range of .
Now let , and define by if and otherwise. Every element of in the range of is in the range of . So the element just constructed for , which is not in the range of , is not in the range of either, and is not surjective. In particular there is no bijection , while the inclusion gives . ∎
The same idea shows that there are arbitrarily large cardinalities.
Theorem 1.7.7 (There is no largest cardinality). For every set , no map is surjective. Hence .
Proof. Let , and let . Suppose for some . Then if and only if , a contradiction. So is not in the range of , and there is no bijection . On the other hand, is an injection . ∎
This is the diagonal argument again. Think of a map as a table with rows and columns indexed by , whose entry in row and column is if and otherwise. The set is obtained by going down the diagonal and switching every entry, so it differs from the row of in column , for every .
By Proposition 1.3.7, subsets of and functions amount to the same thing: is a bijection , whose inverse sends to . So . If is finite with , a function makes one of two choices at each of the elements, so , and the theorem generalizes the inequality . Applying the theorem repeatedly produces ever larger sets , , , …; so there is no largest cardinality.
Finally, sequences of real numbers are no more numerous than real numbers themselves.
Proposition 1.7.8 (Cardinality of mappings). .
Proof. We find injections in both directions and apply the Schröder–Bernstein theorem, working with in place of .
First, . The inclusion is an injection one way. For the other, is a strictly increasing, hence injective, map , and maps injectively into . By the Schröder–Bernstein theorem, there is a bijection . Applying termwise, , is a bijection , with inverse given by applying termwise. So it suffices to show that .
The map is an injection . For the other direction we interleave decimal digits. Let , , be the bijection of Proposition 1.7.4. Given a sequence in , write the decimal expansions , and define a digit sequence by that is, the th digit of is placed in position . Since is a bijection, every position receives exactly one digit. The positions carry the digits of , infinitely many of which differ from ; so does not end in an infinite string of s, and it is the decimal expansion of some . If , then for some , so their decimal expansions differ in some digit , and the two digit sequences built from them differ in position ; by uniqueness of decimal expansions, the corresponding values of differ. So is an injection .
By the Schröder–Bernstein theorem, , and therefore . ∎