Logic and sets

For fifty chapters in a row we’ve been proving theorems without once asking what the word itself means. We wrote “for every $\varepsilon > 0$ there’s a $\delta$”, “the set of values”, “infinitely many primes”, “therefore”, and the last chapter measured information in “yes” or “no” answers. All this worked the way your native language works: you use it without opening a grammar book.

But a native language has habits that don’t suit mathematics. “Tea or coffee?” on a plane offers one of the two, while in a notice saying “discount for students or pensioners” a student who is also a pensioner doesn’t lose the discount. “All the students passed” sometimes means “almost all”. The language of mathematics needs every sentence to have exactly one meaning, and every argument to be checkable for correctness. That’s the grammar we’ll learn, and we’ll practise on an island invented by the American logician and magician Raymond Smullyan in his book What Is the Name of This Book? (1978).

The island of knights and knaves

The island has two kinds of inhabitants. Knights always tell the truth, knaves always lie. You can’t tell them apart by looking. You meet two of them, $A$ and $B$, and $A$ says: “At least one of us is a knave.” Who is who?

Let’s go through the cases. Suppose $A$ is a knave. Then his words are false, that is, there are no knaves among them and both are knights, including $A$ himself. A contradiction: $A$ can’t be both a knave and a knight. So $A$ is a knight. Then his words are true, and there is a knave among the two. Since it isn’t $A$, it’s $B$. Answer: $A$ is a knight, $B$ a knave.

We went through the possible worlds and threw out the one that contradicts itself: the two main operations of this chapter. An islander’s words are either true or false, and an inhabitant’s type must match the truth of what they say.

There’s a sentence on the island that nobody can say: “I am a knave.” A knight saying it would be lying, and a knave would be telling the truth. Such sentences are neither true nor false, and they’re kept out of the world of statements. Remember this sentence: at the end of the chapter it will come back and nearly bring down the whole of mathematics.

There are three inhabitants. $A$ says: “We are all knaves.” $B$ says: “Exactly one of us is a knight.” $C$ says nothing. How many knights are there among them?

$A$ can’t be a knight: then his words “we are all knaves” would be true, and he’d be a knave. So $A$ is a knave, his words are false, and there’s at least one knight among the three. If $B$ were a knave, the only knight would be $C$: exactly one, and $B$’s words would be true. A contradiction, so $B$ is a knight, and there’s exactly one knight among the three: $C$ is a knave. Answer: one knight. Check it in the widget by building this island on the “Your own island” tab.

Lesson one: not, and, or

Compound statements are built from simple ones with connective words, which logicians have agreed to understand strictly and write as symbols. The negation $\lnot A$ (“not $A$”) is true when $A$ is false. The conjunction $A \land B$ (“$A$ and $B$”) is true when both are true. The disjunction $A \lor B$ (“$A$ or $B$”) is true when at least one of the two is true, including when both are. This is the “or” of the discount notice, not of the plane; for “exactly one of the two” there’s a separate connective, exclusive “or”, $A \oplus B$.

The truth of a compound statement depends only on the truth of its parts, so a connective is completely described by a table of all the combinations. We’ll write truth as T and falsehood as F.

The symbol $\equiv$ isn’t a connective inside a formula but our statement about two formulas. The simplest tautology is $A \lor \lnot A$, the law of the excluded middle: every statement is true or false. The second famous law answers a question that comes up in any argument: what does it mean for someone to be wrong when they said “or”?

The trick is that a truth table is finite: by checking four rows we’ve checked every possible case at once.

