Math's Fundamental Flaw

Math’s Fundamental Flaw

Source: Math’s Fundamental Flaw, Veritasium, 33:59, uploaded 2021-05-22, playlist index 1478.

Mathematics has a boundary at its foundations. Veritasium traces it from the question of whether every true statement can be proved to the invention of the modern computer. The explanation moves through infinity, self-reference, a barber, a very large book, and a machine that cannot always tell whether another machine will stop.

The Game of Life and the first undecidable question

The video begins with the Twin Prime Conjecture. Twin primes are pairs such as 11 and 13 or 17 and 19, with one number between them. Prime numbers become rarer as the number line continues, so the conjecture that infinitely many such pairs exist remains open. No one has proved it true or false. Veritasium places that problem beside a stronger result: in any mathematical system capable of basic arithmetic, some true statements will be impossible to prove. The Twin Prime Conjecture might be one of them, although nobody knows whether it is.

Conway’s Game of Life gives the abstract problem a visible form. John Conway created it in 1970 and died in 2020 from COVID-19. The game runs on an infinite square grid whose cells are either alive or dead. A dead cell with exactly three live neighbours becomes alive. A live cell with fewer than two or more than three live neighbours dies. The rules apply to each generation without further intervention, which led Conway to call it a zero-player game.

Simple rules produce several kinds of behaviour. Some patterns remain fixed. Some oscillate between states. A glider moves across the grid. Other patterns disappear, whilst a few keep generating cells without limit. The natural question is whether a given starting pattern will settle, travel, die out, or grow forever.

That question is undecidable. No algorithm can examine every possible starting pattern and always give the right answer in a finite time. Running the pattern for a million generations can show what has happened so far. It cannot establish that the pattern will stop after two million generations, or after a billion, or after a number as large as a googolplex. The obstacle lies in the system’s possible behaviour, so more computation cannot resolve it.

Conway’s game is one example among many. Veritasium names Wang tiles, quantum systems, airline ticketing systems, and Magic: The Gathering. To explain why such unrelated systems share this limit, the video goes back to the crisis that changed mathematics in the nineteenth century.

Cantor and the sizes of infinity

In 1874, Georg Cantor published the paper that helped establish set theory. A set is a defined collection of things, such as the two shoes on a person’s feet, all the planetariums in the world, or the empty set. Cantor wanted to compare two sets of numbers: the natural numbers, meaning 1, 2, 3, 4 and so on, and the real numbers between zero and one. The real numbers include fractions such as one third, irrational numbers such as pi and the square root of two, and every number that can be written as an infinite decimal.

Both collections are infinite, so it is tempting to treat them as equal in size. Cantor tested that idea by imagining a complete list of the real numbers between zero and one. Each real number would sit beside one natural number, which would act as its index. The list would have to contain every real number exactly once.

Cantor then constructed a new real number from the diagonal of the list. He changed the first digit of the first number, the second digit of the second number, and the third digit of the third number, continuing through the list. If a digit was nine, he changed it to eight so that the result stayed simple. The new number differs from the first listed number in its first decimal place, from the second in its second decimal place, and so on. It therefore cannot appear anywhere in the supposed complete list.

This is Cantor’s diagonalisation proof. There are more real numbers between zero and one than natural numbers, even though both collections are infinite. Cantor called the natural-number infinity countable and the real-number infinity uncountable. Larger uncountable infinities exist beyond that one.

The discovery disturbed a discipline that had treated Euclid’s Elements as its foundation for roughly two thousand years. Around the turn of the nineteenth century, Nikolai Lobachevsky and Carl Friedrich Gauss had developed non-Euclidean geometries. The concept of a limit, which calculus depends on, also turned out to need a more careful definition. Cantor’s work added a new problem by showing that infinity had several sizes.

Mathematicians split over what this meant. Intuitionists held that mathematics was a creation of the human mind and that Cantor’s infinities had no independent existence. Henri Poincaré predicted that later generations would regard set theory as a disease from which they had recovered. Leopold Kronecker called Cantor a scientific charlatan and worked against his appointment to a university post.

The formalists took the opposite view. They believed that mathematics could gain secure foundations through set theory and strict logical rules. David Hilbert became their informal leader. He had worked across many areas of mathematics, had nearly beaten Einstein to general relativity, and had developed concepts that later mattered to quantum mechanics. Hilbert accepted Cantor’s work and wanted to use a formal system of proof to settle the disorder that had appeared in mathematics. “No one shall expel us from the paradise that Cantor has created,” he declared.

Self-reference and the limits of a formal system

