How to work with this page

This page is the workshop for Lesson 5 of the Logic unit. You work through it alone, in about 45 minutes, with your Lesson 5 handout beside you. It has one job: to make sure that after this lesson you never again say unprovable when you mean false — and never say “Gödel proved” about something Gödel did not prove.

Each part is built the same way:

1. Explanation — short, with the lesson’s own examples.
2. Exercise — you type or choose, then press Check. Nobody sees your mistakes. The page counts your first try; that number is for you.

The page has three stages. Stage 1 puts the lesson’s case on trial and asks you to take a side before you have the tools. Stage 2 gives you the tools: the definitions, Gödel numbering, the two theorems and what they do not say, the Lucas–Penrose argument laid out as premises. Stage 3 sends you back to your verdict with the tools in hand. Your sheet tells you when each stage is due.

Recall — Lesson 4 from memory

Before anything new: eight questions on Lesson 4, without your notes. Guess first: how many of the eight will you get? …… of 8.

Stage 1 — The case first

On 29 October 2018 Lion Air Flight 610, a Boeing 737 MAX 8, crashed into the Java Sea thirteen minutes after takeoff, killing all 189 aboard. On 10 March 2019 Ethiopian Airlines Flight 302, the same type, crashed six minutes after takeoff, killing all 157 aboard. Both crashes were attributed to MCAS, a flight-control law Boeing had added to compensate for the MAX’s larger, further-forward engines: it read a single angle-of-attack sensor and, if the nose seemed too high, trimmed the stabiliser to push it down. The system had been formally specified, certified and tested; inside its design envelope it worked correctly. In each crash the single sensor was damaged or misaligned — a badly installed replacement vane, a probable bird strike. Outside the conditions it was specified for, MCAS did not fail silently: it activated again and again (more than twenty times on the Lion Air flight), commanding nose-down against pilots who had never been told MCAS existed. The Joint Authorities Technical Review (2019) concluded that certification had treated MCAS as a minor refinement of an existing system rather than a new flight-control law pilots needed to know about and could override.

The lesson’s use of the case, in one sentence: MCAS could not recognise from inside its specification that it had left it; Hilbert’s programme could not recognise from inside the system that the system was consistent — the structural shape is the same.

Stage 2 · Part A — The definitions, and the dream they belonged to

A1. Hilbert’s programme

By the early twentieth century, mathematicians led by David Hilbert wanted to place all of mathematics on an absolutely secure axiomatic foundation. Three goals: propose a complete set of axioms; show the axioms are consistent (they lead to no contradiction); show they are complete (every mathematical truth can be derived from them). Mathematics would then be a perfect, closed system.

The crack was already visible. In 1901 Bertrand Russell found a contradiction inside the axioms of Frege’s Grundgesetze der Arithmetik — the set of all sets that do not contain themselves: if it contains itself, it does not; if it does not, it does. His letter reached Frege in June 1902, with the second volume already at the printer. Russell and Whitehead’s Principia Mathematica (1910–1913) attempted the repair with a “theory of types” across nearly 2,000 pages; it takes 379 pages to prove that 1 + 1 = 2.

A2. Three words, fixed

• A consistent system never proves a contradiction — never both P and ¬P.
• A complete system can prove or refute every statement in its language.
• A statement the system can neither prove nor refute is undecidable in that system. (The word is in the title of Gödel’s 1931 paper; a complete system has no undecidable statements.)

Two more pieces of vocabulary you will need: Gödel numbering assigns a unique whole number to every formula, so that statements about formulas can be translated into statements about arithmetic; and the principle of explosion (ex contradictione quodlibet) is the reason mathematicians choose consistency when forced to choose — from a contradiction, anything at all can be derived.

Part B — Gödel numbering, and the two theorems

B1. The idea of Gödel numbering

Gödel’s proof needs a formal system to talk about itself. A system for arithmetic speaks only about numbers; so give every formula a number. Then “formula so-and-so is provable” is a claim about a number — and a claim about a number is something the system can express.

A toy version, small enough to run by hand. The language has four symbols, each with a one-digit code:

The Gödel number of a formula is its codes written out in order and read as a single number. So 0=0 becomes 1 3 1, the number 131; and s0=s0 (in the toy language, s means “the successor of”) becomes 2 1 3 2 1, the number 21321. Every formula gets a number, and from any such number the formula can be read back.

B2. The two theorems, as the lesson states them