Write out all four combinations of values of $A$ and $B$. There are no others: each statement is either true or false. In each row find $A \lor B$: it’s false only in the last one, where both are false. Negation flips the column: $\lnot(A \lor B)$ is true only in the last row. Now the right-hand side. The conjunction $\lnot A \land \lnot B$ is true when $\lnot A$ and $\lnot B$ are both true, that is, when $A$ and $B$ are both false. Again that’s only the last row. The columns agree in all four rows. So $\lnot(A \lor B) \equiv \lnot A \land \lnot B$: the first law is proved. We’ll derive the second law from the first without drawing a new table. The first law holds for any statements, including $\lnot A$ and $\lnot B$: $\lnot(\lnot A \lor \lnot B) \equiv \lnot\lnot A \land \lnot\lnot B \equiv A \land B$, since a double negation gives back the original value. Equivalent formulas stay equivalent after negation, so $\lnot A \lor \lnot B \equiv \lnot(A \land B)$.

Checking with a table is completely mechanical, and it’s better left to a machine. Type in two formulas: the widget will build the tables, say whether the formulas are equivalent, and if not, show a row where they differ.

The circles next to the table aren’t decoration. Two circles have exactly four regions (inside both, only in the first, only in the second, outside) just as the table has four rows, and three circles have eight regions, as many as a formula with three variables has rows. This coincidence will come in handy when we get to sets.

Lesson two: if…, then…

The trickiest connective is “if…, then…”. Take a promise: “If it rains tomorrow, I’ll take an umbrella.” When is it broken? Only if it rained and there’s no umbrella. If it doesn’t rain, the promise required nothing, and it can’t be broken, whatever the person does with the umbrella.

The hypothesis: “it rains”. While it’s false, the implication is true whatever the conclusion. The conclusion: “I’ll take an umbrella”. If it’s true, the implication is true whatever the hypothesis. The negation of the hypothesis. An implication asserts exactly one thing: it never happens that the hypothesis holds and the conclusion doesn’t. Example: “if $n$ is divisible by $4$, then $n$ is even”. At $n = 8$ the hypothesis and conclusion are true; at $n = 6$ the hypothesis is false and the conclusion true; at $n = 7$ both are false. In all three cases the implication is true. Only a number divisible by $4$ and odd could refute it, and there are none.

The rows with a false hypothesis are the most confusing: “if $2 + 2 = 5$, then the Moon is made of cheese” is a true statement. Logicians say: from a falsehood anything follows. According to a well-known anecdote, Bertrand Russell was once asked to prove that $2 + 2 = 5$ implies he was the Pope. Russell replied: subtract three from both sides and we get $1 = 2$; the Pope and I are two, so the Pope and I are one. That’s exactly why a contradiction in a theory is a disaster: if both $C$ and $\lnot C$ have been proved in it, every statement can be proved in it.

Swapping the hypothesis and the conclusion gives the converse $B \to A$. It may or may not be true: “if a number is divisible by $4$, it’s even” is true, but “if a number is even, it’s divisible by $4$” isn’t, with counterexample $6$. But every implication has a twin that’s always equivalent to it.

Four rows again. We look for where each implication is false: an implication has only one such row.

Write out the four combinations of values of $A$ and $B$. $A \to B$ is false only where $A$ is true and $B$ false: in the second row. $\lnot B \to \lnot A$ is false only where $\lnot B$ is true and $\lnot A$ false, that is, $B$ false and $A$ true. That’s the same second row. The columns agree in all rows, so $A \to B \equiv \lnot B \to \lnot A$. For comparison, the converse $B \to A$. It’s false in the third row, where $B$ is true and $A$ false, and true in the second. The columns differ, and $B \to A$ can’t be derived from $A \to B$.

The meaning of the law is clear without a table too. “If it’s raining, the pavement is wet” and “if the pavement is dry, it isn’t raining” say the same thing. But “if the pavement is wet, it’s raining” is something else: a street-cleaning lorry may have watered it.

It seems impossible to go wrong here. In 1966 the English psychologist Peter Wason tested this with four cards. Play it yourself before reading on.

The rule “if one side has a vowel, the other side has an even number” is an implication $P \to Q$, and it can be broken only by a card where $P$ is true and $Q$ false. You have to turn over $E$ (in case there’s an odd number behind it) and $7$ (in case there’s a vowel behind it). On the card $K$ the hypothesis is false, on the card $4$ the conclusion is already true, and turning them over settles nothing. Most people choose $E$ and $4$, or just $E$; in various experiments something like one person in ten gives the right answer. We check the hypothesis but forget about the contrapositive, “if odd, then not a vowel”.

