Countable and Uncountable Sets

The distinction between countable and uncountable infinity is one of the most profound discoveries in mathematics, revealing that there are fundamentally different "sizes" of infinity.

Countability

Definition5.4Countable and uncountable

A set $A$ is countable if $|A| \leq \aleph_0$ , i.e., there exists an injection $A \hookrightarrow \mathbb{N}$ . A set is countably infinite if $|A| = \aleph_0$ , and uncountable if $|A| > \aleph_0$ .

Equivalently, $A$ is countable if and only if $A$ is finite or there exists a surjection $\mathbb{N} \twoheadrightarrow A$ (i.e., $A$ can be enumerated as a sequence).

Theorem5.2Properties of countable sets

Every subset of a countable set is countable.
A countable union of countable sets is countable: if $A_n$ is countable for each $n \in \mathbb{N}$ , then $\bigcup_{n=0}^{\infty} A_n$ is countable.
The Cartesian product of finitely many countable sets is countable.
$\mathbb{Z}$ , $\mathbb{Q}$ , and the set of algebraic numbers are countable.

Cantor's Diagonal Argument

Theorem5.3Uncountability of the reals

$\mathbb{R}$ is uncountable. More specifically, $[0,1]$ is uncountable.

Proof

Suppose $f: \mathbb{N} \to [0,1]$ is a surjection. Write each $f(n)$ in decimal: $f(n) = 0.d_{n,1}d_{n,2}d_{n,3}\ldots$ (choosing the non-terminating representation when ambiguous).

Define $x = 0.e_1 e_2 e_3 \ldots$ where $e_n = 5$ if $d_{n,n} \neq 5$ and $e_n = 6$ if $d_{n,n} = 5$ . Then $x \in [0,1]$ but $x \neq f(n)$ for any $n$ (since $x$ and $f(n)$ differ in the $n$ -th decimal place). This contradicts surjectivity. $\blacksquare$

■

Cardinality Comparisons

ExampleSets with cardinality of the continuum

All of the following have cardinality $\mathfrak{c} = 2^{\aleph_0}$ :

$\mathbb{R}$ , $(0,1)$ , $[0,1]$ (via bijections using tangent or similar).
$\mathbb{R}^n$ for any finite $n$ (by space-filling curve arguments or interleaving decimals).
$\mathcal{P}(\mathbb{N})$ (by characteristic functions).
The Cantor set $\mathcal{C}$ (despite having Lebesgue measure zero).
$C([0,1])$ , the space of continuous functions on $[0,1]$ .

RemarkThe beth numbers

The beth numbers are defined by: $\beth_0 = \aleph_0$ , $\beth_{\alpha+1} = 2^{\beth_\alpha}$ , $\beth_\lambda = \sup_{\alpha < \lambda}\beth_\alpha$ . So $\beth_1 = \mathfrak{c}$ , $\beth_2 = 2^{\mathfrak{c}}$ , etc. The GCH is equivalent to $\beth_\alpha = \aleph_\alpha$ for all $\alpha$ . Without GCH, the relationship between the aleph and beth hierarchies is highly non-trivial.