Here is a seemingly innocuous question: When are two sets $A$ and $B$ the same size? Why, when they have the same number of elements, of course. This is a good answer, except that it turns out to be not at all clear what "same number of elements'' actually means when $A$ and $B$ are infinite. Do $\N$, $\Z$, $\Q$ and $\R$ all have different numbers of elements, or are some of them the same size?

This question really has no answer unless we agree on what "the same size'' means. Here is one way (the standard way) to define it: We say the sets $A$ and $B$ have the same size or cardinality if there is a bijection $f\colon A\to B$. If this is the case we write $A\approx B$.

Example 4.7.1 If $A$ and $B$ are finite, then $A\approx B$ if and only if $A$ and $B$ have the same number of elements. $\square$

This example shows that the definition of "same size'' extends the usual meaning for finite sets, something that we should require of any reasonable definition.

We say a set $A$ is countably infinite if $\N\approx A$, that is, $A$ has the same cardinality as the natural numbers. We say $A$ is countable if it is finite or countably infinite.

Example 4.7.2 The set $E$ of positive even integers is countably infinite: Let $f\colon \N\to E$ be $f(n)=2n$. $\square$

Example 4.7.3 The set $S$ of positive integers that are perfect squares is countably infinite: Let $f\colon \N\to S$ be $f(n)=n^2$. $\square$

In the last two examples, $E$ and $S$ are proper subsets of $\N$, but they have the same cardinality. This seeming paradox is in marked contrast to the situation for finite sets. If $A$ is finite and $B$ is a proper subset of $A$, it is impossible for $A$ and $B$ to have the same number of elements.

If $A$ is a countably infinite set and $f\colon \N\to A$ is a bijection, then $$ A=\{f(1), f(2), f(3), … \}. $$ In other words, a set is countably infinite if and only if it can be arranged in an infinite sequence.

Example 4.7.4 The set $\Z$ of all integers is countably infinite: Observe that we can arrange $\Z$ in a sequence in the following way: $$ 0, 1, -1, 2, -2, 3, -3, 4, -4, … $$ This corresponds to the bijection $f\colon \N\to \Z$ defined by $$ f(n)= \cases{n/2, &if $n$ is even;\cr -(n-1)/2, &if $n$ is odd.\cr} $$ $\square$

Example 4.7.5 The set $\Q^+$ of positive rational numbers is countably infinite: The idea is to define a bijection $g\,\colon \N\to \Q^+$ one prime at a time. The positive integer powers of, say, 2 can be paired up with the non-zero integer powers of $2$, that is, $$ \def\u{\updownarrow} \matrix {2, & 4, & 8, & 16, &… & 2^k, &…\cr \u & \u & \u & \u & & \u &\cr 2, & 1/2,& 4,& 1/4, &…& 2^{f(k+1)},&…\cr} $$ where $f$ is the bijection between the positive integers and the entire set of integers in example 4.7.4. We do this for every prime in the same way: $$ \def\u{\updownarrow} \matrix {p, & p^2, & p^3, & p^4, &… & p^k, &…\cr \u & \u & \u & \u & & \u &\cr p, & 1/p,& p^2,& 1/p^2, &…& p^{f(k+1)},&…\cr} $$ Call this function $g$, $\ds g(p^k)=p^{f(k+1)}$. Then we extend this to products of prime powers. For example, $$ \eqalign{g(3^4 5^5)=&g(3^4) g(5^5)= 5^3/3^2;\cr g(7^{10}11^4 13^7 17)=&(13^4 17)/(7^5 11^2);\cr g(2^8 3^5 5^4 11^2 7^3)=&(3^3 7^2)/(2^4 5^211).\cr} $$ In general, then, let $g(1)=1$ and $$ \eqalignno{ g (p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})&= p_1^{f(e_1+1)}p_2^{f(e_2+1)}\cdots p_k^{f(e_k+1)}& (4.7.1)\cr }$$ That $g$ is a bijection is a consequence of the fact that any rational number can be uniquely expressed as $a/b$, where $a$ and $b$ are positive integers that are relatively prime (so their prime factorizations involve disjoint sets of primes). $\square$

Here are some simple but important properties of cardinality:

Theorem 4.7.6 Suppose $A$, $B$ and $C$ are sets. Then

    a) $A\approx A$,

    b) $A\approx B$ implies $B\approx A$,

    c) $A\approx B$ and $B\approx C$ implies $A\approx C$.

Proof. Since $i_A\colon A \to A$ is a bijection, part (a) follows. If $f\colon A\to B$ is a bijection, then by theorem 4.6.11, $f^{-1}\colon B\to A$ is a bijection, so part (b) is true. Similarly, part (c) follows from the fact that the composition of bijections is a bijection. $\qed$

Exercises 4.7

Ex 4.7.1 Show that the following sets are countably infinite:

Ex 4.7.2

Ex 4.7.3 Show that the following sets of real numbers have the same cardinality:

Ex 4.7.4 Show that $\Q$ is countably infinite. (Hint: you can arrange $\Q^+$ in a sequence; use this to arrange $\Q$ into a sequence.)

Ex 4.7.5 Suppose $B$ is a countably infinite set and $S$ is a subset of $B$. Explain why $S$ is also countable. Suppose $f\colon A\to B$ is an injection. Explain why $A$ is countable.

Ex 4.7.6 Show that $\N\times \N$ is countably infinite. (Hint: map $(n,m)\in \N\times \N$ to $2^{n-1}(2m-1)$.)

Ex 4.7.7 Use problem 6 and induction to prove that $\N\,^k = \N\times \N\times \cdots \times \N$ is countably infinite.

Ex 4.7.8 Prove that $\Z\,^k = \Z\times \Z\times \cdots \times \Z$ is countably infinite.

Ex 4.7.9 Any positive rational number other than 1 can be written as $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ in exactly one way, where the $e_i$ are non-zero integers. Write a simple expression (analogous to equation (4.7.1)) for $g^{-1}\colon \Q^+\to\N$.