The bar rule “if someone is drinking beer, they’re over eighteen” works the same way: you have to check the beer and the sixteen-year-old. Here most people in the experiments answer correctly: we’re used to looking for rule-breakers in real life. The logic on the two tabs is the same, but the intuition differs, and mathematics needs a logic that doesn’t depend on what the subject is.

Implications in both directions give the equivalence $A \leftrightarrow B \equiv (A \to B) \land (B \to A)$: “$A$ if and only if $B$”, “$A$ is necessary and sufficient for $B$”. That’s how an islander is linked to their words: if $X$ is “$X$ is a knight” and $S$ is what was said, then $X \leftrightarrow S$. The whole island puzzle is a conjunction of such equivalences, and the widget above solved it with a table.

Lesson three: all and some

Connectives aren’t enough to write the most ordinary mathematical statement: “the square of any number is non-negative”. This isn’t about one statement but infinitely many: $0^2 \ge 0$, $1^2 \ge 0$, $(-2.5)^2 \ge 0$, …

The symbol $\exists$ is a turned letter E, for “exists”; it was introduced by Giuseppe Peano in 1897. The symbol $\forall$, an upside-down A (for “all”), appeared only in 1935, with Gerhard Gentzen. Quantifiers seem like simple words until there are two of them. Let $R(s, z)$ mean “student $s$ solved problem $z$”. The sentence $\forall z\ \exists s\ R(s, z)$ reads “every problem was solved by somebody”, and $\exists s\ \forall z\ R(s, z)$ reads “somebody solved every problem”. The only difference is the order of the symbols, but the meanings differ: in the second sentence one student covers everything, in the first each problem may have its own solver. The first follows from the second, but not the other way round.

Understanding of quantifiers is best tested by a game. A statement with quantifiers is a match between two players: the Prover moves for $\exists$ and picks a suitable object, the Refuter moves for $\forall$ and picks the most awkward one. The statement is true if the Prover has a winning strategy: that’s how truth is explained in game semantics, developed by the Finnish logician Jaakko Hintikka.

In the match for $\forall z\ \exists s$ the Prover picks a student already knowing the problem, and the choice may depend on the problem. In the match for $\exists s\ \forall z$ the choice is made blind: one student against any problem. It was the same in the game with the Sceptic in the chapter on limits: we named $N$ after hearing $\varepsilon$.

How do you negate statements with quantifiers? “Not all swans are white” means “there’s a swan that isn’t white”. For centuries Europeans thought swans were white, until at the end of the seventeenth century Dutch sailors saw black ones in Australia, and one black swan was enough.

Hence a mechanical rule: to negate a chain of quantifiers, change each $\forall$ to $\exists$, each $\exists$ to $\forall$, and negate the statement at the end. One subtlety: a condition attached to a variable, as in $\forall \varepsilon > 0$, stays in place under negation. The notation $\forall \varepsilon > 0\ \ Q$ is short for $\forall \varepsilon\ (\varepsilon > 0 \to Q)$, and its negation, by the law for implications $\lnot(A \to B) \equiv A \land \lnot B$, is $\exists \varepsilon\ (\varepsilon > 0 \land \lnot Q)$, that is, $\exists \varepsilon > 0\ \ \lnot Q$.

Now we can say honestly what “the sequence doesn’t tend to $a$” means. The definition from chapter 25 and its negation:

$$a_n \to a:\quad \forall \varepsilon > 0\ \ \exists N\ \ \forall n > N\quad |a_n - a| < \varepsilon;$$ $$a_n \not\to a:\quad \exists \varepsilon > 0\ \ \forall N\ \ \exists n > N\quad |a_n - a| \ge \varepsilon.$$

