Foundations

Cardinality and Countability

Two sets have the same cardinality when a bijection exists between them. The naturals, integers, and rationals are countable. The reals are uncountable, proved by Cantor's diagonal argument.

CoreTier 2Stable~35 min

Prerequisites

Sets Functions and Relations

Quiz (3)

Why This Matters

The distinction between countable and uncountable sets has direct consequences for computability and learning theory. The set of all computer programs is countable (each program is a finite string). The set of all functions $\{0,1\}^* \to \{0,1\}$ is uncountable. Therefore, most functions cannot be computed by any program. Similarly, most hypothesis classes in learning theory are uncountable, which is why we need complexity measures like VC dimension rather than simply counting hypotheses.

Core Definitions

Definition

Cardinality

Two sets $A$ and $B$ have the same cardinality, written $|A| = |B|$ , if there exists a bijection $f: A \to B$ (as defined in sets, functions, and relations). Cardinality extends the notion of "size" from finite sets to infinite ones.

Definition

Countable Set

A set $S$ is countable if $|S| \leq |\mathbb{N}|$ . Equivalently, $S$ is countable if it is finite or there exists a bijection $f: \mathbb{N} \to S$ . A countably infinite set has cardinality $\aleph_0$ .

Definition

Uncountable Set

A set $S$ is uncountable if no surjection $f: \mathbb{N} \to S$ exists. Equivalently, no enumeration $s_1, s_2, s_3, \ldots$ can list all elements of $S$ .

Countability Results

$\mathbb{Z}$ is countable. List the integers as $0, 1, -1, 2, -2, 3, -3, \ldots$ This is an explicit bijection with $\mathbb{N}$ .

$\mathbb{Q}$ is countable. Arrange all fractions $a/b$ in a grid indexed by $(a, b)$ and traverse diagonally (Cantor's pairing argument), skipping duplicates.

A countable union of countable sets is countable. If $A_1, A_2, \ldots$ are each countable, then $\bigcup_{i=1}^{\infty} A_i$ is countable. Enumerate by diagonalizing over the index $i$ and the enumeration within each $A_i$ .

Main Theorems

Theorem

Uncountability of the Reals

Statement

The set $\mathbb{R}$ is uncountable. More precisely, the interval $[0, 1]$ is uncountable: there is no surjection from $\mathbb{N}$ onto $[0, 1]$ .

Intuition

Any proposed list of real numbers in $[0, 1]$ must miss at least one. The diagonal argument constructs that missing number explicitly by differing from the $n$ -th listed number in its $n$ -th decimal digit.

Proof Sketch

Suppose $r_1, r_2, r_3, \ldots$ is a list of all numbers in $[0, 1]$ . Write each $r_n$ in decimal. Define a new number $d$ whose $n$ -th digit differs from the $n$ -th digit of $r_n$ (e.g., if the digit is 5, make it 6; otherwise make it 5). Then $d \neq r_n$ for every $n$ because they differ in the $n$ -th digit. So $d \in [0, 1]$ is not in the list. Contradiction.

Why It Matters

This is the first proof that different sizes of infinity exist. It establishes that $|\mathbb{R}| > |\mathbb{N}|$ , which has consequences throughout mathematics. In CS: the set of Turing machines is countable, the set of languages over $\{0,1\}$ is uncountable, so most languages are undecidable.

Failure Mode

The proof requires care with decimal representations. Numbers like $0.999\ldots = 1.000\ldots$ have two representations. The standard fix is to avoid using 0 and 9 as replacement digits (use only digits 5 and 6, for instance).

Theorem

Cantor's Theorem

Statement

For any set $S$ , the power set $\mathcal{P}(S)$ has strictly greater cardinality than $S$ :

$|S| < |\mathcal{P}(S)|$

There is no surjection from $S$ onto $\mathcal{P}(S)$ .

Intuition

There are always more subsets of $S$ than elements of $S$ . The proof generalizes the diagonal argument: given any function $f: S \to \mathcal{P}(S)$ , construct the "anti-diagonal" set $D = \{s \in S : s \notin f(s)\}$ , which cannot be in the range of $f$ .

Proof Sketch

Let $f: S \to \mathcal{P}(S)$ be any function. Define $D = \{s \in S : s \notin f(s)\}$ . For any $s \in S$ : if $s \in D$ , then $s \notin f(s)$ , so $D \neq f(s)$ . If $s \notin D$ , then $s \in f(s)$ , so $D \neq f(s)$ . Either way $D \neq f(s)$ , so $f$ is not surjective.

Why It Matters

This produces an infinite hierarchy of infinities: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$ . Since $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = 2^{\aleph_0}$ , this also shows $|\mathbb{R}| > |\mathbb{N}|$ as a corollary.

Failure Mode

The construction of $D$ is not circular, though it may appear so. The set $D$ is well-defined for any given $f$ . The proof shows no single $f$ can work, not that $D$ depends on an unknown $f$ .

Common Confusions

Watch Out

Countable does not mean you can list elements in order

$\mathbb{Q}$ is countable, but any enumeration of the rationals is necessarily not in their natural order. "Countable" means a bijection with $\mathbb{N}$ exists; it says nothing about preserving any structure.

Watch Out

The rationals are dense but countable

$\mathbb{Q}$ is dense in $\mathbb{R}$ (between any two reals there is a rational), yet $\mathbb{Q}$ is countable while $\mathbb{R}$ is not. Density is a topological property. Cardinality is a set-theoretic one. They are independent.

Exercises

ExerciseCore

Problem

Prove that the set of all finite-length binary strings $\{0, 1\}^*$ is countable.

ExerciseAdvanced

Problem

Use Cantor's theorem to show that the set of all functions $f: \mathbb{N} \to \{0, 1\}$ is uncountable. Then explain why this implies most functions are not computable.

References

Canonical:

Halmos, Naive Set Theory, Chapters 15-16
Enderton, Elements of Set Theory, Chapter 6

Current:

Jech, Set Theory, 3rd millennium ed., Chapter 1
Munkres, Topology (2000), Chapter 1 (set theory review)

Next Topics

Measure theory foundations: cardinality underlies why we need measure theory (not all subsets of $\mathbb{R}$ are measurable)

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Sets, Functions, and RelationsLayer 0A
Basic Logic and Proof TechniquesLayer 0A

Next Topics

Measure Theoretic ProbabilityContinue →