Mathematical Worlds: Logic and infinity

The edge of reason: paradoxes, logic and infinity

A paradox is an argument that starts from things that seem obviously true and ends somewhere that seems obviously false. For 2,500 years, paradoxes have been the places where mathematics found out it was missing something.

Zeno's runner who can never finish, a hotel that is full yet always has room, infinities of different sizes, a set that both contains itself and does not, and a sentence that says it cannot be proved. Each one forced mathematicians to invent something new: limits, set theory, formal logic, and the limits of proof itself.

Everyone High school University Game

½ + ¼ + ⅛ + … : infinitely many pieces, one finite square.

Chapter 1 Everyone Game

What is a paradox?

The philosopher W. V. O. Quine sorted paradoxes into three kinds, and the difference matters.

  • A veridical paradox has a surprising conclusion that is actually true. In a room of just 23 people, two probably share a birthday.
  • A falsidical paradox has a false conclusion because of a hidden mistake. A "proof" that 1 = 2 always divides by zero somewhere.
  • An antinomy reaches a contradiction by reasoning that seems completely correct. "This sentence is false" is true if it is false and false if it is true. Antinomies are the serious ones: they show that some accepted way of reasoning is broken.

Test yourself. For each puzzle below, decide which kind it is, then find the trick.

Chapter 2 Everyone High school

Zeno: can Achilles ever catch the tortoise?

Around 450 BCE, Zeno of Elea argued that motion is impossible. We know his arguments mainly through Aristotle, who quoted them in order to refute them.

Achilles and the tortoise. Achilles runs ten times as fast as a tortoise, which starts 100 metres ahead. When Achilles reaches the tortoise's starting point, the tortoise has moved 10 m further. When he covers those 10 m, it has moved 1 m more. And so on: every time Achilles reaches where the tortoise was, it has moved on. There are infinitely many stages, so how can he ever pass it?

The resolution: an infinite sum can be finite

The stages are infinitely many, but they get shorter and shorter, and so do the times they take. Achilles' distances add up to

100 + 10 + 1 + 0.1 + ⋯ = 111.111… = 10009 metres

which is exactly where he catches the tortoise. Zeno assumed that infinitely many steps must take forever. The mathematics to answer him properly came 2,000 years later: Augustin-Louis Cauchy and Karl Weierstrass in the 19th century defined the limit of a sum precisely. For a geometric series with ratio |r| < 1:

a + ar + ar² + ar³ + ⋯ = a1 − r

Zeno had other paradoxes too. The dichotomy: to cross a room you must first cross half, then half of what is left, and so on, so you can never even start. The arrow: at each single instant a flying arrow occupies one place and is not moving, so when is it moving? The answer to the arrow is the derivative: velocity at an instant is a limit of average velocities over shorter and shorter times, defined in the calculus of Newton and Leibniz.

Philosophers still argue about whether limits answer everything Zeno asked. In 1954 James Thomson imagined a lamp switched on and off at 1 minute, ½ minute, ¼ minute, … before noon. Is it on or off at noon? The sum of the times is finite, but the sequence on, off, on, off, … has no limit. Such "supertasks" are still debated.

Chapter 3 High school University

Infinite sums that behave badly

Zeno's sum shrinks fast enough to be finite. Some sums shrink, yet still grow without limit. Others change their total if you merely change the order of the terms.

The harmonic series and the leaning tower

The terms of 1 + ½ + ⅓ + ¼ + ⋯ shrink to zero, but the sum is infinite. Nicole Oresme proved it around 1350: group the terms as ½ + (⅓ + ¼) + (⅕ + … + ⅛) + ⋯, and each group is more than ½. You can feel this with books or blocks: stack them at the edge of a table, each shifted as far as it can go. With n blocks the top one can overhang the edge by ½(1 + ½ + ⋯ + 1/n) block lengths, which grows without limit. With enough blocks, the top one can be as far out as you like.

Each block's centre of mass sits exactly above the edge of the block below; the whole stack's centre of mass sits above the table's edge. Any further and it topples.

Riemann's rearrangement theorem

The alternating series 1 − ½ + ⅓ − ¼ + ⋯ adds up to ln 2 ≈ 0.693. But Bernhard Riemann proved that by changing only the order of its terms, you can make it add up to any number you like, or to infinity. The trick: take positive terms until you pass your target, then negative terms until you fall below it, and repeat. Both the positive and the negative parts are infinite, so you never run out, and the steps shrink, so you close in on the target. Choose a target:

This only happens for conditionally convergent series, whose positive and negative parts each add up to infinity. If the sum of the absolute values is finite, every order gives the same total. "Infinite sum" is a limit, not ordinary addition, and it does not always obey ordinary addition's rules.

Chapter 4 Everyone Game

Hilbert's hotel: full, but always room for more

David Hilbert described it in a 1924 lecture, and George Gamow made it famous. A hotel has infinitely many rooms, numbered 1, 2, 3, …, and every room is taken. A new guest arrives. Can the manager find her a room, without making anyone share or leave?

Yes: ask the guest in room n to move to room n + 1. Everyone still has a room, and room 1 is free. Try the manager's job below, from one new guest up to infinitely many coaches.

Galileo had already noticed the puzzle in 1638. There seem to be fewer square numbers (1, 4, 9, 16, …) than whole numbers, yet pairing every n with n² matches them perfectly. Galileo concluded that "greater", "less" and "equal" do not apply to infinite collections. Two and a half centuries later, Georg Cantor concluded the opposite: they do apply, if you define them by matching.

Chapter 5 High school University Game

Cantor: some infinities are bigger than others

Two collections have the same size if their members can be paired off one to one, with nothing left over. This is how a child who cannot count can still tell that there are as many cups as saucers. Georg Cantor applied it to infinite sets, starting in 1874, and found a whole ladder of infinities.

A set that can be paired with 1, 2, 3, … is called countable, and its size is written ℵ0 (aleph-null). The even numbers are countable, and so are all the integers. Surprisingly, so are all the fractions: arrange them in a grid and walk through it in a zigzag, skipping repeats like 2/4 = 1/2.

The diagonal argument: the real numbers cannot be counted

In 1891 Cantor gave a famously short proof that infinite sequences of 0s and 1s (or, equivalently, the real numbers) cannot be listed. Suppose someone hands you a list that claims to contain them all. Build a new sequence: its 1st digit is the opposite of the 1st sequence's 1st digit, its 2nd digit the opposite of the 2nd sequence's 2nd digit, and so on down the diagonal. The new sequence differs from every sequence in the list somewhere, so it is not in the list. No list can be complete.

The game: you are the list maker. Fill in the rows below (tap a digit to flip it) and try to make a list that Cantor cannot beat. Then press the button and watch him build a sequence you missed.

The same argument proves Cantor's theorem: every set is strictly smaller than the set of all its subsets. So there is no largest infinity: ℵ0 < 2ℵ0 < 22ℵ0 < ⋯

Is there an infinity strictly between the whole numbers and the real numbers? Cantor believed not: this is the continuum hypothesis, first on Hilbert's famous 1900 list of problems. The answer is astonishing. Kurt Gödel showed in 1940 that it cannot be disproved from the standard axioms of set theory, and Paul Cohen showed in 1963 that it cannot be proved either. It is independent: the usual axioms do not decide it.

Cantor's ideas met fierce resistance; Leopold Kronecker opposed them, and Cantor suffered long periods of depression. Hilbert defended him in 1926: "No one shall expel us from the paradise that Cantor has created."

Chapter 6 High school University

Russell's paradox: the set that breaks set theory

By 1900 it seemed that all of mathematics could be built from sets. Gottlob Frege had spent years writing that foundation down, using one natural rule: any property defines a set, the set of things with that property.

In June 1902, as Frege's second volume was going to press, a letter arrived from the young Bertrand Russell. Some sets are members of themselves (the set of all sets with more than three members has more than three members). Most are not (the set of cats is not a cat). Russell asked: what about

R = { x : x ∉ x },   the set of all sets that are not members of themselves?

If R is a member of itself, then by its own definition it is not. If it is not, then it qualifies, so it is. Either way, a contradiction. Frege added an appendix: "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." Ernst Zermelo had found the same contradiction a little earlier, but did not publish it.

The barber and other disguises

Russell later gave a popular version. In a village, the barber shaves exactly those men who do not shave themselves. Who shaves the barber? Here the answer is easy: no such barber can exist. Russell's paradox is harder, because the "barber" R was supposed to exist by a rule everyone accepted.

A version with words, found by Kurt Grelling and Leonard Nelson in 1908: call an adjective autological if it describes itself ("short" is short, "English" is English), and heterological if it does not ("long" is not long). Try sorting some words:

How mathematics was repaired

  • Types. Russell's answer: sort objects into levels, so a set may contain only things of a lower level. "x ∈ x" then cannot even be written. Whitehead and Russell's Principia Mathematica (1910–1913) built mathematics this way, and needed hundreds of pages to reach a proof that 1 + 1 = 2.
  • Axioms. Zermelo's answer (1908), refined by Abraham Fraenkel and Thoralf Skolem into the system now called ZFC. A property no longer creates a set from nothing; it can only select members from a set you already have. R is never formed. ZFC is the foundation most mathematicians use today.