Bertrand Russell found a problem in 1901. If a set can contain anything, it can contain another set, or itself. The set of all sets contains itself. That invites a more troublesome collection: the set of all sets that do not contain themselves. Call it R. If R contains itself, its definition says that it must not. If it does not contain itself, its definition requires it to contain itself. The statement creates a contradiction as soon as it refers to its own membership.

Russell later described the same structure through a village barber. The barber must shave all and only the men who do not shave themselves, and the barber lives in the village. If he shaves himself, he belongs among the men he must leave alone. If he does not shave himself, he belongs among the men he must shave. The barber’s rule cannot determine what the barber does.

Zermelo and other mathematicians associated with Hilbert’s school restricted the idea of a set to remove these paradoxes. The collection of all sets ceased to count as a set, as did the collection of all sets that do not contain themselves. The restriction removed this particular contradiction. Self-reference continued to return in less obvious forms.

Hilbert wanted a proof system built from axioms, inference rules, and a symbolic language whose operations could be checked exactly. An axiom is accepted as true. The inference rules derive new statements from existing ones whilst preserving truth. Ordinary claims could be translated into the formal language. “If you drop a book, it will fall” becomes a relation of the form A then B. “No human is immortal” takes a corresponding symbolic form.

Bertrand Russell and Alfred North Whitehead built such a system in Principia Mathematica. The three volumes, published between 1910 and 1913, contain nearly 2,000 pages of dense notation. It takes 762 pages to reach a complete proof that one plus one equals two, followed by the authors’ dry note that the proposition is occasionally useful. A fourth volume was planned and never completed.

The system’s size was part of its appeal. Formal notation removes the ambiguity of ordinary language and makes it possible to reason about the system itself. Hilbert wanted answers to three questions:

Completeness: Can every true statement be proved from the axioms?
Consistency: Does the system avoid contradictions, so that it cannot prove both a statement and its negation?
Decidability: Is there an algorithm that can always determine whether a statement follows from the axioms?

Hilbert believed that the answer to each question would be yes. At a conference in 1930, he ended a speech with the words “We must know. We will know.” He had the sentence placed on his grave. The day before, at a small meeting at the same conference, the 24-year-old logician Kurt Gödel had explained that the answer to the first question was already no.

Gödel’s number card

Gödel’s proof turns statements about a formal system into statements inside that system. He assigns a unique number to each basic symbol. The symbol for “not” might receive one number, “or” another, and “if then” a third. Numbers themselves receive symbols too. Zero has its own Gödel number, while one is written as the successor of zero, and two as the successor of the successor of zero. The notation is cumbersome because the system needs a way to represent both mathematical objects and the symbols used to describe them.

Sequences of symbols also receive numbers. For the equation zero equals zero, Gödel takes the first prime numbers and raises each to the power of the corresponding symbol’s number. With the numbers used in the video, the result is 2⁶ × 3⁵ × 5⁶, or 243 million. Prime factorisation recovers the sequence of symbols, so every possible expression has a unique Gödel number.

The formal system can therefore contain a statement about the statement whose Gödel number is g. Gödel constructs one that says: “There is no proof of the statement with Gödel number g.” The statement’s own Gödel number is g, so its content is that it has no proof.

If the statement is false, a proof exists. That proof would establish that no proof exists, making the system inconsistent. If the statement is true, it has no proof, so the system contains a true statement that cannot be proved. Either way, a consistent system capable of basic arithmetic is incomplete. Truth and provability have separated.

The video compares the structure to a self-referential exchange from The Office: Jim is his own worst enemy, so the enemy of Jim is his own friend, which turns Jim’s friend into an enemy again. The television joke carries the shape of Gödel’s construction without carrying its mathematics.

Gödel’s second incompleteness theorem closes Hilbert’s second route to safety. A consistent formal system capable of arithmetic cannot prove its own consistency. A system may be consistent and incomplete, yet it cannot produce a proof from inside itself that no contradiction will ever appear. The formal system has to rely on a stronger system for that assurance, which then faces the same problem at its own level.

Turing and the halting problem

Alan Turing addressed Hilbert’s third question in 1936. At the time, a computer was a person, often a woman, who carried out long calculations. Turing imagined a machine simple enough to analyse and powerful enough to perform any computable operation. It has an infinitely long tape divided into squares, a read-write head, and an internal state. At each step it can overwrite a zero or one, move left or right, or halt.

The machine’s instructions form a programme. The programme tells it what to do for each symbol and internal state. A Turing machine can simulate any algorithm given enough time, from addition and subtraction to the algorithm that runs YouTube. That generality lets Turing translate Hilbert’s question into a question about whether programmes stop.

