Level B2 · Upper-Intermediate

The Foundations of Mathematics

"God made the natural numbers; all else is the work of man." Leopold Kronecker

Level B2 crosses a real threshold: formulas replace words. Peano's axioms turn "number" from an intuition into nine precise lines; Cantor's naive set theory turns "collection" into a paradise — though, as an old anonymous saying about set theory goes, it's "a paradise with plenty of dark cellars," and Russell's paradox is the darkest of them. The chapter's answer is hereditarily finite sets: a sufficiently rich, paradox-free universe built from nothing but $\emptyset$.

What you'll learn

—First-order Peano Arithmetic ($\mathsf{PA}$) axiom by axiom: equality, successor, addition, multiplication, order, and the induction schema.
—Why induction is a schema — one axiom per formula — not a single second-order sentence, and what that costs in strength.
—Cantor's naive comprehension principle, why it's so seductive, and exactly how Russell's paradox breaks it.
—How restricting comprehension to a single primitive predicate ($\in$) and a short axiom list yields hereditarily finite sets ($\mathsf{HF}$) — paradox-free by construction.
—Why $\mathsf{HF}$ and $\mathsf{PA}$ turn out to be mutually interpretable — two languages for exactly the same finitary mathematics.

1. From words to formulas

In the late 19th century, mathematics needed a rigorous foundation for something everyone thought they already understood — the natural numbers. Giuseppe Peano's answer, in 1889, was to name the smallest set of undefined primitives that could carry the whole edifice: zero, and the operation "successor of." Everything else — addition, multiplication, order — gets defined recursively on top, and proved correct from the axioms alone, never from what a number "obviously" is.

Cantor's set theory, roughly contemporary, took the opposite gamble: instead of a minimal primitive vocabulary, it started from one maximally generous principle — every property defines a set — and built the arithmetic of the infinite on top of it. Both projects are the same instinct as Level A1's alphabet and Level A2's mathematical concept, just aimed at bigger game: define the undefined terms as narrowly and as explicitly as the subject allows.

2. A paradise, its cellars, and a way out

Peano Arithmetic's axioms are short enough to read in one sitting — and the last one is doing almost all the work:

PA1–7Equality, successor injectivity, $S(a)\ne 0$, and the recursive laws for $+,\cdot,<$.

PA8$\varphi[a/0]\land\forall x\,(\varphi[a/x]\to\varphi[a/Sx])\to\forall y\,\varphi[a/y]$ — induction, one axiom per formula $\varphi$.

That last clause is a schema, not a single sentence, precisely because first-order logic can't quantify over "all properties" the way second-order logic can — a limitation with real teeth, since it's exactly why $\mathsf{PA}$ has nonstandard models and can't pin down $\mathbb N$ up to isomorphism the way its second-order cousin can.

For a closer look at that whole ladder of theories — from first-order $\mathsf{PA}$ up through $\mathsf{ACA}_0$ and $\mathsf{Z}_2$ to the set-theoretic $\mathsf{ZFA}$ — see Hierarchy of Second-Order Arithmetic Theories.

Cantor's naive set theory has no such restraint: any property $\mathcal A(a)$ defines a set $\{x\mid\mathcal A(x)\}$. That freedom is what let him build the arithmetic of transfinite cardinals — and it's also what breaks. Define $R=\{x\mid x\notin x\}$. Is $R\in R$? If yes, then by definition $R\notin R$; if no, then $R$ satisfies its own defining property, so $R\in R$. Either way, contradiction — Russell's paradox.

The fix isn't cleverness, it's restraint: stop asking "which property defines a set?" and start asking "starting from a set I already have, which new sets am I allowed to build?" $\mathsf{HF}$, hereditarily finite sets, answers with a short axiom list — pairing, union, power set, separation, regularity — plus, crucially, the negation of the axiom of infinity. The result is a universe where every set is finite, every element of a set is itself finite, and Russell's $R$ simply cannot be built. And because every such set can be coded as a natural number and vice versa, $\mathsf{HF}$ and $\mathsf{PA}$ turn out to describe the very same mathematics in two different dialects.

3. Try it yourself

The first five exercises from the chapter's problem set, from the English edition.

Express the statement "Every natural number is either zero or a successor" in the language of $\PA$.
Formalize the definition of a "square number" using only multiplication.
Express the following arithmetic concepts in the language of $\PA$:
- "$x$ is an even number".
- "$x$ is a divisor of $y$" ($x \mid y$).
- "$x$ is a prime number".
- The Goldbach conjecture: "Every even integer greater than 2 is the sum of two primes".
Write a definition of a prime number using only the divisibility predicate ($x \mid y$) and the predicate of being invertible (a unit) $Inv(x) \leftrightarrow \exists y\,(xy=1)$.
Express the "Twin Prime Conjecture": there are infinitely many pairs of primes $p, q$ such that $q = S(S(p))$.

Level B2 has 22 exercises in total, each with a full worked solution in the book's appendix.

The rest of Level B2 — and one more level

This digest skips the full derivation of arithmetic's basic properties from the axioms alone, the precise difference between weak and strong order, why truth for all naturals differs from formal provability of a universal statement, and the tree-shaped representation that makes "hereditarily finite" visual. Level C1 takes the full $\mathsf{ZFC}$ axioms, the Axiom of Choice, and the von Neumann universe all the way to the edge of set-theoretic paradise.

Pre-order on Springer Back to the book overview

← Level B1 — Formal Logic Level C1 — A Mathematician's Paradise →