But how do we know ZFC itself contains no hidden contradiction? That question leads to Gödel.

Chapter 7 Everyone High school Game

Logic, liars and truth-tellers

Logic studies which conclusions follow from which statements, whatever the statements are about. Its basic tool is the truth table: list every way the parts could be true or false, and work out the whole.

Type a formula with letters p, q, r and the connectives not (¬), and (∧), or (∨), -> (if … then) and <-> (if and only if). A formula that is true in every row is a tautology: true by its form alone.

"If p then q" is false only when p is true and q is false. So "if pigs fly, then 2 + 2 = 5" counts as true: one of the classic surprises of logic, the paradoxes of material implication.

Game: knights and knaves

On Raymond Smullyan's island, knights always tell the truth and knaves always lie. Each islander below makes a statement. Decide who is who: tap a name to switch between knight and knave, then check. Every puzzle has exactly one solution.

The liar

Now suppose an islander says: "I am a knave." A knight cannot say it (it would be a lie), and a knave cannot say it either (it would be true). On Smullyan's island nobody can say it. In ordinary language, though, anyone can say "This sentence is false." If it is true, it is false; if false, true. This is the liar paradox, attributed to Eubulides of Miletus in the 4th century BCE.

Self-reference is not needed. In 1913 Philip Jourdain wrote a card: on one side, "The sentence on the other side is true"; on the other, "The sentence on the other side is false." Neither sentence talks about itself, yet together they trap you. Alfred Tarski's response (1933) was that a language cannot define its own truth: "true" must be defined in a richer language that talks about the first one.

Chapter 8 University

Gödel: the sentence that cannot be proved

After the crisis of the paradoxes, David Hilbert proposed a programme: write all of mathematics as a formal system of axioms and rules, and then prove, by safe finite reasoning, that the system can never produce a contradiction. In 1931 a 25-year-old Austrian, Kurt Gödel, showed that this is impossible.

Gödel's idea was to turn the liar into mathematics. Replace "this sentence is false" by

G:   "This sentence cannot be proved."

If the system could prove G, it would prove something false. So, if the system only proves true things, G is not provable, which is exactly what G says: G is true but unprovable. There is no contradiction this time, only a gap.

How can a sentence talk about itself? Gödel numbering

The hard part is making a statement of arithmetic refer to statements. Gödel gave every symbol a number and coded a formula, a list of symbols s1s2s3…, as the single number 2s1 · 3s2 · 5s3 ⋯, using the primes in order. Unique factorisation means the formula can always be read back. Statements about formulas and proofs then become statements about numbers. Try it:

Alphabet: 0=1, S (successor, "plus one")=2, +=3, × or *=4, ==5, (=6, )=7, x=8, ¬ or ~=9, ∀ or A=10. So S0+S0=SS0 says 1 + 1 = 2.

Gödel's incompleteness theorems (1931)

  1. First theorem. Any consistent formal system strong enough to do basic arithmetic, whose axioms can be listed by a computer, contains true statements about whole numbers that it cannot prove.
  2. Second theorem. Such a system cannot prove its own consistency. Hilbert's programme, in its original form, cannot succeed.

In 1936 Alan Turing used the same diagonal idea for computers: no program can decide, for every program and input, whether it will eventually stop. Suppose one could; build a program that asks it about itself and then does the opposite. This is Cantor's diagonal argument, Russell's paradox and the liar again, now as a theorem about machines.

The Berry paradox (published by Russell in 1906, who credited the Oxford librarian G. G. Berry): "the smallest positive integer not definable in under sixty letters" has just been defined in under sixty letters. George Boolos turned it into a short proof of Gödel's first theorem in 1989.

Chapter 9 Everyone High school Game

Paradoxes of chance

Probability is where intuition fails most often. These are veridical paradoxes: the surprising answers are correct, and you can check them by experiment.

Game: the Monty Hall problem

Behind one of three doors is a car; behind the others, goats. You pick a door. The host, who knows where the car is, opens a different door with a goat behind it, and offers you a switch. Should you switch? When Marilyn vos Savant answered "yes, it doubles your chances" in Parade magazine in 1990, thousands of readers, including mathematicians, wrote in to say she was wrong. She was right. Play, then let the computer play 1,000 times.

Why: your first pick is right 1 time in 3. The host's door never changes that. So the other closed door hides the car the remaining 2 times in 3.

The birthday paradox

