We have seen that many infinite sets that might seem to have different sizes are in fact the same size. Are there infinite sets that are not the same size as the integers? The answer is `yes', in fact, a resounding `yes'—there are infinite sets of infinitely many different sizes. We'll begin by showing that one particular set, $\R$, is uncountable. The technique we use is the famous diagonalization process of Georg Cantor.
Proof. We will show that $\N\not\approx(0,1)$. Once we know this, then for a contradiction we suppose there is a bijection $g\colon\N\to\R$. By exercise 3 in section 4.7, we know there is a bijection $f\colon\R\to(0,1)$. Thus there is a bijection $f\circ g\colon\N\to(0,1)$, which contradicts $\N\not\approx(0,1)$.
Now, for a contradiction, suppose $(0,1)$ is countably infinite, so these numbers can be arranged in a sequence, say $r_1$, $r_2$, $r_3$, …. We show that this cannot be a list of all the reals in $(0,1)$ by finding a real number that is not on the list, contradicting the assumption.
The numbers $r_i$ can be written in decimal form; the list might start something like this: $$ \eqalign{r_1&=.\underline 23454167…,\cr r_2&=.1\underline 5367843…,\cr r_3&=.86\underline 954367…,\cr r_4&=.199\underline 19423…,\cr r_5&=.2245\underline 3665…,\cr &\quad \vdots\cr} $$ Let $r$ be the real number with decimal expansion $0.d_1d_2d_3d_4d_5… $, where $d_i=1$ unless the $i$th expansion has a 1 in the $i$th place to the right of the decimal point, in which case $d_i=5$. (For the list above, the expansion would be $0.11151\ldots$; the `diagonal' entries are underlined.) This decimal expansion is different than every expansion in the list, so $r$ is not on the list. $\qed$
This proof is actually a bit trickier than it appears, because two different decimal expansions can represent the same real number. See exercise 14.
We want to be able to talk about the "size'' of an infinite set, in much the same way that we talk about the size of a finite set (as in, "The set $\{a,b,c,d,e\}$ has size 5.''). With every set $A$ we associate a symbol $\overline A$, called the cardinal number of $A$, and we say that $\overline A=\overline B$ if and only if $A\approx B$.
Some cardinal numbers occur so frequently that they have been given special names: $\overline{\N}=\aleph_0$ ("aleph-naught'') and $\overline{\R}=c$ (the size of the "continuum''). In this language, we can say that the "size'' of $\Q$ or of $\Z$ is $\aleph_0$, and that the size of $(0,1)\subseteq\R$ is $c$.
One familiar feature of finite `sizes' is that they come in a particular order—that is, if two sizes are different then one is bigger than the other. When can we say that one infinite cardinal number is bigger than another? Here is a natural way: If $\overline A$ and $\overline B$ are cardinal numbers, define $\overline A\le \overline B$ to mean that there is an injection $f\colon A\to B$.
There is a potential, somewhat subtle problem with this definition. We are defining a relationship between `sizes' by referring to particular sets that have those sizes. What if we were to choose different sets, say $A'$ and $B'$, with the same sizes?
Lemma 4.8.2 Suppose $\overline A= \overline {A'}$ and $\overline B=\overline {B'}$. There is an injection $f\colon A\to B$ if and only if there is an injection $f'\colon A'\to B'$.
Proof. Suppose there is an injection $f\colon A\to B$. There are bijections $\theta\colon A'\to A$ and $\phi\colon B\to B'$. So $f'=\phi\circ f\circ \theta$ is an injection from $A'$ to $B'$. The converse is similar. $\qed$
The upshot of this lemma is that the definition does not depend upon which particular set is chosen to represent these two cardinal numbers, that is, "$\le$'' is well-defined. This ordering of the cardinal numbers has some familiar properties.
Theorem 4.8.3 Suppose $A$, $B$ and $C$ are sets. Then
a) $\overline A\le\overline A$;
b) if $\overline A\le \overline B$ and $\overline B\le \overline C$, then $\overline A\le \overline C$.
Proof. For part (a), use the identity map. For part (b), if $f\colon A\to B$ and $g\colon B\to C$ are injections, then $g\circ f\colon A\to C$ is an injection, so $\overline A\le \overline C$.$\qed$
Exercises 4.8
Ex 4.8.1 Show that $\R^2$ is not countable.
Ex 4.8.2 Show that the set $S$ of all infinite sequences of 0's and 1's is not countable (the elements of $S$ are infinitely long strings of the form "00110101110…'').
Ex 4.8.3 Suppose $A$ and $B$ are disjoint countably infinite sets. Show that $A\cup B$ is countably infinite. (Think about arranging things into sequences.)
Ex 4.8.4 Suppose $A$ is finite and $B$ is countably infinite. Show that $A\cup B$ is countably infinite.
Ex 4.8.5 Suppose $A$ and $B$ are countably infinite sets. Show that $A\cup B$ is countably infinite.
Ex 4.8.6 Use exercise 5 and induction to prove that the union of any finite collection of countably infinite sets is countably infinite.
Ex 4.8.7 Suppose that $\{A_i\mid i\in\N\}$ is a set of non-empty countable sets. Prove that $\bigcup_{i\in\N} A_i$ is countable.
Ex 4.8.8 Show that the set of all polynomials with coefficients in $\Z$ is countably infinite.
Ex 4.8.9 The set of all (complex) roots of all polynomials with coefficients in $\Z$ is the algebraic numbers. Show that the algebraic numbers are countable. You may use the face that every polynomial has a finite number of roots.
Ex 4.8.10 Let $\cal I$ be the set of irrational numbers (i.e., $\{x\in \R: x\notin \Q\,\}$). Show that $\cal I$ is not countable. (Use exercise 5.)
Ex 4.8.11 Suppose $A$ and $B$ are non-empty sets. Show that $\overline A\le \overline B$ if and only if there is a surjection $g\colon B\to A$.
Ex 4.8.12 Suppose $A$ is a countable set and $f\colon A\to B$ is a surjective function. Show that $B$ is also countable. (Hint: use exercise 5 of section 4.7.)
Ex 4.8.13 Use decimal expansions to construct an injection from (0,1) to the irrationals (remember that a number is rational if and only if its decimal terminates or repeats).
Ex 4.8.14 In the proof of theorem 4.8.1, we constructed a decimal expansion that was not on a given list of decimal expansions. This does not by itself imply that the real number represented by the constructed expansion is not the same as a real number represented by an expansion on the list, because some real numbers have more than one decimal expansion. Explain which real numbers have more than one decimal expansion, and then explain why the real number constructed in the proof is guaranteed not to be on the list of real numbers.