Kurt Gödel, “On Formally Undecidable Propositions of Principia Mathematica and Related Systems” (1931):

First Incompleteness Theorem — Any consistent formal system capable of expressing basic arithmetic contains true statements that cannot be proved within the system.

Second Incompleteness Theorem — A consistent formal system cannot prove its own consistency.

The First is proved by constructing, with the coding, a statement G whose informal content is: This statement cannot be proved in this system. Warm-up first: “This sentence has five words” is true not because someone proved it but because the sentence correctly describes itself. G does the same, except what it describes is its own unprovability.

The two horns. Suppose the system is consistent — it never proves a false statement.

• If G were provable, the system would have proved a statement asserting its own unprovability: a false claim, proved. The system would be inconsistent.
• If G is not provable, then G’s claim about itself — that it cannot be proved — is accurate.

Why unprovability entails truth. In a consistent system the first horn is ruled out, so G is not provable. But G says exactly that — and, by the argument just given, correctly. A statement whose content is correct is true.

The Second follows the same shape and does the more damage: any proof of consistency would itself have to be produced within a formal system. You cannot use mathematics to prove that mathematics contains no hidden contradiction.

Part C — What the theorems show, and what they do not

C1. The forced trade

Consistency and completeness cannot both be had in any system powerful enough to encode arithmetic. Mathematicians choose consistency, because of the principle of explosion. What this means: truth is not the same as provability — there is a gap — and Hilbert’s programme of securing all mathematics on a finite set of consistent, complete axioms is impossible. What this does not mean: that mathematics is unreliable. Gödel sentences are constructed specifically to be unprovable; they do not arise in ordinary mathematical practice. And whether incompleteness implies anything about the human mind is a separate, contested question.

Part D — The Lucas–Penrose argument, standardised

D1. Premises and conclusion

The lesson’s Position A, laid out as an argument:

1. For any formal system F proposed as capturing human mathematical reasoning, F has a Gödel sentence G(F) that F cannot prove.
2. A competent mathematician, given F and the assumption that F is consistent, can see that G(F) is true.
3. Therefore the mathematician can do something F cannot; F does not capture human mathematical reasoning — the mind is not a formal system.

Position B (Putnam, Feferman) does not deny premise 1: that is Gödel’s theorem. It attacks premise 2. The “seeing” is conditional on F’s consistency, which humans cannot reliably check for arbitrary strong systems — the Second Theorem says no strong consistent system can prove its own consistency, and humans are not exempt. Formalise the conditional (“if F is consistent, then G(F)”) and you get a formal system that proves the same thing. Putnam’s name for the mistake is equivocation: the mathematician’s “seeing” smuggles in an assumption a formal system could have been handed as an axiom. Penrose’s reply: add that confidence to F as an axiom and the argument iterates — the new system has its own Gödel sentence.

Stage 3 — Back to the case

Your verdict, with the tools

Take out what you wrote at Stage 1. Now rewrite it in three sentences:

1. Your side (A, with Lucas and Penrose; or B, with Putnam and Feferman).
2. Your reason — and say which premise of the standardised argument it lives at. Premise 1 is Gödel’s theorem; nobody on either side rejects it. Premise 2, the mathematician’s seeing, is where the case lives — and your sentence must say whether that seeing is conditional on the system’s consistency or not.
3. The price your side pays. A: answer Putnam’s charge of equivocation — why the “seeing” is not itself an assumption a formal system could have been handed as an axiom. B: say what is missing from the standard reply that Penrose’s microtubule proposal is (however speculatively) trying to supply, rather than dismissing it as a shrug.

Then check your own paragraph:

• Did you state the consistency condition? A verdict that leaves “assuming F is consistent” unstated has not yet begun.
• Did your reason name a premise, not an outcome (“computers can’t do X”, “MCAS crashed”)?
• Did you keep unprovable and false apart, and incomplete and inconsistent apart?
• Did you say the price in your own words, not the sheet’s?

Only now: compare with the three model paragraphs — two good ones, one bad one.

Done?

You can now:

• say what consistent and complete mean, and why a strong enough system must give up one;
• state both theorems as the lesson does, and tell which is which;
• explain, with a toy code, how a system about numbers comes to talk about itself;
• walk the two horns and say why unprovability entails truth for G;
• list what the theorems do not show — and catch “Gödel proved…” being used for something Gödel did not prove;
• lay Lucas–Penrose out as premises and say where Putnam’s attack lands.

Go back to your sheet.