The second line is a ready-made strategy for the Sceptic: one tolerance $\varepsilon$, and after any index $N$ there’s a term outside the band. For $(-1)^n$ and $a = 1$, $\varepsilon = 1$ will do: after any $N$ there’s an odd $n$, and there $|a_n - 1| = 2 \ge 1$. In chapter 25 we found this move by guesswork; now the rule hands it to us.

A function $f$ is continuous at a point $a$ if $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x$: $|x - a| < \delta$ implies $|f(x) - f(a)| < \varepsilon$. What does it mean for $f$ to be discontinuous at $a$?

$\exists \varepsilon > 0\ \forall \delta > 0\ \exists x$: $|x - a| < \delta$ and $|f(x) - f(a)| \ge \varepsilon$ $\exists \varepsilon > 0\ \forall \delta > 0\ \exists x$: $|x - a| < \delta$ implies $|f(x) - f(a)| < \varepsilon$ $\forall \varepsilon \le 0\ \exists \delta \le 0\ \forall x$: $|x - a| \ge \delta$ implies $|f(x) - f(a)| \ge \varepsilon$ $\exists \varepsilon > 0\ \forall \delta > 0\ \forall x$: $|x - a| < \delta$ implies $|f(x) - f(a)| \ge \varepsilon$

Change $\forall \varepsilon$ to $\exists \varepsilon$, $\exists \delta$ to $\forall \delta$, $\forall x$ to $\exists x$, and negate the implication: $\lnot(A \to B) \equiv A \land \lnot B$. The result is the Sceptic’s strategy: name one tolerance, and in any window around $a$, however narrow, find a point where the value has jumped away from $f(a)$ by at least $\varepsilon$. That’s how the sign function $\operatorname{sgn} x$ behaves at zero: $\varepsilon = \frac12$ will do.

Lesson four: the grammar of proof

In chapter 0 a proof was called a chain of steps, each of which follows from the previous ones by the rules of logic. Now the rules can be named. Formally, a proof is a finite sequence of statements, each of which is an axiom, a theorem already proved, an assumption, or obtained from earlier ones by a rule of inference. The main rule of inference was known to the ancient Greek Stoics: from $A$ and $A \to B$ follows $B$. It’s called modus ponens, and its validity can be seen from a table: the formula $\bigl(A \land (A \to B)\bigr) \to B$ is a tautology. Such a sequence can be checked by a machine that doesn’t understand the meaning of the words; programs like Lean and Coq check proofs of big theorems exactly this way (chapter 60). People write more briefly, but the course of their proofs follows a few patterns, and each pattern is a tautology.

From the other side

Sometimes it’s hard to derive $B$ from $A$, but easy to derive $\lnot A$ from $\lnot B$. By the law of the contrapositive that’s the same thing.

It isn’t clear how to approach it directly. Let’s prove the contrapositive: if the conclusion is false, so is the hypothesis.

The negation of the conclusion “$a > 10$ or $b > 10$” is, by De Morgan’s law, “$a \le 10$ and $b \le 10$”. From a corner of a $10 \times 10$ square mark off a rectangle with sides $a$ and $b$. Since neither side is longer than ten, its opposite corner lies inside the square or on its boundary. The whole rectangle fits in the square: it fills the corner of the square it was marked off from. A part of a figure is no bigger than the whole, so $ab \le 10 \cdot 10 = 100$. Without the picture: $ab \le 10b \le 10 \cdot 10$, because inequalities with positive factors can be multiplied. We’ve proved $\lnot B \to \lnot A$: if $a \le 10$ and $b \le 10$, then $ab \le 100$. By the law of the contrapositive this is equivalent to the original statement.

By contradiction

By contradiction: we assume $\lnot A$ and derive a contradiction $C \land \lnot C$; the formula $(\lnot A \to (C \land \lnot C)) \to A$ is a tautology. That’s how we proved the irrationality of $\sqrt2$ (chapter 6) and the infinitude of the primes (chapter 3). Here’s an even shorter example.

