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.**
The proof is by contradiction.
If $\R$ were countably infinite
the reals could be arranged in a sequence, say $r_1$,
$r_2$, $r_3$, ….
We show that this cannot be a listing of all the reals by finding a real
number that is not on the list.
Imagine that the fractional parts of these numbers are written
in their decimal form in a list. The list might start something like this:
$$
\eqalign{&.\underline 23454167…,\cr
&.1\underline 5367843…,\cr
&.86\underline 954367…,\cr
&.199\underline 19423…,\cr
&.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.