Target Audience: Anyone who has met sets and functions and is ready for the first genuinely surprising theorem in mathematics.
Prerequisites: Sets, Relations and Functions — especially bijections — and Proof Techniques, since the central arguments are proofs by contradiction.
This is the unit where careful definitions pay off spectacularly. Everything rests on one decision made in Section 1 — that "same size" means "there is a bijection" — and once that is fixed, the consequences are forced, whether or not they feel reasonable.
Two of them are famous: the rationals are no more numerous than the counting numbers, and the reals are strictly more numerous. The explorer shows both sides: an explicit list that reaches every rational, and the argument for why no list can reach every real.
Sections 9 and 10 go beyond what a first course needs; read them for the view, not for technique.
For finite sets, "same size" is easy: count both and compare. That method dies the moment the sets are infinite, so we need a definition that never counts.
To check that every sheep has a pen without counting either, put one sheep in each pen. If they run out together, the two collections are the same size. That is a bijection — and it needs no numbers at all.
This is the whole idea of the page. Everything below is that one move applied where counting is impossible.
For finite sets, a proper subset really is strictly smaller. For infinite sets this fails, and it must: the even numbers are a proper subset of \(\mathbb{N}\), yet \(n \mapsto 2n\) pairs them off perfectly.
This is not a paradox but a definition of infinite: a set is infinite exactly when it can be put in bijection with a proper subset of itself. If that offends intuition, the intuition was trained on finite sets.
\(A\) and \(B\) have the same cardinality, written \(|A| = |B|\), when there exists a bijection \(f : A \to B\).
Note what this does not say: it does not define \(|A|\) as an object. It defines the relation "same size" directly, which is all that is needed and avoids awkward questions about what an infinite number is.
Reflexive via \(\mathrm{id}_A\); symmetric because a bijection has a bijective inverse; transitive because a composition of bijections is a bijection. All three facts come straight from Unit 3.
So "same cardinality" partitions all sets into classes of equal size — the equivalence relation and partition machinery doing real work.
\(|A| \leq |B|\) when there is an injection \(A \to B\), and \(|A| \lt |B|\) when \(|A| \leq |B|\) but \(|A| \neq |B|\).
An injection embeds \(A\) into \(B\) with room possibly to spare. That \(\leq\) behaves as an order — in particular that \(|A| \leq |B|\) and \(|B| \leq |A|\) force \(|A| = |B|\) — is Section 8, and it is a genuine theorem, not a triviality.
Countable includes the finite sets. Some authors use "countable" to mean countably infinite, so check the convention before reading a theorem — a claim like "every countable union of countable sets is countable" changes meaning with it.
\(A\) is countably infinite exactly when its elements can be written as an infinite list without repeats,
because such a list is a bijection \(\mathbb{N} \to A\). Every countability proof below amounts to exhibiting a list; every uncountability proof amounts to showing no list can work.
\(f : \mathbb{N} \to 2\mathbb{N}\), \(f(n) = 2n\), is a bijection. So there are exactly as many even numbers as natural numbers, despite the evens omitting infinitely many naturals.
The second is why the anti-diagonal walk in the next section works: each diagonal is finite, and there are countably many of them.
"List all the integers: \(0, 1, 2, 3, \ldots\) and then \(-1, -2, -3, \ldots\)" is not a list. Nothing in the second half is ever reached, because no natural number indexes it. A valid enumeration assigns each element a finite position — which is why the integers are listed by alternating signs instead.
Alternate signs:
Explicitly, \(f(n) = n/2\) for even \(n\) and \(f(n) = -(n-1)/2\) for odd \(n\). Every integer appears exactly once, at a finite position. So \(|\mathbb{Z}| = \aleph_0\).
Arrange \(\mathbb{N} \times \mathbb{N}\) in a grid and walk the finite anti-diagonals \(a + b = 0, 1, 2, \ldots\). Each diagonal is finite, so every pair is reached in finitely many steps.
For the positive rationals, walk the same grid reading \((a,b)\) as \(a/b\), and skip any fraction not in lowest terms so no value is listed twice. Then interleave with the negatives and \(0\) as for \(\mathbb{Z}\).
Full argument on The Countability of ℤ and ℚ.
The top half lists a countable set: choose the set, and slide to see more of the enumeration. The bottom half runs Cantor's diagonal argument on a proposed list of reals — the highlighted diagonal builds a number that is not on it.
Suppose someone hands you this list of numbers in \((0,1)\), written as decimals. The diagonal is highlighted.
Each escape digit is chosen to be 4 or 5, differing from the diagonal digit directly above it — which is exactly why the number cannot equal any row.
\(\mathbb{R}\) is uncountable. Indeed the interval \((0,1)\) already is.
Suppose, for contradiction, that \((0,1)\) is countable, so its elements can be listed \(x_1, x_2, x_3, \ldots\). Write each in decimal:
Build \(z = 0.z_1 z_2 z_3 \ldots\) by setting \(z_n = 5\) if \(d_{nn} = 4\), and \(z_n = 4\) otherwise.
Then \(z \in (0,1)\), but \(z \neq x_n\) for every \(n\), because they differ in the \(n\)-th decimal place. So \(z\) is missing from a list that was supposed to contain everything — contradiction. \(\blacksquare\)
Because some reals have two decimal expansions: \(0.4999\ldots = 0.5000\ldots\). If the escape digits were allowed to be \(0\) or \(9\), the number \(z\) might differ from \(x_n\) digit-by-digit while still being the same number, and the contradiction would evaporate.
Confining \(z\) to the digits \(4\) and \(5\) means it never ends in all \(0\)s or all \(9\)s, so its expansion is unique and digitwise difference really does mean difference. This is the step most retellings skip.
Not "that particular list was badly chosen" — the list was arbitrary. The construction turns any proposed enumeration into a number it misses, so no enumeration can exist.
Full argument on The Uncountability of the Real Numbers.
\(\mathbb{Q}\) is countable and \(\mathbb{R}\) is not, so the irrationals must be uncountable — there are, in a precise sense, vastly more irrational numbers than rational ones, even though the rationals are dense in the line. The same argument gives uncountably many transcendental numbers, without exhibiting a single one.
For every set \(A\), \(|A| \lt |\mathcal{P}(A)|\). No set is in bijection with its own power set — not even an infinite one.
\(a \mapsto \{a\}\) is an injection \(A \to \mathcal{P}(A)\), so \(|A| \leq |\mathcal{P}(A)|\).
For the strictness, let \(f : A \to \mathcal{P}(A)\) be any function and set
If \(D = f(d)\) for some \(d\), then \(d \in D \Leftrightarrow d \notin f(d) = D\) — a statement equivalent to its own negation. So \(D\) is not in the image, \(f\) is not surjective, and no bijection exists. \(\blacksquare\)
\(D\) is the set of elements that "do not contain themselves" under \(f\), and the contradiction has exactly the shape of Russell's paradox. The difference is the outcome: Russell showed a naive axiom was untenable; Cantor shows a function cannot exist. Same diagonal move, different target.
Full argument on Cantor's Theorem.
If \(|A| \leq |B|\) and \(|B| \leq |A|\), then \(|A| = |B|\). That is: injections both ways guarantee a bijection.
For numbers this is trivial. For cardinalities it is not: you are handed two injections and must construct a bijection out of them, and neither injection need be anywhere near surjective.
Showing \(|(0,1)| = |\mathbb{R}|\) directly needs a clever formula. With Schröder–Bernstein you only need two easy injections: \((0,1) \hookrightarrow \mathbb{R}\) is inclusion, and \(\mathbb{R} \hookrightarrow (0,1)\) is any squashing map. Bijection guaranteed, no formula required.
Full argument, including the iterated-image construction, on The Schröder–Bernstein Theorem.
Cantor's theorem applies to any set, including infinite ones, so it can be iterated:
There is no largest infinity. The cardinal \(\aleph_0 = |\mathbb{N}|\) is the smallest infinite one, and \(|\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}\) turns out to equal \(|\mathbb{R}|\), written \(\mathfrak{c}\) and called the cardinality of the continuum.
Addition and multiplication of infinite cardinals are dull — they just take the larger. Exponentiation is where everything happens.
We know \(\aleph_0 \lt \mathfrak{c}\). Is there a cardinality strictly between them — a set larger than \(\mathbb{N}\) but smaller than \(\mathbb{R}\)?
The Continuum Hypothesis asserts there is no such set. Gödel (1940) showed it cannot be disproved from the standard axioms of set theory; Cohen (1963) showed it cannot be proved from them either.
So it is independent: both it and its negation are consistent with the usual axioms. This is not ignorance that better mathematics will fix — the axioms simply do not decide the question, much as the parallel postulate does not follow from Euclid's other four.
"Nobody has proved it yet" and "it cannot be proved" are entirely different claims. Goldbach's conjecture is the first kind; the Continuum Hypothesis is provably the second.
| Idea | The one thing to remember |
|---|---|
| Same size | A bijection exists. Never counting. |
| Infinite | In bijection with a proper subset of itself — a feature, not a paradox. |
| Countable | Finite, or listable as \(a_1, a_2, \ldots\) with every element at a finite position. |
| ℤ and ℚ | Countable. Alternate signs; walk the finite anti-diagonals. |
| ℝ | Uncountable, by diagonalisation. Escape digits 4 and 5 to dodge the dual-decimal trap. |
| Cantor's theorem | \(|A| \lt |\mathcal{P}(A)|\) always. No largest infinity. |
| Schröder–Bernstein | Injections both ways give a bijection — the workhorse for proving equal cardinality. |
| Continuum Hypothesis | Independent of the standard axioms — undecidable, not merely unsolved. |
Text used for this page: Hammack, Book of Proof, Chapter 14 (free online). This completes Tier 0. Tier 1 begins with Algebra, Polynomials and Complex Numbers.
| Notation | Read as | Means |
|---|---|---|
| \(|A| = |B|\) | A and B are equinumerous | There is a bijection \(A \to B\). |
| \(|A| \leq |B|\) | A is no larger than B | There is an injection \(A \to B\). |
| \(|A| \lt |B|\) | A is strictly smaller than B | An injection exists, but no bijection. |
| \(\aleph_0\) | aleph-null | \(|\mathbb{N}|\) — the smallest infinite cardinality. |
| \(\mathfrak{c}\) | the continuum | \(|\mathbb{R}| = 2^{\aleph_0}\). |
| \(2^{\aleph_0}\) | two to the aleph-null | \(|\mathcal{P}(\mathbb{N})|\), which equals \(\mathfrak{c}\). |
| \(A \hookrightarrow B\) | A embeds in B | Notation for an injection. |
| \(\mathcal{P}(A)\) | the power set of A | All subsets. Always strictly bigger than \(A\). |