Down the chain

Mathematical induction from chapter 13 is also a pattern: $\bigl(P(1) \land \forall k\ (P(k) \to P(k + 1))\bigr) \to \forall n\ P(n)$. Its rigour is best seen in a proof that only pretends to use it.

“Let’s prove that all horses are the same colour. The statement $P(n)$: in any herd of $n$ horses, all are the same colour. Base: $P(1)$ is true. Step: take a herd of $k + 1$ horses. Without the last horse there’s a herd of $k$, all the same colour; without the first, again $k$, again all the same colour. The horses in the middle belong to both herds, so they’re all the same colour.” Where’s the mistake?

In the base: $P(1)$ isn’t proved The step fails going from $k = 1$ to $k + 1 = 2$ You can’t assume $P(k)$, that’s what has to be proved There are finitely many horses in the world, so induction doesn’t apply

In a herd of two horses there are no “horses in the middle”: without the last one the first remains, without the first the last remains, and the two herds have no horses in common. The step has to work for every $k$, and at $k = 1$ it breaks, so the chain of dominoes snaps at the second. The example is attributed to George Pólya.

Show one, or prove there is one

A statement “there exists an $x$ with property $P$” is most easily proved by construction, by exhibiting such an $x$. But sometimes existence can be proved without showing the object.

The proof is flawless, but it doesn’t say which of the two pairs works. Such proofs are called non-constructive; the intuitionists, a group of twentieth-century logicians, didn’t accept them. Here, as it happens, the answer is known: by the Gelfond–Schneider theorem (1934) the number $\sqrt2^{\sqrt2}$ is transcendental, so the second case is the one that works. And there’s a very simple constructive example: $\sqrt2^{\log_2 9} = 2^{\frac12\log_2 9} = 2^{\log_2 3} = 3$, where $\log_2 9$ is irrational for the same reason as $\log_2 3$.

With a single example

The last pattern is refutation. Since $\lnot\,\forall x\ P(x) \equiv \exists x\ \lnot P(x)$, a “for all” statement is refuted by a single counterexample. But a “there exists” statement can’t be refuted by an example: its negation begins with “for all” and needs a proof. The course began with this asymmetry.

Lesson five: sets

So far we’ve learned verbs and conjunctions. Time for nouns: a mathematician almost always talks about many objects at once, “all the roots of an equation”, “the points of a circle”, “the even numbers”.

By a set we mean any collection into a whole of definite, well-distinguished objects of our perception or of our thought, which are called the elements of the set.

A set is given either by a list, $\{2, 3, 5, 7\}$, or by a property: $\{x \in \mathbb R \mid x^2 < 2\}$ is all real $x$ with $x^2 < 2$, that is, the interval $(-\sqrt2, \sqrt2)$. Order and repetition in a list don’t matter: $\{1, 2, 2\} = \{2, 1\}$, they have the same elements.

The empty set is a subset of every $A$: the condition $\forall x\ (x \in \varnothing \to x \in A)$ holds, because the hypothesis $x \in \varnothing$ is always false, and anything follows from a falsehood. And there’s only one empty set: two empty sets have the same elements, namely none.

Operations on sets are the connectives of logic in new clothes: $x \in A \cup B$ means $x \in A \lor x \in B$, intersection is “and”, complement is “not”. Every law of logic immediately gives a law for sets, and Euler circles are a truth table drawn in the plane.

Let’s draw both sides of the first law and check that the same thing is shaded. Each of the four regions of the picture is a row of the table from lesson one.

Inside the enclosing rectangle $U$ are two circles, $A$ and $B$. They divide $U$ into four regions: in both circles, only in $A$, only in $B$, outside both. The union $A \cup B$ is three regions out of four: everything that’s in at least one circle. Its complement $(A \cup B)^{c}$ is the remaining fourth region, outside both circles. Now the right-hand side. $A^{c}$ is everything outside the circle $A$; hatch it with slanting lines. $B^{c}$ is everything outside the circle $B$; hatch it the other way. The intersection $A^{c} \cap B^{c}$ is where the hatchings cross: outside both circles. It’s the same region as in the third step. The regions coincide however the circles are placed: move the centres, and check that it works for circles with no points in common too. In the language of elements: $x \in (A \cup B)^{c} \iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in A^{c} \cap B^{c}$ by De Morgan’s first law for statements. The second law follows in the same way from the second.