How many people do you need in a room for a better-than-even chance that two share a birthday? Only 23. The probability that all n birthdays differ is (365/365)(364/365)⋯((365 − n + 1)/365), and it falls below ½ at n = 23. The surprise is that you are not asking about your birthday: with 23 people there are 253 pairs.

Bertrand's paradox: what does "random" mean?

In 1889 Joseph Bertrand asked: draw a chord of a circle "at random". What is the probability that it is longer than the side of the triangle inscribed in the circle? Here are three natural ways to choose, giving three different answers. The paradox teaches that "at random" means nothing until you say exactly how.

Simpson's paradox: when the whole contradicts its parts

A real example from a 1986 study of kidney-stone treatments (Charig and colleagues). Treatment A did better than treatment B for small stones, and better for large stones, yet worse overall.

Treatment ATreatment B
Small stones93% (81 of 87)87% (234 of 270)
Large stones73% (192 of 263)69% (55 of 80)
All patients78% (273 of 350)83% (289 of 350)

There is no arithmetic mistake. Treatment A was mostly given for large stones, the hard cases, and B mostly for small ones. Combining the groups mixes up the treatment with the difficulty of the case. Simpson's paradox is why medical statisticians insist on asking how patients were assigned to treatments, and why randomised trials matter.

Chapter 10 High school University

Impossible shapes

Gabriel's horn: you can fill it, but not paint it

In 1643 Evangelista Torricelli spun the curve y = 1/x, for x ≥ 1, around the x-axis. The horn it makes is infinitely long. Its volume is finite, exactly π, but its surface area is infinite. So it holds a finite amount of paint, yet that paint could never cover its inside surface. The catch: a layer of paint has a thickness, and the horn soon becomes narrower than any fixed thickness.

Volume from 1 to a: π(1 − 1/a), which approaches π. Surface area: more than 2π ln a, which grows without limit.

The Banach–Tarski paradox

In 1924 Stefan Banach and Alfred Tarski proved that a solid ball can be cut into finitely many pieces (five are enough) which can be moved by rotations and shifts, without stretching, and reassembled into two balls, each the same size as the original.

This does not break physics: the pieces are infinitely scattered "clouds" of points that have no volume at all, in the sense that no consistent volume can be assigned to them. Their existence depends on the axiom of choice, which says you can pick one element from each of infinitely many sets at once, even without a rule for choosing. The axiom is part of ZFC, it is used throughout modern mathematics, and Banach–Tarski is the price. Mathematicians mostly accept it: the paradox shows that "volume" only makes sense for reasonable sets.

More impossible shapes: the Koch snowflake has an infinite perimeter around a finite area, and the Hilbert curve fills a square. See The world of fractals.

Chapter 11

What the paradoxes taught us

ParadoxWhat it revealed
Zeno (c. 450 BCE)Infinite processes need limits; resolved by 19th-century analysis.
Galileo (1638), Hilbert's hotel (1924)An infinite set can be matched with part of itself; size of infinite sets is defined by one-to-one pairing.
Riemann's rearrangement (1850s)Infinite sums are limits, not ordinary addition; order can matter.
Cantor's diagonal (1891)There are different sizes of infinity, and no largest one.
Russell (1902)"Every property defines a set" is contradictory; led to type theory and ZFC.
Liar, Berry, GrellingSelf-reference about truth and definability needs care; Tarski: truth cannot be defined inside the same language.
Gödel (1931), Turing (1936)Any rich enough formal system has true but unprovable statements; some problems no computer can decide.
Continuum hypothesis (1940, 1963)Some natural questions are independent of the standard axioms.
Monty Hall, birthdays, Bertrand, SimpsonProbability needs precise models; intuition misleads, experiment and careful definitions do not.
Banach–Tarski (1924)The axiom of choice creates sets that have no volume.

Further reading

  • Eugene P. Northrop, Riddles in Mathematics: A Book of Paradoxes (1944). The classic popular book on mathematical paradoxes.
  • Martin Gardner, Aha! Gotcha: Paradoxes to Puzzle and Delight (1982).
  • Raymond Smullyan, What Is the Name of This Book? (1978). Knights, knaves and, at the end, Gödel.
  • Ernest Nagel and James R. Newman, Gödel's Proof (1958). A short, clear account of the incompleteness theorems.
  • Douglas Hofstadter, Gödel, Escher, Bach (1979).
  • Apostolos Doxiadis and Christos Papadimitriou, Logicomix (2009). Russell's search for foundations, as a graphic novel.
  • R. M. Sainsbury, Paradoxes (3rd ed., 2009). A philosophical treatment for university students.