Countable sets

We next show that there is no infinite set strictly smaller than ${\mathbb{N}}$.

Proposition 1   If $\char93 S \le \aleph_0$, then either $S$ is finite or $\char93 S=\aleph_0$.

Proof. Start listing distinct elements of $S$:

$$s_0,s_1,s_2,s_3,\dots$$

If at some point we run out of elements, then $S$ is finite. Otherwise we have constructed an injection ${\mathbb{N}}\rightarrow S$ sending $n$ to $s_n$ for each $n \in {\mathbb{N}}$, so $\aleph_0 = \char93 {\mathbb{N}}\le \char93 S$. But $\char93 S \le \aleph_0$ was given, so in this case, $\char93 S=\aleph_0$. $\qedsymbol$

A set $S$ is called countable if $\char93 S \le \aleph_0$, and $S$ is called countably infinite if $\char93 S=\aleph_0$. According to our definition (which not all people agree on), finite sets like $\{1,2,3\}$ and $\emptyset$ also are considered to be countable.

The following is an extremely useful tool for calculating cardinalities.

Theorem 2 (Typewriter Principle)   Let $S$ be a set. If there is a way to label each element of $S$ with a finite string of typewriter symbols (like fYe*4^!!!@) so that no two elements of $S$ are given the same label, then $S$ is countable; i.e., $\char93 S \le \aleph_0$. If moreover $S$ is infinite, then $\char93 S=\aleph_0$.

Proof. Let $T$ be the set of all finite strings of typewriter symbols. There are fewer than $900$ typewriter characters, so we may assign each a three-digit code not beginning with 0. For instance, we might assign

$$a \mapsto 100$$

$$b \mapsto 101$$

$$\% \mapsto 486$$

$$\vdots$$

Let strings of characters be mapped to the concatenation of the character codes; for instance, $ba\%$ would map to $101100486 \in {\mathbb{N}}$. This gives an injection $T \rightarrow {\mathbb{N}}$, so $\char93 T \le \char93 {\mathbb{N}}= \aleph_0$. The labelling of $S$ gives an injection $S \rightarrow T$, so $\char93 S \le \char93 T \le \aleph_0$. The final statement follows from Proposition 1. $\qedsymbol$

Proposition 3   $\char93 {\mathbb{Q}}= \aleph_0$.

Proof. Each rational number can be labelled with a string of typewriter symbols representing it like -75/89, and ${\mathbb{Q}}$ is infinite, so the Typewriter Principle shows that $\char93 {\mathbb{Q}}= \aleph_0$. $\qedsymbol$

An algebraic number is a complex number that is a zero of some nonzero polynomial with rational coefficients. A transcendental number is a complex number that is not algebraic. The set of algebraic numbers is denoted by $\overline{{\mathbb{Q}}}$. For instance, $\sqrt{2} \in \overline{{\mathbb{Q}}}$, since $\sqrt{2}$ is a zero of $x^2-2$. On the other hand, it is true (but very difficult to prove) that $\pi$ and $e$ are transcendental.

Proposition 4   $\char93 \overline{{\mathbb{Q}}}= \aleph_0$.

Proof. We can describe $-i\sqrt{2}$ as

the complex zero of x^2+2 closest to -1.4i

Similarly, each $a \in \overline{{\mathbb{Q}}}$ can be singled out by a finite string of typewriter symbols giving a polynomial with rational coefficients of which it is a zero, together with an approximate description of its location to distinguish it from the other zeros of that polynomial. By the Typewriter Principle, $\char93 \overline{{\mathbb{Q}}}= \aleph_0$. $\qedsymbol$