Some machines halt when their work is finished. Others enter an infinite loop. Turing asked whether an algorithm could examine any machine and input, then always decide whether that machine would halt. Assume such a machine H exists. It receives a programme and its input, simulates the result, and prints either “halts” or “never halts”.

Turing modifies H into a new machine, H+. When H says “halts”, H+ enters an infinite loop. When H says “never halts”, H+ halts at once. Now give H+ its own code as its input. If H says that H+ will never halt, H+ halts. If H says that H+ will halt, H+ loops. Every answer is wrong, so a machine like H cannot exist.

This is the halting problem. No general algorithm can determine whether an arbitrary Turing machine will halt. Turing connects it back to mathematical proof by describing a programme that lists theorems from a set of axioms. The programme checks each theorem for the Twin Prime Conjecture. If it finds a proof, it halts. If the conjecture has no proof, it continues forever. A solution to the halting problem would therefore decide the conjecture and every similar question. Since the halting problem has no solution, mathematics is undecidable in the general case.

The spectral gap and Turing-complete systems

The limit also appears in physics. A many-body quantum system has a ground state and a first excited state. The energy difference between them is the spectral gap. A system with no gap has energy levels that run continuously down to the ground state, and at low temperatures it can undergo phase transitions. A system with a gap lacks the energy needed to cross it.

In 2015, Toby Cubitt, David Pérez-García, and Michael Wolf proved that deciding whether an arbitrary quantum system has a spectral gap is undecidable. Even a complete description of the microscopic interactions between a material’s particles cannot always determine its macroscopic properties. The video presents that result as a physical version of the halting problem.

A Turing-complete system can perform every computation that a Turing machine can perform. Its power brings an analogue of the halting problem with it. For Wang tiles, the question is whether a set of tiles can cover the plane forever. For a complex quantum system, it is the spectral gap. For the Game of Life, it is whether a pattern eventually stops.

The list extends to programming languages, airline ticketing systems, Magic: The Gathering, PowerPoint slides, and Excel spreadsheets. A single Turing-complete language would be enough in principle because any other Turing-complete system can simulate it. Conway’s Game of Life even contains a Turing machine inside itself. Since the game can simulate a Turing machine, it can simulate the game itself. The video shows the Game of Life running on the Game of Life.

The computer in front of us

Hilbert’s programme still produced the foundations of modern computation. Turing used his ideas about machines during the Second World War at Bletchley Park, where his team built calculating machines to help crack Nazi codes. Veritasium cites an estimate that the intelligence gathered from decrypted messages shortened the war by two to four years. The video then connects Turing’s designs with ENIAC, describing it as the first true programmable electronic computer and naming Turing and John von Neumann in that account.

Gödel’s later life was marked by severe anxiety about being poisoned. He stopped eating and died from starvation. Hilbert died in 1943 with “We must know. We will know” on his grave. Turing was convicted by the British government in 1952 for homosexual acts, lost his security clearance, and was forced to undergo hormone treatment. He died by suicide in 1954, before he could see how far his ideas would travel.

Modern computers grew from a question about proof systems, and that question arose from self-reference. Hilbert wanted mathematics to be complete, consistent, and decidable. The attempts to secure those properties revealed a permanent boundary: some mathematical truths cannot be proved, some systems cannot certify their own consistency, and no algorithm can settle every question that follows from a set of axioms.

Veritasium’s closing claim stays with the productive side of that boundary. The discovery changed the study of infinity, helped shape the machines used during a world war, and led to the device displaying the video. Mathematical work continued through the boundary, and its new questions became part of the machinery of everyday life.

Limits

The historical narrative, quoted lines, figures, and technical explanations here follow Veritasium’s English captions and video description. The description credits Asaf Karagila for consultation on set theory and rewrites, Alex Kontorovich for reviewing earlier drafts, Toby Cubitt for help with the spectral gap, and Henry Reich for feedback. The note does not independently check the historical episodes, the 762-page figure from Principia Mathematica, the estimate about the length of the Second World War, the account of Turing’s post-war work, or the underlying papers.

The source uses “true” in the ordinary mathematical sense whilst discussing formal systems, and it explains Gödel’s construction at an accessible level. The exact result depends on conditions about the system, including that it can express basic arithmetic and remains consistent. “Mathematics is undecidable” therefore means that no single algorithm can decide every statement derivable from a sufficiently expressive formal system. Ordinary calculation and individual mathematical problems can still be decidable.