How many rows of the truth table of the formula $A \lor B \lor C \lor D$ contain T? In other words, how many of the sixteen regions does the union of four sets in general position cover?

There are $2^4 = 16$ rows in all. The disjunction is false only where all four variables are false: one row. The other $16 - 1 = 15$ rows give T.

Lesson six: a function is a set of pairs

In chapter 9 a function was a rule: each $x$ is assigned exactly one $y$. But what is a “rule”? Set theory gives an unexpected answer: a function can be identified with its graph.

There’s no “rule” in the definition: a map is a list of pairs in which each element of $A$ appears first exactly once, and it needn’t be given by a formula. The three main properties of maps are about the arrows leading from $A$ to $B$.

You won’t manage to build an injection from five dots into four: that’s the pigeonhole principle, five pigeons in four holes. A bijection exists only between sets of the same size, and only a bijection can be run backwards.

For infinite sets this is false, and that’s where the next chapter begins. The map $n \mapsto n + 1$ from $\mathbb N$ to $\mathbb N$ is injective, but no arrow leads into one. And $n \mapsto \lceil n/2 \rceil$ (half, rounded up) hits every natural number, but one is hit twice, from $1$ and from $2$.

How many surjections are there from the set $\{1, 2, 3\}$ onto the set $\{a, b\}$?

There are $2^3 = 8$ maps in all: each of the three elements independently chooses $a$ or $b$ (the rule of product). Only two of them aren’t surjective: all to $a$ and all to $b$. That leaves $8 - 2 = 6$. None of them is an injection: three elements can’t have two different images.

Lesson seven: equal in different ways

The fractions $\frac12$, $\frac24$ and $\frac36$ are written differently, but they’re one number (chapter 5). A clock shows the same thing at 3 in the morning and at 15:00. The device is the same: objects are declared “the same” if they agree in something important, and you work with whole groups.

“Having the same remainder on division by $12$” is an equivalence relation on the integers. “Divides” isn’t: $2$ divides $4$, but $4$ doesn’t divide $2$, so there’s no symmetry. “Differing by less than one” isn’t either: $0 \sim 0.6$ and $0.6 \sim 1.2$, but $0$ and $1.2$ differ by more than one, so transitivity fails. An equivalence, on the other hand, cuts a set into pieces with nothing left over and no overlaps.

Now we can say what a remainder is and what a fraction is without the words “the same thing written differently”. The classes of integers modulo $n$ are the elements of $\mathbb Z_n$ from the chapter on remainders: $\mathbb Z_{12}$ is twelve classes, the numbers on a clock face. And a positive rational number is a class of pairs of natural numbers under the relation $(p, q) \sim (p', q') \iff pq' = p'q$: the pairs $(1, 2)$, $(2, 4)$, $(3, 6)$, … form one class, and that class is $\frac12$. On the grid of points in the plane each class lies on a ray from the origin: a picture we’ll need in the next chapter.

How many different equivalence relations are there on the set $\{a, b, c\}$?

By the theorem on splitting, an equivalence relation is the same as a partition of the set into classes: knowing the classes, we know who is equivalent to whom, and vice versa. A three-element set has five partitions: everyone in one class; each in their own; and three ways to single out a pair, $\{a, b\}\{c\}$, $\{a, c\}\{b\}$, $\{b, c\}\{a\}$. Answer: $5$.

Lesson eight: the word that breaks the dictionary

Cantor allowed “any collection” of objects to be called a set. Let’s take this seriously. The set of all sets, if it exists, is itself a set and so lies in itself. The set of all teacups isn’t a teacup and doesn’t lie in itself. Let’s gather together all the sets that don’t lie in themselves:

$$R = \{x \mid x \notin x\}.$$

This is the conversation with the islander who said “I am a knave”. Let’s ask about $R$ itself: does it lie in itself?

Suppose $R$ exists. About any set you can ask whether it lies in $R$, and about $R$ itself too. By the law of the excluded middle, either $R \in R$ or $R \notin R$. Suppose $R \in R$. Only sets that don’t contain themselves lie in $R$, so $R \notin R$. A contradiction. Suppose $R \notin R$. Then $R$ is a set that doesn’t contain itself, and by definition all such sets lie in $R$. So $R \in R$. A contradiction again. Both cases are impossible, and there are no others. So the assumption is false: there’s no such set. More briefly: the definition of $R$ gives $R \in R \leftrightarrow R \notin R$, and a statement of the form $A \leftrightarrow \lnot A$ is false in every row of the table.

Bertrand Russell found this contradiction in 1901; Ernst Zermelo in Göttingen had stumbled on it a little earlier but didn’t publish. In June 1902 Russell wrote about it to Gottlob Frege, who was finishing the second volume of his Basic Laws of Arithmetic, an attempt to derive the whole of arithmetic from logic. Frege’s axioms allowed everything with some property to be gathered into a set, and in his system the set $R$ existed. The volume came out in 1903 with an afterword:

Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished.

In the popular version, which Russell himself retold, the paradox goes like this: the village barber shaves those and only those villagers who don’t shave themselves. Does he shave himself? Both answers are impossible, but the conclusion is simple: there’s no such barber. With sets the conclusion is the same, and the crisis is that the old rules allowed such a set to be built.

The way out was found by the same Zermelo. In 1908 he proposed axioms under which a set can’t be gathered “from everything in the world” but can only be cut out of one that already exists.

The axiom of separation makes its move against the paradox modestly: the contradictory set isn’t forbidden, there’s simply nothing to build it from. Today the foundation of mathematics is the ZFC system: Zermelo’s axioms, supplemented in 1922 by Abraham Fraenkel and Thoralf Skolem. The letter C in the name is a reminder that among them is the axiom of choice, which is often considered separately from the rest. Here are all nine axioms in outline, in words:

Remarkably, almost all of mathematics needs nothing more. Numbers too are built from sets: in 1923 John von Neumann proposed taking the empty set as zero, $\{\varnothing\}$ as one, $\{\varnothing, \{\varnothing\}\}$ as two, and in general $n + 1 = n \cup \{n\}$. Here it’s convenient to start the natural numbers at zero; in many school textbooks zero isn’t counted as a natural number, and that’s a matter of convention, not truth. The principle of induction, which Peano declared an axiom of arithmetic in 1889, becomes a theorem in ZFC. From pairs of natural numbers the integers and fractions are built (lesson seven), from fractions the real numbers, and from them functions, spaces, probabilities. This whole course grows out of the nine rows of the table.

An exam on the island

A grammar is learned not only by reading but by exercises. The trainer has three levels: count the rows of a truth table, choose the correct negation of a statement with quantifiers, and sort out the island’s inhabitants.

Where next

For finite sets we proved: if $A$ and $B$ have the same number of elements, an injection from $A$ to $B$ is necessarily a bijection. For the natural numbers this is false: the shift $n \mapsto n + 1$ maps $\mathbb N$ one-to-one onto its own part $\{2, 3, 4, \dots\}$. So an infinite set has as many elements as a part of itself? Galileo noticed this back in 1638 (there are as many squares $1, 4, 9, 16, \dots$ as there are natural numbers) and decided that the words “more” and “fewer” don’t apply to infinities. Georg Cantor decided otherwise: to call sets the same size if there’s a bijection between them, and see what happens. What happened is that infinities come in different sizes. Can the natural numbers be compared with the points of a segment, and is there a largest infinity? Three people argue about it in the next chapter.