Put yourself back in the schoolroom. The teacher writes on the board the rules for adding, multiplying and taking powers of positive whole numbers, eleven of them:1

x+y=y+x,x⋅(y+z)=x⋅y+x⋅z,(x+y)+z=x+(y+z),1x=1,x⋅1=x,x1=x,x⋅y=y⋅x,xy+z=xy⋅xz,(x⋅y)⋅z=x⋅(y⋅z),(x⋅y)z=xz⋅yz,(xy)z=xy⋅z.

With them you can prove (x+1)2=x2+2x+1, and every other identity you were set as homework. A student at the back asks the obvious question. Do these rules settle every identity that is true of the positive whole numbers? If an equation between two expressions in x, y, 1, +, ⋅ and powers holds whatever numbers are put for the letters, can it always be derived from the eleven?

The question is Tarski’s, and it waited more than a decade for an answer. The answer is no. Here is an identity, found by Wilkie, in which A=1+x, B=1+x+x2, C=1+x3 and D=1+x2+x4:

(Ay+By)x⋅(Cx+Dx)y=(Ax+Bx)y⋅(Cy+Dy)x.

It is true for every pair of positive whole numbers x and y. The reason is a hidden common factor: C=A⋅(1−x+x2) and D=B⋅(1−x+x2), so that Cx+Dx is (Ax+Bx) times (1−x+x2)x, and in the same way Cy+Dy is (Ay+By) times (1−x+x2)y. Both sides are then the same product, written in a different order. But the factor 1−x+x2 has a minus sign in it, and the eleven rules have no subtraction. The identity is true, and the rules cannot derive it.

Failing to find a derivation would prove nothing. To show that a claim does not follow from rules, exhibit a world in which the rules hold and the claim fails. For Wilkie’s identity the smallest such world has twelve elements, with tables for addition, multiplication and powers that obey all eleven rules.

That no smaller world exists was settled in 2026 by the method of the last chapter. Each possible entry of each table became a propositional letter, the eleven rules and the failure of Wilkie’s identity became clauses, and a SAT solver said “no” for eleven elements, with a proof of 368 megabytes that an independent program checked.2 These are the two kinds of evidence of the last chapter: a structure, which anyone can check by plugging in, shows that a claim does not follow; a closed search, written down as a proof, shows that no smaller structure does.

Adding Wilkie’s identity to the board does not end the matter: no finite list of identities, however long, derives every true one. There is no last patch.

The schoolroom is a small version of a large hope. In 1899 Hilbert wrote down axioms for Euclid’s geometry from which every theorem followed by logic alone, and he hoped for the same in arithmetic, the study of the counting numbers 0,1,2,… with addition and multiplication: axioms from which every truth about the numbers could be derived. Every sentence about the counting numbers is true or false, even when nobody knows which. Goldbach’s conjecture, that every even number greater than 2 is a sum of two primes, is one such sentence. With such axioms, settling it would be a matter of searching through derivations.

On 8 September 1930, in Königsberg, Hilbert ended an address with the words Wir müssen wissen. Wir werden wissen. (We must know. We shall know.) On the day before, in the same city, a young logician from Vienna, Kurt Gödel, had announced a theorem that showed the hope to be mistaken.

The last chapter left open two questions about theories and programs, and this chapter takes them up.

  • The search gap. The first-order procedure REFUTE certifies every entailment that holds, and runs for ever on some that do not. Is that a fault of the procedure, which a cleverer search would repair?

  • The specification gap. Even a perfect oracle for “does this follow from the theory?” tells us only what follows from the theory, when what we wanted was what is true of the system it describes. The two agree only when the theory says everything about the system. Can it always be chosen so?

Neither gap can be closed in general, and one construction answers both questions: the rules by which programs run can be written down as sentences. The chapter takes four steps.

  • Section 8.1 shows that no program checks whether a combinator halts, writes the rules by which combinators run as a handful of first-order sentences, and concludes that no program decides first-order validity. That settles the search gap.

  • Section 8.2 makes the specification gap precise: a specification captures a structure when it proves exactly the sentences true there, and that happens exactly when a program can decide those sentences. Computation cannot be captured, and every finite structure can.

  • Section 8.3 shows that the counting numbers contain computation, so that no specification captures them, and, the first incompleteness theorem, names for any sound specification a true sentence that it does not prove.

  • Section 8.4, the second incompleteness theorem, shows that a consistent specification of arithmetic does not entail its own consistency, a limit that does not mention the counting numbers at all.

Two optional sections follow. Section 8.5 proves in full that halting can be expressed, and Section 8.6 asks which infinite structures can be captured. The main line quotes some of their results but none of their proofs.

8.1 Computation as a Theory

The search gap asks whether any procedure decides entailment, so we need to say what a procedure is. Chapter 1 has the answer: a procedure is a combinator, since combinators compute everything that any machine computes.3 We use the rules for a step, the shape of a normal form and the fact that no step is a wrong turn.

Definition 8.1 (halting). A combinator halts when it has a normal form.

Formally, a combinator M halts if M⇝∗N for some N in normal form.

Theorem 8.2 (halting is undecidable). There is no program for checking whether a given combinator halts.4

Proof. Suppose that a program h checks it. Let P be the program that, given a combinator M, asks h whether M given itself as input halts, and does the opposite: it loops for ever if h says yes, and halts if h says no. By Turing completeness P is a combinator, and

P given itself haltsiffh says that P given itself does not haltiffP given itself does not halt,

which is impossible. □

Remark 8.3 (programs reading programs). A combinator takes combinators as its inputs, not strings, so “given a combinator” and “given itself” need a convention. A program reads a combinator M as the string of K, S and brackets that spells it, that is, as a number, its code ⌜M⌝ (Definition 8.23); and “M given itself” is M applied to the numeral of its own code. With these readings the proof is exact: P, written in pseudocode, is a combinator by Fact 8.24, and h is asked about the combinator P⌜P⌝―, which a program can write down.

With the theorem in hand we can show that no program decides validity in first-order logic, and hence that the first-order procedure REFUTE, which stops exactly on the unsatisfiable clause sets, is as good as any procedure can be: a semi-decision procedure, which can be improved only in speed. The proof writes the combinators as a theory, a set of sentences about combinators in the signature

ΣKS=({K,S}, {ap}, {Step,Nf,Halts}, ar),

with ar(ap)=ar(Step)=2 and ar(Nf)=ar(Halts)=1. We write ap(x,y) as xy, as application is written, so that every combinator is a closed term; Step(x,y) says that x steps to y, Nf(x) that x is in normal form, and Halts(x) that x halts.

Each rule of Chapter 1 says that if the facts above the bar hold, so does the fact below. Read the bar as an implication, and the rule is a sentence. For instance,

P⇝P′PQ⇝P′Qapp1becomes∀x∀x′∀y(Step(x,x′)→Step(xy,x′y)):

the letters P, P′ and Q, which stand for any combinators, become variables bound by ∀; the premiss becomes the antecedent; and the conclusion becomes the consequent. Formulas of this shape, with atomic premisses and one atomic conclusion, are called Horn clauses.

Definition 8.4 (the theory of computation). The theory of computation is the rules for a step, for normal forms and for halting, written as sentences.

Formally, the theory of computation Π is the set of the universal closures of the eleven formulas of ΣKS in Figure 8.1.

Steps(K)  Step(Kxy,x)(app1)  Step(x,x′)→Step(xy,x′y)(S)  Step(Sxyz,xz(yz))(app2)  Step(y,y′)→Step(xy,xy′)Normal forms(N1)  Nf(K)(N3)  Nf(x)→Nf(Kx)(N2)  Nf(S)(N4)  Nf(x)→Nf(Sx)(N5)  (Nf(x)∧Nf(y))→Nf(Sxy)Halting(H1)  Nf(x)→Halts(x)(H2)  (Step(x,y)∧Halts(y))→Halts(x)
Figure 8.1. The theory of computation.

The four sentences for steps are Chapter 1’s rules, the five for normal forms are the shapes of the shape lemma, and the two for halting say that a normal form halts and that halting passes back along a step. The theory is the same for every program: only the sentence Halts(M) mentions M.

Example 8.5 (a run, twice). The combinator KKSS steps to KS by a K step in the function. By the rules of Chapter 1 the step is

KKS⇝KKKKSS⇝KSapp1

and in NK, from the sentences (K) and (app1) of Π, it is

(app1)Step(KKS,K)→Step(KKSS,KS)∀E(K)Step(KKS,K)∀EStep(KKSS,KS)→E

where a bar marked (∀E) stands for as many (∀E) steps as the sentence has quantifiers. Each rule becomes its sentence, instantiated by (∀E) and applied by (→E). The result KS is in normal form, and the rest of the derivation of Halts(KKSS) goes the same way, one line for each rule used:

Nf(S)(N2)Nf(KS)(N3), with the line aboveHalts(KS)(H1), with the line aboveHalts(KKSS)(H2), with the step and the line above.

The theory Π is meant to describe computation, and the next lemma says that it gets halting right. Parts (i)–(iii) say that Π is strong enough: every step, every normal form and every halting combinator is recorded by a derivation, as in the example. Part (iv) says that Π is not too strong: it never proves that a combinator halts when it does not. So the sentence Halts(M) follows from Π exactly when M halts, and questions about halting become questions about first-order consequence.

Lemma 8.6 (a program is a theory). For all combinators M and N:

  1. if M⇝N, then Π⊢NKStep(M,N);

  2. if M is in normal form, then Π⊢NKNf(M);

  3. if M halts, then Π⊢NKHalts(M);

  4. if Π⊢NKHalts(M), then M halts.

So M halts iff Π⊢NKHalts(M), iff Π⊨Halts(M).

Proof. Parts (i)–(iii) read the rules as sentences, as in the example.

  • (i). By induction on the rules that stack up to M⇝N: each rule is an instance of one of (K), (S), (app1), (app2), reached by (∀E) and applied by (→E).

  • (ii). By induction on M: by the shape lemma, M is K, S, KN1, SN1 or SN1N2 with N1, N2 in normal form, and (N1)–(N5) cover the five cases.

  • (iii). Take a run M=M0⇝⋯⇝Mk to a normal form. By (ii) and (H1), Π⊢NKHalts(Mk); by (i) and (H2), Π⊢NKHalts(Mi+1) gives Π⊢NKHalts(Mi), back to i=0.

  • (iv). Let T be the structure whose domain is the set of combinators, in which each closed term means itself, and Step, Nf and Halts are true of the steps, the normal forms and the combinators that halt. Every sentence of Π is true in T: the four for steps are the rules, the five for normal forms are the shape lemma read from right to left, and a normal form halts, as does anything that steps to a combinator that halts. If Π⊢NKHalts(M), then T⊨Halts(M), by the soundness of NK, and so M halts.

The last sentence of the lemma is (iii) and (iv) together, with the soundness and completeness of NK. □

Theorem 8.7 (validity is undecidable). No program decides, for every sentence of ΣKS, whether it is valid.

Proof. Write ⋀Π for the conjunction of the eleven sentences of Π. Given a combinator M, a program can write down the sentence ⋀Π→Halts(M), and by Lemma 8.6

M haltsiff⊨⋀Π→Halts(M).

A program that decided validity would therefore check whether a given combinator halts, and there is none (Theorem 8.2). □

A larger signature does not help: a program that decided validity for it would decide, in particular, the sentences of ΣKS. The proof is a reduction: a computable map from halting questions to questions of the new kind, with the same answers. Every undecidability result of the chapter is proved by one, and the work is always in checking that the answers agree (here, Lemma 8.6).

Corollary 8.8 (other forms of the question). No program decides, for every input of the following kinds, the question asked:

  1. given a finite set Γ of sentences and a sentence φ, whether Γ⊢NKφ;

  2. given a finite set of sentences, whether it is satisfiable;

  3. given a finite set of clauses, whether it is satisfiable.

Proof. Take Γ=Π and φ=Halts(M) for (i). For (ii) and (iii), Π∪{¬Halts(M)}, a set of clauses once the quantifiers are dropped, is unsatisfiable exactly when M halts. □

In (i) the set Γ is always Π: there is one finite set of sentences whose consequences no program decides.

This settles the search gap. The first-order procedure REFUTE stops on every unsatisfiable clause set, and so does REFUTE-U. A procedure that also stopped on every satisfiable set would decide satisfiability, and by part (iii) of the corollary there is none. A cleverer search can be faster, but it cannot gain the other half of the answer. The valid sentences can be listed, by running REFUTE on the negations of all sentences at once and printing those whose runs close, so they have a semi-decision procedure; but they cannot be decided.5 Membership can be confirmed; non-membership, in general, cannot.

Remark 8.9 (what remains decidable). None of this makes logic useless in practice. Many questions can still be decided.

  • Propositional logic is decided by DPLL.

  • Whether finitely many sentences have a model with n elements, for a given n, is a propositional question for a SAT solver.

  • Many restricted languages have decision procedures of their own, and some of them close this chapter.

No method decides every first-order question, and the tools in use make one of three choices.

  • They restrict the language to a part that can be decided.

  • They accept a search that may not stop, as REFUTE does.

  • They keep a person in the loop, as the interactive provers built on type theory do.

8.2 Specifications

The specification gap asks whether a theory can say everything true of the system it describes, and Π is a first test case. It describes a structure that was there before any theory of it: computation itself. In the language ΣKS, computation is the structure T of the proof of Lemma 8.6: its domain is the set of combinators, each closed term means itself, and

⟦Step⟧T={(M,N):M⇝N},⟦Nf⟧T={M:M is in normal form},⟦Halts⟧T={M:M halts}.

The structure deserves its name. Every program, in any programming language, can be written as a combinator, and running the program is then running the combinator: that is Turing completeness. So a question about what a program does is a question about T, and the combinators express everything there is to compute.6

Does expressing everything mean that Π says everything? The theory Π proves only truths about T, since T is a model of it, and it proves Halts(M) for every combinator M that halts. But it does not prove everything true there. The Monster Ω of Chapter 1 has no normal form, and

T⊨¬Halts(Ω)butΠ⊬NK¬Halts(Ω),

since in the structure where every combinator halts the sentences of Π are true, and so is Halts(Ω) (Exercise 8.3). So a language that can express every computation comes with a theory that leaves open some questions that computation settles.

Could Π be extended to close the gap? In a trivial way it can: the set of all sentences true in T proves every truth about T, each in one line. But a theory is of use only if it can be written down, which here means that a program can recognise its members. Nothing guarantees that for the set of all truths. So the question is whether some theory that can be written down says everything true of T. The answer is no. To prove it we make three notions precise: the set of all truths, a theory that can be written down, and a theory that says everything.

Definition 8.10 (the theory of a structure). The theory of a structure is the set of everything true of it.

Formally, for a Σ-structure M,

Th(M):={φ:φ is a Σ-sentence and M⊨φ}.

For every sentence φ, exactly one of φ and ¬φ is in Th(M), since M⊨¬φ exactly when M⊭φ: a structure takes a side on every question its language can ask. That is what distinguishes a structure from a theory, which may leave a question open.

To be of use, a theory needs one thing besides its sentences: a program that recognises its members.

Definition 8.11 (specification). A specification is a theory that a checker can read: given a sentence, the checker tells whether it belongs to the theory.

Formally, let Σ be a finite signature. Its sentences are then finite strings of symbols from a finite list, once each variable is written as x followed by digits. A Σ-theory Θ is a specification if there is a program that, given a Σ-sentence, always halts and says whether it is in Θ.7

The sets one would naturally write down are specifications.

  • A finite set of sentences is a specification: the program compares the given sentence with each of them. The theory of computation Π is one.

  • The equality axioms of a signature that contains = are a specification. There are infinitely many instances of (Eq2), one for each formula, but a program recognises an instance by its shape.

  • In the same way, every finite set of sentences together with all the instances of finitely many schemas is a specification.

The definition asks for a program because the point of a derivation from Θ is that anyone can check it, and checking it includes checking that its open hypotheses are in Θ.

Remark 8.12 (a list of axioms is enough). One could ask for less: that a program merely list the members of Θ, one after another. Nothing would change. If a program lists the sentences φ0,φ1,φ2,…, then the sentences φn∧⋯∧φn, with n+1 copies of φn, form a specification with the same theorems. Each is equivalent to φn, and a program recognises one by counting its copies and running the list that far.8 So “a theory that can be written down” means the same on either reading.

Definition 8.13 (captures). A specification captures a structure when what follows from it is exactly what is true of the structure.

Formally, a specification Θ captures a Σ-structure M if, for every Σ-sentence φ,

Θ⊢NKφiffM⊨φ.

The definition has two halves, of very different weight.

  • Only truths: if Θ⊢NKφ then M⊨φ. When M⊨Θ this half is free, by the soundness of NK.

  • Every truth: if M⊨φ then Θ⊢NKφ. This is the half with content: it asks the theory to settle every question that the structure settles.

So Π, a specification since it is finite, does not capture T: it proves only truths about T, but not ¬Halts(Ω). The set Th(T) proves exactly the truths about T, trivially, and would capture T if it were a specification. The question is whether some specification captures T.

Remark 8.14 (three senses of “complete”). The word “complete” has three uses nearby, and they are easy to confuse.

  • The completeness of NK is a property of a proof system: whatever is true in every model of Θ can be derived from Θ.

  • The second half of capturing, which many books call the completeness of Θ, is a property of a theory: whatever is true in the one structure we meant can be derived from Θ. When every sentence true in M is true in every model of Θ, the completeness of NK gives it; the gap between the two is the specification gap. To keep the senses apart we say “captures”, and never “complete”, for this one.

  • Turing completeness is a property of a programming language: every program can be written in it. It says that the combinators can express every computation, not that a theory of them proves every truth about computation.

The last two pull against each other. Because the combinators can express every program, the diagonal program of the halting theorem among them, no specification captures computation (Corollary 8.17).

What a specification makes possible is a mechanical list of its theorems. A program can recognise the members of a specification, and a program can check a derivation, rule by rule. So a program can list the theorems of a specification, one after another, by checking every candidate derivation in turn.9

Lemma 8.15 (a specification’s theorems can be listed). For every specification Θ there is a program that runs for ever and prints sentences, such that the sentences it prints are exactly the sentences φ with Θ⊢NKφ.

Proof. A derivation of NK is a finite tree of formulas, and can be written out as a string of symbols. The program tries every string.

procedure LIST                     -- prints the theorems of Theta
    for each string w, shortest first, then in alphabetical order:
        if w is a derivation of NK,
           each open hypothesis of w is in Theta,
           and the conclusion of w is a sentence:
            print the conclusion of w

Each test halts: a derivation is checked node by node against the finitely many rules and their side conditions, and membership of Θ is asked of the program for Θ. So every string is dealt with in finite time. A sentence φ with Θ⊢NKφ has a derivation, which is some string, and is printed when LIST reaches it. A sentence that is not derivable is never printed. □

Proofs are easy to check and hard to find, and a program that checks every candidate finds them all, eventually. The list says nothing about a sentence that is not on it, however long one waits, and that is the whole difficulty. But a structure takes a side on every question, so a specification that captured it would sooner or later list either φ or ¬φ, for every sentence φ.

Theorem 8.16 (capturing makes truth decidable). If a specification Θ captures a structure M, there is a program that, given a sentence φ, always halts and says correctly whether M⊨φ.

Proof. The program waits for φ or its negation to be printed.

procedure DECIDE(phi)              -- phi a sentence
    for each theorem psi of Theta, as LIST prints them:
        if psi is phi:                   answer yes
        if psi is the negation of phi:   answer no

It halts: either M⊨φ or M⊨¬φ, and Θ proves every truth about M, so one of the two is printed. Its answer is correct.

  • If φ is printed, then Θ⊢NKφ. Since Θ captures M, it proves only truths, so M⊨φ, and the answer is yes.

  • If ¬φ is printed, then in the same way M⊨¬φ, and the answer is no.

□

A specification that captures a structure turns truth into computation. Read backwards, the theorem is a way to show that a structure cannot be captured:

if no program decides the truths of M, then no specification captures M.

That answers the question about computation.

Corollary 8.17 (computation cannot be captured). No specification captures the structure T of computation. In particular, Th(T) is not a specification.

Proof. For every combinator M, exactly one of Halts(M) and ¬Halts(M) is true in T, according as M halts or not. A program that decided the truths of T would therefore check whether a given combinator halts, and there is none (Theorem 8.2). So by Theorem 8.16 no specification captures T, and since Th(T) proves exactly the truths about T, it is not a specification. □

For Π we can watch the mechanism. The listing of its theorems prints Halts(M) for every combinator M that halts, and never prints ¬Halts(M). A specification that captured T would also print ¬Halts(M) for every M that does not halt, and waiting for one of the two would decide halting. So the questions that Π leaves open are not a defect of Π: every specification of computation that tells the truth leaves some truth unproved.

The theorem that capturing makes truth decidable has a converse, and together they say that capturing and deciding are the same thing.

Proposition 8.18 (capturing is deciding). A structure M is captured by some specification if and only if some program, given a sentence φ, always halts and says correctly whether M⊨φ.

Proof. One direction is Theorem 8.16. For the other, suppose a program decides the truths of M. Then Th(M) is a specification, and it captures M.

  • Only truths. Whatever it proves is true, by the soundness of NK, since M⊨Th(M).

  • Every truth. Whatever is true is a member, and so is proved by the derivation consisting of that one hypothesis.

□

What a good specification adds is economy: a short list that a person can write, read and argue about, in place of the list of every truth.

Remark 8.19 (deciding with REFUTE). The program DECIDE searches through derivations, which is slow. The first-order procedure REFUTE does the same job faster. Suppose a specification Θ that captures M can be written as a finite set of clauses, and let φ be a sentence. Run REFUTE on Θ∪{¬φ} and on Θ∪{φ}, taking a step of each run in turn.

  • The first run stops exactly when Θ⊨φ, and the second exactly when Θ⊨¬φ.

  • One of φ and ¬φ is true in M and so, because Θ captures M, is entailed by Θ.

So one of the two runs stops, and which one says whether M⊨φ.

Remark 8.20 (finite structures can be captured). Finite structures are the one kind for which the specification gap can always be closed. On a finite structure the definition of truth is an algorithm: each quantifier runs through the domain, so a sentence with k nested quantifiers on n elements takes about nk cases. So its truths can be decided, and by Proposition 8.18 it can be captured. A finite list will do, and it is the list anyone would write. Give each element d a new name cd, and write down

  • distinctness: cd≠ce for each pair of different elements d and e;

  • closure: ∀x(x=cd1∨⋯∨x=cdn), where d1,…,dn are all the elements;

  • the tables: f(ce1,…,cem)=ce whenever f sends e1,…,em to e, and P(ce1,…,cem) or its negation, for each relation symbol P other than = and each tuple.

These sentences, the description ΔM of the structure M, together with the equality axioms, capture M with its elements named. The proof is an induction on sentences: under the closure sentence every ∀ becomes a finite conjunction and every ∃ a finite disjunction, and what is left are entries of the tables. The closure sentence is the one with no counterpart for an infinite structure. It says where the structure stops, and without it a model may have an extra element of which the tables say nothing (Exercise 8.10).

The section has pulled apart four things that are easy to run together.

  • Expressing. The combinators express every program: that is Turing completeness, a property of a language.

  • Proving what happens. The theory Π proves nothing false about T, and proves Halts(M) for every M that halts; but it does not prove ¬Halts(M) for every M that does not.

  • Proving everything, with some theory. The set Th(M) of all truths proves exactly the truths about any structure M, trivially. It captures M only if it is a specification, that is, only if a program can recognise its members.

  • Capturing by a specification. This is the question that matters, and the answer depends on the structure. Every finite structure can be captured (Remark 8.20). Computation cannot, because capturing would decide its truths, and halting cannot be decided.

The rest of the chapter asks the last question of the counting numbers.

8.3 The First Incompleteness Theorem

Computation cannot be captured, but computation is a strange structure, with a partial operation and runs that never end. Surely something as simple as the counting numbers can be captured? They are the structure the founders of modern logic most wanted to capture, and the oldest one in mathematics.

They cannot be, and the reason is that the counting numbers contain computation: the theory Π, and with it everything that can be said about combinators, can be carried inside arithmetic. Combinators can be written as numbers, and stepping, being in normal form and halting as relations between numbers, each expressed by a formula built from + and ×. Then every sentence φ about computation has a translation [φ], a sentence about numbers, with

T⊨φiffN⊨[φ],

and a program can compute [φ] from φ. A specification that captured the counting numbers would let a program decide their truths, and so, through the translation, the truths of computation, which no program can decide (Corollary 8.17). The section fixes the language of the counting numbers and makes this precise in three steps: combinators as numbers, steps as formulas, and the translation. It then names a truth that a given specification misses: the first incompleteness theorem.

The counting numbers

The language is that of the counting numbers in Chapter 6, with equality added, since without it the language could not even say x+y=y+x.

Definition 8.21 (the signature of arithmetic, with equality). In this chapter the signature of arithmetic contains =, and the counting numbers interpret it as identity.

Formally,

ΣA=({0}, {s,+,×}, {<,=}, ar),

with ar(s)=1 and arity 2 for the others. The standard model of arithmetic N, as the structure is traditionally called, has the domain N={0,1,2,…}, and interprets

  • 0 as zero and s as the successor, n↦n+1;

  • + and × as addition and multiplication;

  • < as less than and = as identity.

The language has no symbol for 1, or for 7. It does not need one, since it can count.

Definition 8.22 (numeral). The numeral of a number is the term that counts up to it from 0.

Formally, for each number n the numeral n― is the closed term of ΣA defined by recursion on n:

0―:=0andn+1―:=s(n―).

So 3― is s(s(s(0))), and in general n― has n copies of s. Its value in N is n, by induction on n.

Unlike a finite structure, the counting numbers cannot be written out as a table, since their domain is infinite: they can only be described by a theory.

The language is small, but it says a great deal. Write x∣y for ∃z(x×z=y), “x divides y”, and

Prime(x):=1―<x∧∀y(y∣x→(y=1―∨y=x)),Even(x):=∃z(x=z+z).

With these abbreviations, the sentence ∀x∃p(x<p∧Prime(p)) says that there are infinitely many primes, which is true. The sentence

∀x((Even(x)∧2―<x)→∃p∃q(Prime(p)∧Prime(q)∧p+q=x))

is Goldbach’s conjecture. A specification that captured N would derive it or its negation, and the same holds for most open problems of number theory, which can be written in this language too.

Combinators as numbers

The first step is to write combinators as numbers, and it goes in three moves. A combinator is a string of the four symbols K, S, ( and ), once every application is bracketed; a string of four symbols is a sequence of the digits 1 to 4; and a sequence of digits is a number, written in base five.

Definition 8.23 (code). The code of a combinator is the number its fully bracketed string spells in base five.

Formally, the code ⌜M⌝ of a combinator M is the number whose digits in base 5 are the symbols of M written with every application bracketed, read with 1 for K, 2 for S, 3 for ( and 4 for ).

Here are three combinators and their codes.

CombinatorStringDigitsCode
KK11
KK(KK)3114409
SKK((SK)K)332141457734

Different combinators have different codes, and a program can pass between a combinator and its code in either direction. Inputs are numbers too: the input for the number n is Chapter 1’s numeral of n, written here with a bar beneath, n―, since the bar above is taken by the numerals of arithmetic. A combinator M halts on n if Mn― halts, and for numbers e and n we say that program e halts on n if e is the code of a combinator that halts on n.

Programs are easier to write in pseudocode, and one fact, borrowed from Chapter 1, lets us do so.

Fact 8.24 (programs are combinators). For every program written in pseudocode that takes a number as its input, there is a combinator P such that, for every number n, P halts on n exactly when the pseudocode halts on n.10

We call P the translation of the pseudocode, and do not distinguish the two: they halt on the same inputs, and the code of the pseudocode is the code of its translation.

Steps as formulas

The second step is to express the relations of computation by formulas of arithmetic.

Definition 8.25 (definable). A relation between numbers is definable if some formula of arithmetic is true of exactly the numbers that stand in it.

Formally, a set S of k-tuples of numbers is definable in N if there is a formula φ of ΣA whose free variables are among x1,…,xk such that, for all numbers n1,…,nk,

N⊨φ[n1―/x1,…,nk―/xk]iff(n1,…,nk)∈S.

The even numbers are definable, by Even(x), and so are the primes and the pairs (x,y) with x∣y.

Definability is a matter of truth in N, and says nothing about proofs. A formula that defines a set is true of its members; whether any specification can prove it true of them is a different question, about the specification. The notion that asks for proofs has a name of its own, representability, and the main line of this chapter never uses it. Section 8.4 needs two facts about what one particular specification proves, and states them.

Why should the relations of computation be definable at all? A combinator is a row of digits, and one step rewrites one stretch of the row and copies the rest. In the step from S(KKS) to SK, for instance, the strings are

(S((KK)S)⏟K redex)⇝(SK⏟P),

where the stretch ((KP)Q), with P=K and Q=S, has been replaced by P. So “x steps to y” says something about the digits of x and y at certain positions: that they agree outside one stretch, and inside it have the shape of a redex and of its result. Digits at positions are remainders, and “r is the remainder of a on division by m” is the formula

∃q(a=q×m+r∧r<m).

That takes care of being a combinator, of one step, and of normal form.

Halting is harder, because it says that some run ends, and a run may be as long as you like. A run is a finite table of numbers, one row of digits for each combinator. The one idea needed is that a finite table of numbers can be packed into two numbers a and b, with the entry at position i, counting from 0, the remainder of a on division by 1+(i+1)b. Then “there is a run that ends” is “there are numbers a and b whose table is a run that ends”, which is a statement about remainders again.

Example 8.26 (a table in two numbers). The table with the single row 2,0,3 is packed by a=80 and b=2, with the divisors 1+b=3, 1+2b=5 and 1+3b=7:

80=26×3+2,80=16×5+0,80=11×7+3.

The remainders are the entries, in order. Section 8.5 proves that every finite table can be packed in this way.

Lemma 8.27 (computation is definable). There are formulas Comb(x), App(x,y,z), StepA(x,y), NfA(x) and HaltsA(x) of ΣA such that, for every number p and all combinators M and N:

  1. N⊨Comb(p―) iff p is the code of a combinator;

  2. N⊨App(⌜M⌝―,⌜N⌝―,p―) iff p=⌜MN⌝;

  3. N⊨StepA(⌜M⌝―,⌜N⌝―) iff M⇝N;

  4. N⊨NfA(⌜M⌝―) iff M is in normal form;

  5. N⊨HaltsA(⌜M⌝―) iff M halts.

The proof is in the optional Section 8.5, which writes out the formulas; the main line uses only the lemma. One feature of HaltsA matters later. A combinator can have many runs, and the formula follows one of them, the leftmost run, which at each step rewrites the redex that starts first in the written-out combinator. That run is unique, and it reaches a normal form whenever any run does, so part (v) holds as stated.

The translation

The third step puts the formulas together. A sentence about combinators speaks of terms built from K and S by application, and of the relations Step, Nf and Halts; its translation speaks of their codes.

Definition 8.28 (the translation into arithmetic). The translation of a formula about combinators says the same about their codes.

Formally, for each term t of ΣKS and each variable z not in t, the formula Ct(z), “z is the code of t”, is given by

CK(z):=z=1―,CS(z):=z=2―,Cx(z):=z=x,Ctu(z):=∃v∃w(Ct(v)∧Cu(w)∧App(v,w,z)),

with v and w new variables. The translation [φ] of a formula φ of ΣKS is given by

[Step(t,u)]:=∃v∃w(Ct(v)∧Cu(w)∧StepA(v,w)),[Nf(t)]:=∃v(Ct(v)∧NfA(v)),[Halts(t)]:=∃v(Ct(v)∧HaltsA(v)),[⊥]:=⊥,[ψ◻χ]:=[ψ]◻[χ]for ◻ one of ∧,∨,→,[∀xψ]:=∀x(Comb(x)→[ψ]),[∃xψ]:=∃x(Comb(x)∧[ψ]).

The quantifiers are cut down to the codes of combinators, and everything else is said of codes. For instance, CKK(z) is true in N of 409 alone, so [Halts(KK)] says that HaltsA is true of 409; and since ¬ψ is ψ→⊥, the translation of ¬ψ is ¬[ψ].

Lemma 8.29 (arithmetic contains computation). For every sentence φ of ΣKS,

T⊨φiffN⊨[φ],

and a program, given φ, computes [φ].

Proof. The program follows the equations of the definition. For the rest we prove more, for formulas. Given an assignment s in T, which gives each variable a combinator, let s♯ give each variable the code of that combinator. We show that T,s⊨φ exactly when N,s♯⊨[φ].

  • Terms. For each term t, the formula Ct(z) is true in N, under s♯, of exactly one number, the code of the value of t under s. This is by induction on t, with part (ii) of the lemma that computation is definable for an application.

  • Atomic formulas. By the case of terms and parts (iii)–(v).

  • ⊥ and the connectives. The translation leaves them alone, and so does satisfaction.

  • The quantifiers. By part (i), the numbers of which Comb is true are exactly the codes of combinators, so “for every number that is a code” in N is “for every combinator” in T, and the same for “some”.

□

In words: everything true of computation is true, in translation, of the counting numbers, and nothing else is. In particular the translations of the sentences of Π are all true in N: arithmetic carries a copy of the theory of computation.

Nothing captures arithmetic

The rest is the argument sketched at the start of this section.

Theorem 8.30 (the truths of arithmetic are undecidable). No program decides, for every sentence φ of ΣA, whether N⊨φ.

Proof. A program that decided truth in N would decide truth in T: given φ, it would compute [φ] and decide that (Lemma 8.29). In particular, given a combinator M, it would decide T⊨Halts(M), that is, whether M halts, and no program does (Theorem 8.2). □

Corollary 8.31 (nothing captures arithmetic). No specification captures N. In particular, for every specification Θ with N⊨Θ, there is a sentence φ with N⊨φ and Θ⊬NKφ.

Proof. A specification that captured N would make the truths of N decidable, by Theorem 8.16, and no program decides them, by Theorem 8.30. If N⊨Θ, then Θ proves only truths, by the soundness of NK; since it does not capture N, it must miss a truth. □

So Th(N), the set of all true sentences of arithmetic, is not a specification. However carefully a list of axioms for arithmetic is chosen, if a program can read it and it proves only truths, it misses some truth.

Naming the missed truth

The corollary says that a specification misses a truth, but gives no idea which. For the theory Π the missed truth was a fact about a program that does not halt, ¬Halts(Ω), and for arithmetic it will be the translation of one. We assume that the specification tells the truth, and write a program that watches it at work.

Definition 8.32 (sound). A specification Θ in ΣA is sound if Θ⊢NKφ implies N⊨φ, for every sentence φ.

Here the word names a property of a specification, not to be confused with the soundness of NK, a property of the proof system: whatever NK derives from true premisses is true. The two are connected: by the soundness of NK, a specification Θ is sound exactly when N⊨Θ. A sound specification has the “only truths” half of capturing N (Definition 8.13); the first incompleteness theorem is about the other half.

The program that watches the specification waits for it to say that some program does not halt on its own code.

Definition 8.33 (the diagonal program). Let Θ be a specification in ΣA. The diagonal program DΘ of Θ is the following program, which uses the program LIST of Lemma 8.15 to list the theorems of Θ:

procedure D(e)                     -- e a number
    if e is the code of a combinator M:
        for each theorem phi of Theta, as LIST prints them:
            if phi is  [not Halts(M e)],  e as a numeral:  halt

We write d for its code, and γΘ, or γ, for the sentence [¬Halts(DΘd―)].

On the input e, the program waits for Θ to prove that program e does not halt on e, and halts if that ever happens. The interesting input is the program’s own code, and the sentence γ says, in arithmetic, that D run on its own code does not halt.

Theorem 8.34 (the first incompleteness theorem). If Θ is a sound specification in ΣA, then

N⊨γΘandΘ⊬NKγΘ.

Proof. Write D for the diagonal program of Θ and d for its code, and run D on d:

Θ⊢NKγiffDd― haltsthe definition of D, Lemma 8.15iffT⊭¬Halts(Dd―)iffN⊭γLemma 8.29.

So Θ proves the sentence exactly when the sentence is false. Since Θ is sound, it proves nothing false, so it does not prove the sentence; and then, by the same chain, the sentence is true. □

The proof used three things: that Θ proves only truths, the half of capturing that soundness gives; that its theorems can be listed (Lemma 8.15); and that arithmetic contains computation (Lemma 8.29). It used no particular axioms of arithmetic. Where Corollary 8.31 says only that some truth is missed, the diagonal program points at one: the translation of a fact about a program that never halts, as ¬Halts(Ω) was for Π.

Figure 8.2 draws the theorem. Among the sentences of ΣA, the theorems of a sound Θ lie inside the truths. The sentence γ lies in the gap between them, and its negation is false, so Θ proves neither. Adding γ to Θ widens the theorems to take it in, but the wider specification is again sound and has its own diagonal program, whose sentence lies in the new gap. There is no last patch.

A rectangle of all sentences of the language of arithmetic. Inside it a large ellipse, the sentences true in the counting numbers. Inside that, a smaller ellipse, the theorems of a sound specification Theta. A dot, gamma, lies in the true ellipse but outside the theorems. A dashed ellipse, the theorems of Theta with that sentence added, encloses the dot; a second dot, the new specification’s diagonal sentence, lies outside the dashed ellipse but still among the truths. A third dot, not gamma, lies outside the truths.
Figure 8.2. A sound specification and the truths.

The theorem has two hypotheses on Θ: that it is a specification, and that it is sound. Both are needed, and one example for each shows why.

  • A specification. The set Th(N) proves exactly the truths, so it leaves no truth unproved. It is not a specification (Corollary 8.31), so it has no program LIST, and its diagonal program cannot be written.

  • Sound. A specification that contains a sentence and its negation proves every sentence, by (→E) and (⊥E), and so it proves its own γ. It is a specification, and not sound.

Remark 8.35 (what the theorem shows, and what it does not). The theorem is often quoted, and often quoted wrongly.

  • It shows that no specification of arithmetic that tells the truth tells the whole truth. However the axioms are chosen, provided a checker can read them and they prove nothing false, some true sentence of arithmetic does not follow from them, and the proof says which.

  • It does not show that there are truths that nobody can know. We have just proved γ true, by an argument that uses the soundness of Θ, which Θ cannot supply for itself.

Remark 8.36 (the sentence speaks about itself). The first line of the proof’s chain reads: Θ proves γ exactly when Dd― halts. Read in N, the sentence γ says that Dd― does not halt, and so it says, of itself, “Θ does not prove me”. That is, in another dress, the sentence with which the incompleteness theorem was first proved. There the self-reference was built inside arithmetic: formulas were coded as numbers, and substituting a formula’s own number into it gave a sentence that says of itself that it is not provable. Here the self-reference costs nothing: it is D run on its own code.

It is the same move as in the halting theorem, the one essential idea of the subject: apply a thing to its own description, and arrange for it to do the opposite of what it predicts about itself. The program P did this to a predictor of halting, and the program D does it to a list of theorems; both are a program run on its own code. The move is older than computers: it is the Monster ωω of the first part of the course, the function that applies its argument to itself and then runs for ever. The History lines up four of its appearances in a table.

Remark 8.37 (the schoolroom). The schoolroom of the introduction asked this section’s question of a smaller structure, and of only part of its language. Take the signature with a constant 1 and two-place function symbols +, ⋅ and ↑, where x↑y is xy; let P be the positive integers with their usual operations; and let ΘHS be the equality axioms together with the eleven identities on the board, each with ∀ in front of its variables. Then ΘHS is a specification, and P⊨ΘHS, so it proves only truths. It does not prove every truth: Wilkie’s identity, with ∀x∀y in front, is true in P and not provable from ΘHS. The certificate is a structure of twelve elements, with tables for 1, +, ⋅ and ↑, in which all eleven identities hold and Wilkie’s identity fails at one pair of elements.11

A specification that misses a truth does not show that no specification does better. The identities true of P can be decided by a program,12 so the set of all of them is a specification that proves exactly the true identities. It captures the equational theory of P, its true identities, which no finite list does. It does not capture P, since capturing (Definition 8.13) asks about every sentence, with its connectives and quantifiers.

Nothing captures P in that sense. Let each positive integer n stand for the counting number n−1. Then 0, s, + and × can be defined from 1, + and ⋅; for instance, the counting numbers for which x+y=z are those for which x+y=z+1 holds in P. So a program that decided the truths of P would decide those of N, and none does (Theorem 8.30). By Theorem 8.16, no specification captures P. At school, the fragment can be captured and the whole structure cannot.

8.4 The Second Incompleteness Theorem

We know now that neither computation nor the counting numbers can be captured. For the counting numbers the route was roundabout: it went through another structure, computation, which they happen to contain, and through truth in N, which no specification reaches. Is there a more direct limit, one that mentions no structure at all?

There is, and it is the form in which Hilbert’s programme put the question. Take a specification strong enough to do a little arithmetic, such as Peano arithmetic below. Because it is a specification, a program lists its theorems; because it can do a little arithmetic, it can talk about programs, and so about the program that lists its own theorems. In particular it can state that this program never prints ⊥, which is to say that the specification is consistent. The second incompleteness theorem says that, if the specification is consistent, it cannot prove that sentence.

The theorem matters for two reasons. The first is what its sentence says: consistency is what Hilbert’s programme, the plan to secure mathematics by formal axioms, most wanted the axioms to establish about themselves. The second, and more to the point, is that the theorem has nothing to do with any intended structure. Consistency is a property of derivations, not of truth. So the limit is a limit of being specifiable as such: whatever structure we had in mind, a specification that can reason about programs cannot certify its own consistency, and, by the completeness of NK, its consistency does not even follow from it.

The route has two steps. The first theorem assumed that Θ is sound, a strong assumption: to know that a theory proves nothing false about the counting numbers, one has to know which sentences about them are true, and that is what no specification can tell us. So we first replace soundness by consistency, at the cost of one fact about what PA proves: every true sentence about halting. Then we carry the proof of the first theorem out inside PA. That step rests on three facts about what PA proves of the list of theorems of Θ. We state them exactly and sketch why each holds; the full proofs are long, and we take them on loan.

Peano arithmetic

Both steps need a specification that can reason about programs, and the natural one is the specification every course on arithmetic starts from.

Definition 8.38 (Peano arithmetic). Peano arithmetic, PA, is the set of sentences of ΣA consisting of the equality axioms and the following sentences, each with ∀ in front of its free variables:

  1. s(x)≠0 and s(x)=s(y)→x=y;

  2. x+0=x and x+s(y)=s(x+y);

  3. x×0=0 and x×s(y)=x×y+x;

  4. x<y↔∃z(s(z)+x=y);

  5. for every formula φ with a free variable x, the induction axiom (φ[0/x]∧∀x(φ→φ[s(x)/x]))→∀xφ.

The first group describes the successor, the second and third say how + and × compute, and the fourth defines the order. The fifth is proof by induction, with one axiom for each property it might apply to. A program recognises an induction axiom by its shape, so PA is a specification. Since N⊨PA, it is sound, and so is every specification obtained from it by adding true sentences. It proves a great deal: very nearly every theorem of elementary number theory that has ever been proved can be derived in it. By the first incompleteness theorem it misses some truth all the same.

For arithmetic, PA plays the part that Π played for computation: a short theory, true of the structure we meant, that proves every true fact about halting (Fact 8.39 below) and not every truth.

Consistency, which is to replace soundness, is the property used in the proof of completeness: a set of sentences Θ is consistent if Θ⊬NK⊥. In words: the theory never leads to a contradiction. Equivalently, there is no sentence φ with both Θ⊢NKφ and Θ⊢NK¬φ, since (→E) turns such a pair into ⊥ and (⊥E) turns ⊥ into anything. The definition mentions derivations alone, and no structure.

A sound specification is consistent, since N⊭⊥. The converse fails (Remark 8.49).

To trade soundness for consistency, we need one fact about what PA can prove: that it can check a finished calculation.

Fact 8.39 (true halting is provable). For every combinator M: if M halts, then PA⊢NK[Halts(M)].

The reason is that a halting run is a finite calculation. If M halts, there are particular numbers N, a and b that pack its run, and [Halts(M)] follows by (∃I) from the claim that these numbers do so. That claim comes down to checking each of finitely many rows. Each check is finite because every “for all” in HaltsA can be written to range only over the numbers below a given one, and so it comes down to facts about particular numbers, such as 80―=26―×3―+2―. The specification PA proves each such fact by calculating with its equations, as a pupil checks a long division. We take the details on loan. The fact is the arithmetical counterpart of part (iii) of the lemma that a program is a theory (Lemma 8.6): PA, like Π, proves every true fact about halting. What neither proves is every true fact about not halting.13

So every specification that contains PA proves [Halts(M)] for every combinator M that halts. The step from soundness to consistency uses nothing else about Θ, and the theorem asks for no more.

Theorem 8.40 (the first incompleteness theorem, from consistency). Let Θ be a consistent specification in ΣA that proves [Halts(M)] for every combinator M that halts. Then

N⊨γΘandΘ⊬NKγΘ.

Proof. Write D for the diagonal program of Θ and d for its code. As in the proof of the first incompleteness theorem (Theorem 8.34),

Θ⊢NKγiffDd― halts.

We show first that Θ does not prove the sentence, and then that it is true.

  1. Θ does not prove γ. Suppose it did. Then Dd― halts, so Θ proves [Halts(Dd―)], by the hypothesis. The sentence γ is the negation of that one, so Θ proves a sentence and its negation, and therefore ⊥, which contradicts its consistency.

  2. The sentence is true. By the first step and the display, Dd― does not halt, so T⊨¬Halts(Dd―), and N⊨γ by the lemma that arithmetic contains computation (Lemma 8.29).

□

In words: for a specification that proves every true sentence about halting, and so for every specification that contains PA, consistency is enough in place of soundness. The proof shows the price of the weaker assumption. A consistent specification that is not sound might prove the false sentence ¬γ, and nothing in the argument forbids it. So the theorem cannot say that Θ leaves the question open either way.

Remark 8.41 (a question left open either way). A cleverer program does give a sentence that a consistent Θ containing PA neither proves nor refutes. It searches the listing for a proof of a sentence and for a proof of its negation at once, and acts on whichever comes first. The argument is a little longer, and the main line does without it.14

Consistency as a sentence

Whether Θ is consistent is a question about a program: the one that waits for ⊥.

Definition 8.42 (the consistency sentence). The consistency sentence of a specification says that the program that waits for a contradiction never stops.

Formally, let Θ be a specification in ΣA, let CΘ be the program

procedure C(e)                     -- the input is ignored
    for each theorem phi of Theta, as LIST prints them:
        if phi is bottom:  halt

and let C be the combinator that runs it on 0. The consistency sentence of Θ is

ConΘ:=[¬Halts(C)].

The program CΘ ignores its input, so

Θ is consistentiffC does not haltLemma 8.15iffN⊨ConΘLemma 8.29.

The sentence ConΘ thus says “Θ is consistent” in the language of arithmetic. Like ¬Halts(Ω) for Π and γ for Θ, it is the translation of a fact about a program that does not halt. Hilbert’s programme hoped for a derivation of such a sentence from axioms everyone accepts.

Remark 8.43 (the program, not only what it does). The definition speaks of CΘ itself, and not of any combinator that halts on the same inputs. When Θ is consistent, CΘ halts on no input, like every combinator that never halts. For some of those, such as the translation of “loop for ever”, PA proves that they never halt, and with such a combinator in place of C the sentence would be provable. The sentence must speak of the program that actually searches the theorems of Θ.

Provability as a sentence

The second step of the route carries the proof of the first theorem from consistency out inside PA. That proof is an argument about numbers and programs: if Θ is consistent, then the diagonal program of Θ does not halt on its own code. To run it inside PA, arithmetic has to say not only that Θ proves ⊥ but that it proves any given sentence.

Definition 8.44 (the provability sentence). The provability sentence of φ says that the program that waits for φ stops.

Formally, let Θ be a specification in ΣA, let φ be a sentence of ΣA, and let Wφ be the program

procedure W(e)                     -- the input is ignored
    for each theorem psi of Theta, as LIST prints them:
        if psi is phi:  halt

The provability sentence of φ is

ProvΘ(φ):=[Halts(Wφ0―)].

In words, ProvΘ(φ) says “Θ proves φ”: by Lemmas 8.15 and 8.29, N⊨ProvΘ(φ) exactly when Θ⊢NKφ. The program CΘ of the consistency sentence is W⊥, and the translation of a negation is the negation of the translation, so ConΘ is ¬ProvΘ(⊥).

The sentence [Halts(Dd―)] also says “Θ proves γ”, through the diagonal program. Write h for it, so that γ is ¬h. Three facts about these sentences carry the proof of the first theorem into PA. Each is a true sentence, and each says something that proof used; what is needed is that PA proves it.

Fact 8.45 (what arithmetic proves about provability). Let Θ be a specification in ΣA with PA⊆Θ. Then PA proves each of the following.

  1. The diagonal program does what it says: h→ProvΘ(γ).

  2. The theorems are closed under (→E): ProvΘ(φ)∧ProvΘ(¬φ)→ProvΘ(⊥), for every sentence φ.

  3. True halting is provably provable: [Halts(M)]→ProvΘ([Halts(M)]), for every combinator M.

Each part is true for a reason that PA can follow, and the work is in checking that it can. In each the reasoning is an induction inside PA, on a number about which PA knows nothing in advance: a row of a run, a string in the list, a run of any length. This is where the induction axioms of PA do work that the fact that true halting is provable (Fact 8.39) does not need.15

  • (i). The formula HaltsA follows the leftmost run, and PA proves that this run is unique: two tables with the same first row agree row by row, by induction on the row number. So h speaks of one definite run of D on its own code, and ProvΘ(γ) of one definite run of Wγ on 0. Each run carries out the search of LIST, one string at a time, and stops at the first theorem that equals γ, which for D on its own code is the sentence it waits for. Following each run by induction on the row number, with the invariant that every row is a stage of the search, PA proves that each halts exactly when some string is a derivation of γ from Θ. So the two halt together.

  • (ii). If LIST prints φ and ¬φ, it has met derivations of both. The tree that joins them by (→E) is a derivation of ⊥ with its open hypotheses in Θ, and LIST meets it later, since it tries every string. The joined string is computed from the two by arithmetic on their codes, and checking it comes down to checking its parts. That the search reaches it is again an induction along the run of W⊥.

  • (iii). The reason for the fact that true halting is provable (Fact 8.39) is a recipe: from numbers that pack a run of M, it writes down a derivation of [Halts(M)] from PA, one calculation for each row. The recipe is a program, and part (iii) says that PA proves that the recipe works for every run, including runs whose numbers it knows nothing about except that they pack a run. That takes induction, on the length of the run and on the size of the numbers checked. It is also where PA⊆Θ is used: the derivations that the recipe writes have their open hypotheses in PA, so they are derivations from Θ.

With the three facts, the proof of the first theorem from consistency can be carried out inside PA.

Lemma 8.46 (arithmetic knows the first theorem). If Θ is a specification in ΣA with PA⊆Θ, then

PA⊢NKConΘ→γΘ.

Proof. From PA and the hypothesis h, the parts of Fact 8.45 give, in turn,

ProvΘ(γ)part (i)ProvΘ(h)part (iii), with M=Dd―ProvΘ(⊥)part (ii), with φ=h, since γ is ¬h.

These are the three moves of the first step of the proof of the theorem from consistency, said in arithmetic: Dd― halts, so Θ proves γ; it then also proves that Dd― halts; and a sentence with its negation gives ⊥. The sentence ConΘ is ¬ProvΘ(⊥), so (→E) derives ⊥ from PA, h and ConΘ. Discharging h by (→I) gives ¬h, which is γ, and discharging ConΘ gives ConΘ→γ. □

Theorem 8.47 (the second incompleteness theorem). If Θ is a consistent specification in ΣA with PA⊆Θ, then Θ⊬NKConΘ.

Proof. Suppose Θ⊢NKConΘ. Since PA⊆Θ, the lemma that arithmetic knows the first theorem (Lemma 8.46) gives Θ⊢NKConΘ→γΘ, and (→E) gives Θ⊢NKγΘ. Since Θ contains PA, it proves [Halts(M)] for every combinator M that halts (Fact 8.39), so this contradicts the first incompleteness theorem from consistency (Theorem 8.40). So Θ does not prove ConΘ. □

In words: a consistent specification of arithmetic cannot prove its own consistency. By the completeness of NK, it follows that Θ⊭ConΘ: some model of Θ makes ConΘ false. So this is a limit on what a specification entails, and not only on how well it fits N. Unlike the theorem from consistency, it needs PA⊆Θ in earnest, and not only the true sentences about halting: the argument runs inside PA, with its induction.

Remark 8.48 (what this did to Hilbert’s programme). The programme asked for two things about arithmetic: axioms that prove every truth, and a proof, by means everyone accepts, that the axioms never lead to a contradiction. The first incompleteness theorem rules out the first of these. The second incompleteness theorem rules out the second, in the form intended. The means everyone accepts are, at the very most, those of PA, and the finitary reasoning the programme had in mind is usually taken to be far weaker. Even PA cannot prove its own consistency, let alone that of anything stronger.

How completely this ends the programme depends on what “finitary” means, and that is still argued over. The consistency of PA can be proved by an induction that PA cannot carry out (the History tells the story), and whether that induction is finitary is a matter of judgement, not of proof. Nor does N settle the question. It satisfies PA, so PA is consistent; but that certificate is an infinite structure, which is what the programme set out to do without, and the axioms cannot issue it for themselves.

Remark 8.49 (consistent but not sound). The specification PA is consistent, since it is sound. So, by the theorem, PA does not prove ConPA. It follows that PA together with ¬ConPA is consistent. A derivation of ⊥ from it would give, by (→I), a derivation of ¬¬ConPA from PA, and then, since NK is classical, one of ConPA, which the theorem rules out.

But PA with ¬ConPA added is not sound, since ¬ConPA says that PA is inconsistent, which is false. A consistent theory can prove something false about the numbers, and even something false about itself.

8.5 Defining Halting (optional)

This section proves part (v) of the lemma that computation is definable (Lemma 8.27), which the main line used with only a sketch of its proof, and shows that the formula can be written with every universal quantifier bounded, the form that Fact 8.39 (true halting is provable) needs. Parts (i)–(iv) come from the same pieces. The main line uses these results, not their proofs.

Rather than present the formula and then check it, we work it out by unfolding what it has to say. We want a formula HaltsA(x) that is true of the code of a combinator M exactly when M halts. By definition, M halts when it runs to a normal form, and M runs to a combinator when a finite chain of steps leads from one to the other. So HaltsA has to say: there are k and combinators M0,…,Mk with M0=M, with Mi⇝Mi+1 for each i<k, and with Mk in normal form. In symbols, pretending for a moment that we may quantify over combinators, and over lists of them of any length,

∃k∃M0⋯∃Mk(M0=M∧∀i<k(Mi⇝Mi+1)∧Nf(Mk)).

Four things in this line are not yet arithmetic, and the section deals with them in turn.

  1. The list M0,…,Mk has a length that is not fixed in advance, and a formula has only a fixed number of quantifiers.

  2. Each Mi is a combinator, not a number.

  3. Mi⇝Mi+1 is a step, a relation between combinators.

  4. M0=M and “Mk is in normal form” say how the run starts and how it ends.

Each becomes a statement about digits at positions, and so, in the end, about remainders, which + and × express.

(a) A list as two numbers

The list has to be packed into a fixed number of numbers. Write rem(a,m) for the remainder of a on division by m, for m≥1. The packing uses the function

β(a,b,i):=rem(a, 1+(i+1)b),

called Gödel’s β-function. One fact from elementary number theory is needed, and we prove it.

Lemma 8.50 (the Chinese remainder theorem). Suppose that

  • m0,…,mn are positive integers, no two of which have a common factor greater than 1, and

  • k0,…,kn are numbers with ki<mi for each i.

Then there is a number a with rem(a,mi)=ki for every i≤n.

In words: when the divisors share no factor, the remainders can be chosen independently of one another, and some number has all of them. (With the divisors 2 and 4 they cannot: no number leaves remainder 0 on division by 2 and 1 on division by 4.)

Proof. The idea is to count: there are exactly as many numbers below the product of the mi as there are lists of remainders. Let P=m0m1⋯mn, and send each number a<P to its list of remainders (rem(a,m0),…,rem(a,mn)). Two different numbers a<a′<P have different lists. For if the lists were equal, every mi would divide a′−a. Then their product P would divide a′−a too. To see this, write P as a product of powers of different primes. Take one of them, pk. The prime p divides some mi, since a prime that divides a product divides one of its factors. It divides no other ml, so all k factors p of P come from that one mi. So pk divides mi, and therefore divides a′−a. A number divisible by the powers of different primes is divisible by their product, by the uniqueness of factorisation into primes, so P divides a′−a. But 0<a′−a<P, so P cannot divide a′−a. So the map is one-to-one. There are P numbers below P, and P possible lists of remainders, so every list is the list of some a, and in particular the list (k0,…,kn). □

Lemma 8.51 (packing a sequence). For every finite sequence of numbers k0,…,kn there are numbers a and b such that β(a,b,i)=ki for every i≤n.

In words: every finite list of numbers, however long, can be stored in two numbers, and read back one entry at a time by taking remainders.

Proof. Let j be the largest of n,k0,…,kn, let b=j!, and let mi=1+(i+1)b for i≤n. We check the two hypotheses of the Chinese remainder theorem.

  • ki<mi. We have ki≤j≤j!=b<mi, since j≤j! for every number j (for j=0 because 0!=1).

  • No two of the mi have a common factor. Suppose a prime p divides mi and ml with i<l. Then p divides their difference (l−i)b. It does not divide b: if it did, it would divide mi−1, which is a multiple of b. It would also divide mi, and so their difference 1. So p divides l−i. But 1≤l−i≤n≤j, so l−i divides j!=b, and then p divides b after all, which is a contradiction.

The Chinese remainder theorem now gives a with rem(a,mi)=ki, which says β(a,b,i)=ki. □

Example 8.52 (packing 2,0,3). For the sequence 2,0,3 the proof takes j=3, b=3!=6 and the divisors 7, 13, 19; the Chinese remainder theorem gives a=611, and indeed 611=87×7+2=47×13+0=32×19+3. The proof’s b is generous: the smallest pair that packs the sequence is a=80, b=2.

The function β is definable: β(a,b,i)=v exactly when N makes true

B(a,b,i,v):=∃q(a=q×s(s(i)×b)+v∧v<s(s(i)×b)),

since s(s(i)×b) is 1+(i+1)b.

When β(a,b,i) appears inside a formula as if it were a term, as in β(a,b,i)=1―, the formula abbreviates one that says “there is a v with B(a,b,i,v) and v=1―”. Since β is a function, nothing is lost.

We write ∀i<Nφ for ∀i(i<N→φ), ∃i<Nφ for ∃i(i<N∧φ), and ∀i≤N and ∃i≤N in the same way; and ∃p,q≤Nφ for ∃p≤N∃q≤Nφ. In a sum such as p+3, the number 3 stands for its numeral 3―.

The abbreviations for β bring in quantifiers. Every one of them, wherever it stands, can be bounded by a, since a quotient or a remainder of a is at most a. Every other quantifier below ranges over the rows of a table or the positions in a row, and is bounded by the number of rows or the length of a row. Written so, HaltsA has unbounded quantifiers only in its leading block of ∃. That is the form needed by Fact 8.39.

(b) Combinators as rows

Each combinator of the run is read as its string, a row of digits.

Definition 8.53 (the string of a combinator). The string of a combinator is the combinator written out with all its brackets, the string that its code spells.

Formally, str(M) is defined by recursion on the shape of M:

str(K):=K,str(S):=S,str(M1M2):=(str(M1)str(M2)).

Let M0⇝M1⇝⋯⇝MN be a run. Row i of its table is str(Mi), written in the digits used for codes: 1 for K, 2 for S, 3 for ( and 4 for ). The rows have different lengths, so the table is described by packed sequences of three kinds:

Len(i):=β(a1,b1,i),Dg(i,j):=β(a2,b2,i×W+j),Ct(i,j):=β(a3,b3,i×s(W)+j),

for the length of row i, the digit at position j of row i, and the bracket count of row i before position j, where W is a number at least as large as every length. The bracket count is the number of opening brackets among the first j digits, less the number of closing ones.

The clause Rows says that the numbers mean what was just said. It is the conjunction, for all i≤N, of:

  • Len(i)≤W;

  • for every j<Len(i), the digit Dg(i,j) is one of 1―, 2―, 3―, 4―;

  • Ct(i,0)=0;

  • for every j<Len(i), the count goes up by one at a digit 3―, down by one at a digit 4― (written Ct(i,j)=s(Ct(i,s(j)))), and stays the same at the others.

Two rows of cells. Row i holds the string ( S ( ( K K ) S ) ), with digits 3 2 3 3 1 1 4 2 4 4 beneath. Its positions 2 to 8 are outlined as a K redex, ((K P) Q), with P the K at position 5 and Q the S at position 7. Row i+1 holds ( S K ), digits 3 2 1 4. Arrows copy X, the first two cells, to the first two cells of row i+1; P, at position 5, to position 2; and Y, the last cell, to position 3.
Figure 8.3. A step is the replacement of a stretch.

(c) One step

A step copies most of one row into the next and changes one stretch of it (Figure 8.3). A stretch of row i is the part from a position p up to, but not including, a position q. In the string of a combinator, the stretches that are themselves strings of combinators are the strings of its parts. Call them the term stretches: a single K or S, or an opening bracket together with everything up to the closing bracket that matches it. The matching bracket is where the count first comes back to its value at p:

T(i,p,q):=(q=s(p)∧(Dg(i,p)=1―∨Dg(i,p)=2―))∨(Dg(i,p)=3―∧p<q∧Ct(i,q)=Ct(i,p)∧∀r<q(p<r→Ct(i,p)<Ct(i,r))).

A row is the string of a combinator exactly when it is one term stretch and every opening bracket in it opens a stretch made of two term stretches and a closing bracket:

Wf(i):=T(i,0,Len(i))∧∀p<Len(i)(Dg(i,p)=3―→∃u,v≤Len(i)Pair(i,p,u,v)),

where Pair(i,p,u,v) is T(i,s(p),u)∧T(i,u,v)∧Dg(i,v)=4―: after the bracket at p come two term stretches, from p+1 to u and from u to v, and then a closing bracket.

With term stretches in hand, the step itself can be described. A step rewrites one part of a combinator that is a redex, and leaves the rest alone. In the string, it replaces one stretch:

RedexRow iRow i+1
KX ((KP)Q) YX P Y
SX (((SP)Q)R) YX ((PR)(QR)) Y

Here P, Q and R are term stretches, and X and Y are the rest of the row, unchanged. Figure 8.3 shows one K step written this way, from (S((KK)S)) to (SK), with X=(S, P=K, Q=S and Y=). The new row is made of three copies from the old one, and nothing else.

Write ℓX, ℓP, ℓQ and so on for the lengths of these pieces, and p for the position where the redex starts, which is ℓX. A K redex at p is then described by

RedK(i,p,ℓP,ℓQ):=Dg(i,p)=3―∧Dg(i,p+1)=3―∧Dg(i,p+2)=1―∧T(i,p+3,p+3+ℓP)∧Dg(i,p+3+ℓP)=4―∧T(i,p+4+ℓP,p+4+ℓP+ℓQ)∧Dg(i,p+4+ℓP+ℓQ)=4―∧p+4+ℓP+ℓQ<Len(i).

A copy of a stretch is described by

Cp(i,p,i′,p′,ℓ):=∀j<ℓ(Dg(i′,p′+j)=Dg(i,p+j)),

which says that the ℓ digits of row i′ from p′ are those of row i from p. A K step from row i to row i+1 is

NextK(i):=∃p,ℓP,ℓQ,ℓY≤Len(i)(RedK(i,p,ℓP,ℓQ)∧Len(i)=p+ℓP+ℓQ+ℓY+5∧Len(s(i))=p+ℓP+ℓY∧Cp(i,0,s(i),0,p)∧Cp(i,p+3,s(i),p,ℓP)∧Cp(i,p+ℓP+ℓQ+5,s(i),p+ℓP,ℓY)).

The three copies are X, P and Y, each put in its place in the new row. The formulas RedS(i,p,ℓP,ℓQ,ℓR) and NextS(i) are written in the same way from the S line of the table above, with seven fixed digits in row i, six in row i+1, six copies (X, P, Q, R twice and Y), and the bound p+6+ℓP+ℓQ+ℓR<Len(i). This bound, like the last line of the K formula, keeps every position inside the row, where the digits are fixed by Rows. We do not write the S formulas out here; Exercise 8.15 writes the first and lays out the second.

Let Next(i) be NextK(i)∨NextS(i). A redex starts at position r of row i when

Redex(i,r):=∃ℓP,ℓQ≤Len(i)RedK(i,r,ℓP,ℓQ)∨∃ℓP,ℓQ,ℓR≤Len(i)RedS(i,r,ℓP,ℓQ,ℓR),

and row i has no redex when

Normal(i):=∀r≤Len(i)¬Redex(i,r).

A combinator can have many runs, since a step may rewrite any of its redexes, and HaltsA will follow only one. The leftmost run rewrites, at each step, the redex whose stretch starts first in the row. A term stretch is fixed by the position where it starts, so different redexes start at different positions; the leftmost run therefore takes one definite step at each stage, and is unique. A leftmost step from row i is a step whose redex starts at a position p before which no redex starts. Let NextKL(i) be NextK(i) with the clause

∀r<p¬Redex(i,r)

added next to RedK(i,p,ℓP,ℓQ), let NextSL(i) be obtained from NextS(i) in the same way, and let NextL(i) be their disjunction.

Nothing is lost by following the leftmost run. A redex that lies inside another starts after it, so the redex that starts first is the leftmost of the outermost redexes. By the normalisation theorem for combinators, stated in Chapter 1 and taken on loan there, the run that always rewrites that redex reaches a normal form whenever the combinator has one. We use this theorem only as a fact about combinators, to see what the formula is true of; nothing is proved about it inside PA.

Lemma 8.54 (a step is the replacement of a stretch). For all combinators M and M′:

  1. M⇝M′ exactly when str(M′) is obtained from str(M) by one of the two replacements of the table, with P, Q and R term stretches;

  2. M is in normal form exactly when str(M) has no stretch of either form in the column “Row i” of the table, with P, Q and R term stretches.

In words: a step can be done on the string, by cut and paste, without ever reading the combinator as a tree.

Proof. We show first that the term stretches of str(M) are exactly the strings of the parts of M. Two facts about the bracket count are needed, both proved by induction on a combinator N.

  • Along str(N) the count never falls below its value at the start of str(N).

  • At the end of str(N) the count is back to that value, and, when N is an application, it is not back to it any earlier.

The claim is proved by induction on M. If M is K or S, its string has one symbol and M has one part. If M is M1M2, its parts are M itself and the parts of M1 and of M2, and str(M) is an opening bracket, str(M1), str(M2) and a closing bracket. The whole string is the string of M, and it is a term stretch by the second fact. By the induction hypothesis, the term stretches that lie inside str(M1) or inside str(M2) are the strings of the parts of M1 and M2. There are no other term stretches.

  • One that begins at the first bracket of str(M) ends where the count first comes back to its value at the start, which by the second fact is the end of str(M). So it is the whole string.

  • One that begins with a bracket inside str(M1) ends inside str(M1). Let c be the count just before that bracket. By the first fact, c is at least the count b at the start of str(M1). After the bracket the count is c+1, and at the end of str(M1) it is back to b. Since it moves by one at a time, it comes back to c by then.

  • One that begins with a bracket inside str(M2) ends inside str(M2), in the same way.

A term stretch that is a single K or S lies inside str(M1) or str(M2), so the list is complete.

It follows that a stretch of either form in the column “Row i”, with P, Q and R term stretches, is exactly the string of a part of M that is a redex. The two claims of the lemma follow.

  • (i). A step rewrites one part of M that is a redex, by (K) or (S). The rules (app1) and (app2) carry the rewriting out to the whole term, each putting back one pair of brackets around it and leaving the rest of the string as it was. So the string of the result is the string of M with that stretch replaced, as in the table. Conversely, each replacement of the table rewrites the string of one redex part in this way, and so gives the string of the result of a step. Since different combinators have different strings, M′ is that result.

  • (ii). A combinator is in normal form exactly when it has no part that is a redex.

□

(d) The ends of the run

The last row must be in normal form, which is Normal(N); the first must be the string of the combinator with code x. The digits of row 0 are read off by a fourth packed sequence: Val(j):=β(a4,b4,j) is the number that the first j digits of row 0 spell in base 5. Let Start(x) be the conjunction of

  • Wf(0), which says that row 0 is the string of a combinator;

  • Val(0)=0, Val(Len(0))=x, and Val(s(j))=5―×Val(j)+Dg(0,j) for every j<Len(0), which say that its digits spell x.

Putting it together

Let HaltsA(x) be

∃N∃W∃a1∃b1⋯∃a4∃b4(Rows∧Start(x)∧∀i<NNextL(i)∧Normal(N)).

The formula HaltsA(x) says that there is a table of N+1 rows whose first row is the combinator with code x, whose later rows are each one leftmost step from the row before, and whose last row is in normal form. Each piece of the line we started from has its counterpart:

  • there are k and M0,…,Mk became ∃N∃W∃a1∃b1⋯∃a4∃b4: the length of the run and the numbers that pack its table;

  • each Mi is a combinator became Rows, with Wf;

  • M0=M became Start(x);

  • Mi⇝Mi+1 for each i<k became ∀i<NNextL(i), with the step chosen as the leftmost one;

  • Mk is in normal form became Normal(N).

The other formulas of the lemma come from the same pieces. The formula Comb(x) says that there is a table of one row with Rows and Start(x); the formula NfA(x) adds Normal(0); and StepA(x,y) asks for a table of two rows, the first spelling x, the second spelling y, with Next(0). For App(x,y,z), the string of MN is an opening bracket, the string of M, the string of N and a closing bracket, so

⌜MN⌝=3⋅5ℓ+m+1+⌜M⌝⋅5m+1+⌜N⌝⋅5+4,

where ℓ and m are the numbers of digits of ⌜M⌝ and ⌜N⌝; the powers of 5 form a sequence 1,5,25,…, which is packed and unpacked like any other.

Proof of part (v) of the lemma that computation is definable. Let M be a combinator and e its code; parts (i)–(iv) are proved in the same way, from the same pieces.

  • If M halts, the formula is true of e―. Take the leftmost run M=M0⇝⋯ of M. Since M has a normal form, the normalisation theorem for combinators says that this run reaches one, say MN. Let W be the largest of the lengths of the strings str(Mi), and pack the lengths, the digits, the bracket counts and the values of the first digits of row 0 by the packing lemma (Lemma 8.51), in the orders stated. The resulting numbers make every clause true:

    • Rows, by the choice of the sequences;

    • Start, since row 0 is the string of M;

    • each NextL(i), and Normal(N), by the lemma that a step is the replacement of a stretch (Lemma 8.54): the stretch replaced in row i is the string of the redex that the leftmost run rewrites, and no redex starts before it.

  • If the formula is true of e―, then M halts. Take numbers that make the clauses true for e―. By Start and Rows, row 0 is the string of a combinator whose digits spell e, so it is str(M). By induction on i≤N, row i is the string of a combinator Mi with M⇝∗Mi: for the step from i to i+1, the clause NextL(i) says, among other things, that row i+1 is row i with a stretch replaced as in the table. The stretch replaced is the string of a part of Mi, and it is replaced by the string of a combinator, so row i+1 is the string of a combinator Mi+1. By the lemma that a step is the replacement of a stretch, Mi⇝Mi+1. By Normal(N) and the same lemma, MN is in normal form. So M halts, which is what was to be shown.

□

The definitions of this section can be tested against the combinators themselves, and have been.16

8.6 Decidable Theories (optional)

Nothing later depends on this section. It asks which structures, other than finite ones, can be captured, and proves one case in full. It ends with a remark on the structures that satisfy every truth of arithmetic and are not N.

By Proposition 8.18, a structure can be captured exactly when its truths can be decided, so the question becomes a search for decision procedures. The main tool in that search is quantifier elimination.

Definition 8.55 (quantifier elimination). A set of sentences Θ admits quantifier elimination if for every formula φ there is a formula ψ such that

  • ψ has no quantifiers,

  • ψ has no free variables other than those of φ, and

  • Θ⊨∀x¯(φ↔ψ), where x¯ lists the free variables of φ.

In words: every question that Θ can be asked, however many quantifiers it has, is equivalent under Θ to one without any. When φ is a sentence, ψ is a sentence without quantifiers, built from atomic sentences about the constants alone, and so it is often easy to settle.

The first example is the rationals with their order, an infinite structure captured by a short list of the properties of its order.

Definition 8.56 (dense linear order). The specification DLO (for dense linear order) consists of the equality axioms for the signature {<,=} and the following sentences.

  • Irreflexive: ∀x¬(x<x).

  • Transitive: ∀x∀y∀z((x<y∧y<z)→x<z).

  • Linear: ∀x∀y(x<y∨x=y∨y<x).

  • Dense: ∀x∀y(x<y→∃z(x<z∧z<y)).

  • No end points: ∀x∃y(y<x) and ∀x∃y(x<y).

The rationals (Q,<) make every one of these sentences true.

Theorem 8.57 (a dense order is captured). The specification DLO admits quantifier elimination, and it captures (Q,<).

In words: six sentences and the equality axioms say everything true about the order of the rationals.

Proof. By the completeness of NK it is enough to work in an arbitrary structure that satisfies DLO, so the equivalences below are claims about every such structure. We eliminate quantifiers by induction on φ. The connectives are immediate, ∀x is ¬∃x¬, and the only case with content is ∃xψ with ψ already free of quantifiers. The case is settled in four moves.

  1. Write ψ in disjunctive normal form and move ∃x inside the disjunction, so that it remains to treat ∃x(λ1∧⋯∧λk) with literals λi.

  2. Remove negations: ¬(u<v) is equivalent to v<u∨u=v, and u≠v to u<v∨v<u, by the order axioms; distribute again. Conjuncts that do not mention x move outside the quantifier.

  3. If x<x is a conjunct, the conjunction is false. A conjunct x=x can be dropped. If x=y or y=x is a conjunct for a variable y other than x, then ∃x(x=y∧χ) is equivalent to χ[y/x].

  4. What remains is ∃x(y1<x∧⋯∧yl<x∧x<z1∧⋯∧x<zr), and it is equivalent to the conjunction of all yi<zj. In one direction this is transitivity. In the other, take the largest yi and the smallest zj, which exist since the order is linear. By hypothesis the first is below the second, and density gives an x between them. If there are no yi, or no zj, the absence of a least or greatest element gives x, and the conjunction is empty and true.

For a sentence, the quantifier-free equivalent has no variables and no constants, so it is built from ⊥ by the connectives and is provably true or provably false. So, for every sentence φ, the specification DLO proves φ or proves ¬φ. As (Q,<) satisfies DLO, the specification proves only truths about (Q,<), by soundness. So a true sentence φ is proved, since otherwise ¬φ would be proved and true. Hence DLO captures (Q,<). □

The proof is an algorithm: each move rewrites a formula, and the rewriting ends. So it decides the truths of (Q,<) directly, without the listing of theorems.

Quantifier elimination reaches further than orders.

Remark 8.58 (addition without multiplication). The counting numbers with 0, s, + and < but without × can also be captured, by the axioms of PA that do not mention ×, with induction for the formulas of the smaller language. The proof is again by quantifier elimination, after one addition: for each k and r, a symbol for “x leaves remainder r on division by k”, a relation that can already be written with + alone.17 The definable sets of numbers are then easy to describe: each is, beyond some point, periodic, like the even numbers.

Remark 8.59 (the real numbers). The real numbers with 0, 1, +, × and < can be captured too, by the axioms of an ordered field in which every positive number has a square root and every polynomial of odd degree has a root. The proof is once more by quantifier elimination, now of polynomial inequalities.18 It follows that the sets of reals definable in one variable are finite unions of points and intervals. The counting numbers are not such a set, so they cannot be defined among the reals. The reals contain them, and yet are the tamer of the two.

Remark 8.60 (why multiplication is the dangerous addition). In none of the three infinite structures of this section can a finite sequence be packed into numbers and unpacked again by a formula. With + and × together on the counting numbers, the β-function does exactly that, and with it every halting run is definable. The undecidability of arithmetic then follows from the lemma that arithmetic contains computation (Lemma 8.29) alone.

Even the simplest sentences of arithmetic are affected. No program decides whether a polynomial equation with integer coefficients has a solution in the counting numbers. That question is asked by a sentence whose only quantifiers are existential ones in front of an equation.

Remark 8.61 (non-standard models). The first incompleteness theorem (Theorem 8.34) can also be read through structures. The sentence γ does not follow from Θ, so by the completeness of NK some model M of Θ makes it false. In N it is true, so M is not N, nor a copy of it: it satisfies every sentence of Θ and still disagrees with N about whether D halts on its own code. Both are models of Θ, since Θ is sound, and a model of Θ that is not a copy of N is called a non-standard model of Θ. This one is not a model of Th(N), since it makes the true sentence γ false.

The disagreement has to live somewhere. In M the sentence ¬γ is true, and it claims that a halting run exists. When Θ contains PA one can show, though we do not here, that the numerals 0―,1―,2―,… of M behave exactly as the counting numbers do, so no numeral codes such a run. The run is coded by an element beyond every numeral, an element that no closed term names, and read in M it is an infinitely long “run” that no machine performs.

Non-standard models are not only the price of incompleteness. Even Th(N), which leaves no truth unproved, has them. Add a new constant c and, for every n, the sentence n―<c. Every finite part of this set has a model, namely N with c read as a large enough number, so by compactness the whole set has one, and in it c names an element beyond every numeral. Forget c, and the result satisfies every sentence true in N without being a copy of N: a non-standard model of Th(N) itself. No set of first-order sentences pins the counting numbers down.19

Figure 8.4 summarises the chapter’s answers.

Structure or questionCaptured?Truths decidable?
a finite structureyes, by its tableyes, by evaluation
propositional validity(no structure)yes, by DPLL
(Q,<)yes, by DLOyes, by quantifier elimination
(N,0,s,+,<)yesyes, at great cost
(R,0,1,+,×,<)yesyes, at great cost
(N,0,s,+,×,<)nono
first-order validity(no structure)no; listable by REFUTE
Figure 8.4. What can be captured and decided.

History

The question of this chapter was asked as a programme. Hilbert’s Foundations of Geometry of 1899 set out axioms for Euclid’s geometry from which every theorem followed by logic alone, with nothing taken from the diagrams. In his address to the International Congress of Mathematicians in Paris in 1900, the second of his problems asked for a proof that the axioms of arithmetic (for Hilbert, those of the real numbers) are consistent.20 In the 1920s the request grew into Hilbert’s programme: to write the whole of mathematics in formal systems, and to prove, by elementary reasoning about finite strings of symbols, that those systems are consistent and that they settle every question.

The programme was answered in Königsberg in September 1930, at two meetings a day apart. On 7 September a conference on the epistemology of the exact sciences held a round-table discussion on the foundations of mathematics. There Kurt Gödel, aged twenty-four, remarked that there are true sentences of arithmetic that a consistent formal system cannot prove. Almost nobody took it in. John von Neumann did, and spoke with him afterwards. On 8 September Hilbert addressed the Society of German Scientists and Physicians in the same city, and closed with the words Wir müssen wissen. Wir werden wissen.21

Von Neumann, who had heard the first incompleteness theorem at Königsberg, found the second independently and wrote to Gödel on 20 November 1930 to say so. Gödel had announced both a few weeks earlier. The first was published in 1931, together with a sketch of the second.22

Gödel’s proof is not the one of this chapter. He coded formulas and derivations by numbers. He showed that the relation “p is the number of a derivation of the sentence with number f” can be expressed in the formal system itself, with its true instances provable there. Then, by substituting a formula’s own number into it, he built a sentence that says of itself that it is not derivable: the sentence of Remark 8.36, reached by coding instead of by a program. The general form of this step, the fixed-point lemma, was stated by Carnap in 1934.

From consistency alone Gödel’s argument shows that the sentence is not derivable; to show that its negation is not derivable either, he assumed ω-consistency, a condition between consistency and soundness. Rosser removed that assumption in 1936, by the cleverer sentence of Remark 8.41.23

The second theorem did not leave the consistency of arithmetic in doubt. In 1936 Gentzen, whose natural deduction this course uses, proved PA consistent by an induction longer than any that PA itself can carry out, as the second theorem says he must.24

Computation came next. In 1936 Church showed that no effectively calculable function decides whether a term of his λ-calculus has a normal form (the halting theorem, Theorem 8.2, is the same fact for its cousin, the combinators). In a short note of the same year he deduced that no mechanical procedure decides first-order provability, and so, by the completeness theorem, validity.25 Turing reached the same conclusion independently and by a different route, and the next year showed that his machines compute exactly the functions that Church’s calculus defines, the fact behind the Turing completeness of the combinators.26

The first of Turing’s papers defines his machines, proves by a diagonal argument that no machine decides whether a machine is “circle-free”, and deduces that none decides whether a machine ever prints a given symbol. In its eleventh section it writes, for each machine, a formula of first-order logic that is derivable exactly when the machine prints that symbol: an ancestor of the construction of Section 8.1, with machines in place of combinators and printing in place of halting. The paper does not state the undecidability of the halting problem, and does not use the word “halting”. The self-referential argument for halting in its now standard form is in Kleene’s Introduction to Metamathematics of 1952, and the name “halting problem” first appears in print in Davis’s Computability and Unsolvability of 1958. But Turing’s printing problem and the halting problem are equivalent, and the credit given to Turing is fair in substance if not in letter.27

What “formal system” meant was settled only by the machines. In 1963, and again in 1964, Gödel wrote that Turing’s analysis gave “a precise and unquestionably adequate definition of the general notion of formal system” (in 1964, “concept” in place of “notion”), and that the incompleteness theorems therefore hold for every consistent formal system that contains a little arithmetic.28

The decidable cases came first. Presburger showed in 1929 that the counting numbers with addition alone can be captured and decided. By 1930 Tarski had a decision procedure for the real numbers with addition and multiplication, though it was published only after the war. In 1974 it was shown that every procedure for Presburger’s structure is enormously expensive.29 The last word on the undecidable side came in 1970, when Matiyasevich completed the work of Davis, Putnam and Julia Robinson and answered the tenth of Hilbert’s problems of 1900: no procedure decides whether a polynomial equation with integer coefficients has a solution in whole numbers.30

The schoolroom problem has a history of its own. The eleven identities are in Dedekind’s Was sind und was sollen die Zahlen? of 1888. Tarski asked in the 1960s whether they derive every true identity; the question is in print in a paper of 1969 with Doner.31 Wilkie found his identity in 1981, and the paper describing it was published in 2000.32 Gurevič gave the first counter-model, with 59 elements, in 1985, and proved in 1990 that no finite list of identities derives every true one.33 Smaller counter-models followed, down to a twelve-element one of Burris and Yeats, who conjectured that twelve is the least. A computer search by Zhang in 2005 ruled out fewer than eleven.34 Meanwhile Macintyre had shown in 1981 that the set of all true identities is decidable.35 In 2026 Subercaseaux and Przybocki proved the conjecture with a SAT solver, as the introduction describes, and classified the twelve-element counter-models: up to isomorphism there are 8957952 of them.36 At about the same time, and with a SAT encoding of their own, Hajdari and Niederhauser also ruled out eleven elements and found twelve-element counter-models other than that of Burris and Yeats.37

Every undecidability result of the chapter is a diagonal argument, and the diagonal is older than all of them. Figure 8.5 lines up four of its appearances. Each starts from a list, applies each entry of the list to its own index, and twists the result, so that the twisted diagonal differs from every entry of the list. Figure 8.6 collects the dates.

WhoThe listEach applied to itselfThe twistWhat follows
Cantor, 1891infinite sequences of 0s and 1sthe nth digit of the nth sequencechange itthe list misses a sequence
Russell, 1901all setsis the set a member of itself?take those that are notthe sets not members of themselves form no set
haltingall programsdoes the program halt on its own code?do the oppositeno program decides halting
the program Dthe theorems of Θdoes Θ say program e does not halt on e?halt exactly thenΘ misses a truth
Figure 8.5. One argument, four times.
WhoWhenWhat
Dedekind1888the eleven identities
Hilbert1899; 1900axioms for geometry; the consistency of arithmetic asked for
Presburger1929addition alone is decidable
Tarskiby 1930; 1948the real numbers are decidable
Gödel1930; 1931the incompleteness theorems
Church1936having a normal form is undecidable
Church; Turing1936first-order validity is undecidable
Rosser1936a sentence neither proved nor refuted, from consistency alone
Gentzen1936the consistency of PA, from outside it
Kleene; Davis1952; 1958the halting argument; the name
Matiyasevich1970polynomial equations are undecidable
Wilkie1981a true identity the eleven do not derive
Gurevič1985; 1990a counter-model; no finite list suffices
Subercaseaux, Przybocki2026the least counter-model has twelve elements; all of them classified
Hajdari, Niederhauser2026no eleven-element counter-model, by a second encoding
Figure 8.6. Incompleteness: who did what.

Summary

A program is a combinator, and no program decides whether a program halts: a predictor of halting, run on its own code, would contradict itself. Chapter 1’s rules for running a combinator, read as sentences, make a finite theory Π, the same for every program: a derivation by the rules is a derivation in NK from Π, and the combinators themselves form a model of Π, so “the program halts” follows from Π exactly when it does. So first-order validity is undecidable, even for the consequences of that one set. The first-order procedure REFUTE certifies every entailment that holds and runs for ever on some that do not, and that is as good as any procedure can be.

A specification is a theory that a program can recognise. It captures a structure when the sentences that follow from it are exactly those true in the structure. If a specification captures a structure, a program decides the structure’s truths by listing theorems until the sentence or its negation appears. The converse holds too, so a structure can be captured exactly when its truths can be decided. Computation, whose truths include which combinators halt, cannot be captured. Once its elements have names, every finite structure in a finite signature is captured by finitely many sentences and the equality axioms: name the elements, say that they are different and that there are no others, and copy the tables.

The counting numbers contain computation: combinators can be coded as numbers, and steps, normal forms and halting defined with + and ×, so every sentence about computation translates into a sentence about numbers with the same truth value. So the truths about the counting numbers are undecidable, and no specification captures them. For each sound specification, the program that waits for it to say “this program does not halt on itself” gives a true sentence the specification does not prove. For a specification that proves every true sentence about halting, as one that contains Peano arithmetic does, consistency is enough in place of soundness. And a consistent specification that contains Peano arithmetic cannot prove its own consistency; by completeness, it does not even entail it. The first theorem does not show that some truths can never be known: the true sentence it names was proved true, by an argument that uses the soundness the specification cannot supply for itself (Remark 8.35).

This part of the course began with the wish never to be surprised by a system one has specified. Its three chapters have said where that wish can be met. For a system with finitely many elements, a finite list of sentences can say everything, and a program can check every claim. For a question in propositional logic, a solver can settle it, quickly in practice. For a first-order question, a search finds every proof there is, and may search for ever when there is none. For the counting numbers, the simplest infinite system there is, no specification says everything, and no program decides what is true. That is not a failure to know: it is a theorem, which is a way of knowing, and it is what Hilbert’s “we shall know” turned out to mean.

Exercises

The exercises run from practice to proof.

  • Exercises 8.1 to 8.5 are about programs, the theory of computation and reductions;

  • Exercises 8.6 to 8.10 are about specifications and finite structures;

  • Exercises 8.11 to 8.13 are about arithmetic and the incompleteness theorems;

  • Exercises 8.14 to 8.16 go with the optional sections, and are optional too.

Exercise 8.1. The combinator K(IK), that is, K(SKKK), halts. Write its run, and the lines by which the rules of Π derive that it halts, as in Example 8.5. Which sentences for steps are used, and where?

Exercise 8.2. Let X be a set of combinators that contains K and S and contains KN, SN and SNN′ whenever it contains N and N′. Show that X contains every combinator in normal form. Show that the set of combinators in normal form is itself such a set. So it is the smallest one, which is why T interprets Nf by it.

Exercise 8.3. Let G be the structure whose domain is the set of combinators, with K, S and application as in the structure T of the proof of Lemma 8.6, in which Step, Nf and Halts are true of everything. Show that G satisfies Π and makes Halts(Ω) true. Why does this not contradict the lemma that a program is a theory (Lemma 8.6)? Why does the proof of part (iv) of that lemma use T, and not just any model of Π?

Exercise 8.4. Compute the code of I=SKK. Which numbers below 500 are codes, and of which combinators?

Exercise 8.5. Show that no program decides, given the code of a program, whether that program halts on the input 0. (Find a reduction: from e and n, compute the code of a program that ignores its input and does what program e does on n.)

Exercise 8.6. Say which of the following sets of sentences are specifications, with a reason for each.

  1. The eleven identities of Remark 8.37, each with ∀ in front of its variables.

  2. The induction axioms of PA.

  3. The set of all sentences true in a structure with five elements.

  4. The set of all sentences of ΣA true in N.

  5. The set of sentences of ΣA with fewer than a hundred symbols that are true in N.

Exercise 8.7. Let A=1+x, B=1+x+x2, C=1+x3, D=1+x2+x4 and E=1−x+x2.

  1. Show that C=A⋅E and D=B⋅E.

  2. Deduce that (Ay+By)x⋅(Cx+Dx)y=(Ax+Bx)y⋅(Cy+Dy)x for all positive integers x and y.

  3. Check that E≥1 for every positive integer x, so that every quantity in the argument is a positive integer. Which step of the argument cannot be imitated with the eleven identities, and why?

Exercise 8.8. Let M be a structure whose truths are decided by a program. Prove in full that Th(M) is a specification and that it captures M. Which half of capturing uses the soundness of NK?

Exercise 8.9. The structure B has the domain {a,b,c}, and its signature has three symbols.

  • A one-place function symbol f, with f(a)=b, f(b)=c and f(c)=c.

  • A one-place relation symbol P, true of a alone.

  • The relation symbol =, interpreted as identity.

  1. Write the description ΔB of B (Remark 8.20), and count its sentences.

  2. The sentence ∀x(P(x)→¬P(f(x))) is true in B. Following the idea in Remark 8.20, describe a derivation of it from the equality axioms and ΔB: which instances are proved, and how are they combined?

Exercise 8.10. Take the equality axioms and the description ΔB of Exercise 8.9, and remove the closure sentence. Find a model of what is left in which the sentence ∀x(f(x)=x→x=cc) is false, although it is true in B. What does the example show about the closure sentence?

Exercise 8.11. Write in ΣA, using Prime and x∣y as abbreviations and with every quantifier’s scope bracketed:

  1. there are infinitely many pairs of primes that differ by 2;

  2. every number is the sum of four squares;

  3. every number greater than 1 is divisible by a prime.

Exercise 8.12. Let Θ be a specification in ΣA and γ the sentence γΘ of its diagonal program.

  1. Which step of the proof of the first incompleteness theorem fails if Θ is not assumed sound?

  2. Suppose that Θ is sound, and let Θ′ be Θ with γ added. Show that Θ′ is a sound specification. Does the first incompleteness theorem apply to Θ′, and with which sentence?

Exercise 8.13. Add a fifth row to the table of diagonal arguments in the History, for Cantor’s theorem that no function f from a set A to the set of its subsets is onto: the list, each applied to itself, the twist, and what follows.

Exercise 8.14. (Optional.) Find numbers a and b with β(a,b,i) equal to 1, 0, 1 for i=0,1,2, first by the method of the proof of the packing lemma, and then a smaller pair by trial.

Exercise 8.15. (Optional.) Write out the formula RedS(i,p,ℓP,ℓQ,ℓR) that Section 8.5 leaves to the reader, in the style of RedK. Then say where, in row i+1 of an S step, the six fixed digits stand, and where each of the six copies begins.

Exercise 8.16. (Optional.) Eliminate the quantifier from ∃x(y<x∧x<z∧x≠w) in DLO, following the four moves of the proof, and simplify the result.

References

  • Stanley Burris and Karen Yeats. The saga of the high school identities. Algebra Universalis, 52:325–342, 2004.
  • Alonzo Church. A note on the Entscheidungsproblem. Journal of Symbolic Logic, 1(1):40–41, 1936a.
  • Alonzo Church. An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2):345–363, 1936b.
  • William Craig. On axiomatizability within a system. Journal of Symbolic Logic, 18(1):30–32, 1953.
  • Martin Davis. Computability and Unsolvability. McGraw-Hill, New York, 1958.
  • John W. Dawson Jr. Logical Dilemmas: The Life and Work of Kurt Gödel. A K Peters, Wellesley, MA, 1997.
  • John Doner and Alfred Tarski. An extended arithmetic of ordinal numbers. Fundamenta Mathematicae, 65:95–127, 1969.
  • Michael J. Fischer and Michael O. Rabin. Super-exponential complexity of Presburger arithmetic. In Complexity of Computation, volume 7 of SIAM–AMS Proceedings, pages 27–41. American Mathematical Society, 1974.
  • Gerhard Gentzen. Die Widerspruchsfreiheit der reinen Zahlentheorie. Mathematische Annalen, 112:493–565, 1936.
  • Alexander V. Gheorghiu. High school algebra and the limits of AI. Mathematics Today, 61(5), October 2025. Graham Hoare Prize 2025.
  • Kurt Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38:173–198, 1931.
  • Kurt Gödel. Collected Works, Volume I: Publications 1929–1936. Oxford University Press, Oxford, 1986. Edited by Solomon Feferman and others.
  • R. Gurevič. Equational theory of positive numbers with exponentiation. Proceedings of the American Mathematical Society, 94:135–141, 1985.
  • R. Gurevič. Equational theory of positive numbers with exponentiation is not finitely axiomatizable. Annals of Pure and Applied Logic, 49:1–30, 1990.
  • Agon Hajdari and Johannes Niederhauser. SATisfying the high school identities but not Wilkie’s identity. arXiv:2608.16406, 2026.
  • Petr Hájek and Pavel Pudlák. Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin, 1993.
  • Joel David Hamkins and Theodor Nenu. Did Turing prove the undecidability of the halting problem? arXiv:2407.00680v3, 2025.
  • David Hilbert. Grundlagen der Geometrie. Teubner, Leipzig, 1899.
  • David Hilbert. Mathematische Probleme. Lecture to the International Congress of Mathematicians, Paris. Published in Nachrichten der Königlichen Gesellschaft der Wissenschaften zu Göttingen, 253–297, 1900.
  • David Hilbert. Naturerkennen und Logik. Die Naturwissenschaften, 18:959–963, 1930.
  • Stephen Cole Kleene. Introduction to Metamathematics. North-Holland, Amsterdam, 1952.
  • Angus Macintyre. The laws of exponentiation. In Model Theory and Arithmetic, volume 890 of Lecture Notes in Mathematics, pages 185–197. Springer, 1981.
  • Yuri V. Matiyasevich. Enumerable sets are Diophantine. Soviet Mathematics Doklady, 11:354–357, 1970.
  • Open Logic Project. The Open Logic Text. https://openlogicproject.org, 2026. Release 9620cc7, 12 July 2026. Licensed CC BY 4.0.
  • Mojżesz Presburger. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du I Congrès des Mathématiciens des Pays Slaves, Warszawa 1929, pages 92–101, 1930.
  • J. Barkley Rosser. Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1(3):87–91, 1936.
  • Bernardo Subercaseaux and Benjamin Przybocki. A SAT attack on Tarski’s high school algebra problem. arXiv:2608.08421v2, 2026.
  • Alfred Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley, second edition, 1951. First issued as a RAND report, 1948.
  • Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1):230–265, 1937a.
  • Alan M. Turing. Computability and λ-definability. Journal of Symbolic Logic, 2(4):153–163, 1937b.
  • Alex J. Wilkie. On exponentiation – a solution to Tarski’s high school algebra problem. Quaderni di Matematica, 6:107–129, 2000. Manuscript circulated 1981.
  • Jian Zhang. Computer search for counterexamples to Wilkie’s identity. In Automated Deduction – CADE-20, volume 3632 of Lecture Notes in Computer Science, pages 441–451. Springer, 2005.

Notes

  1. The story of this introduction, as far as Hilbert, is adapted from Gheorghiu (2025). ↩

  2. Subercaseaux and Przybocki (2026). A lemma, checked in the same way, extends the “no” to fewer elements, and the encoding was verified in a proof assistant. Burris and Yeats had conjectured that 12 is the least size; the History tells the rest of the story. ↩

  3. Every program in any programming language can be written as a combinator, and the Church–Turing thesis says that every procedure that could be called mechanical can be too. So “no program” means “no combinator” throughout this chapter, and each “no program” is a theorem about combinators. The thesis is used only where a program written in pseudocode is taken to be a combinator (Fact 8.24), and there it saves writing the combinator out. The impossibility results do not rest on it; it says only how far they reach. ↩

  4. This is the fact usually called the undecidability of the halting problem. Most accounts credit it to Turing’s paper of 1936, which did not state it. The History tells the story. ↩

  5. Textbooks call such a set computably enumerable, or semi-decidable. ↩

  6. Computation is also presented as a structure whose elements are the programs of a language and whose one operation runs one program on another, partial because a run may not end; with the programs taken to be numbers, it is known as Kleene’s first algebra. It has programs that behave as K and S, which is how the combinators name its elements. The chapter works with T, which speaks the language of Π. ↩

  7. Textbooks call such a set decidable, or recursive, and a theory with a decidable set of axioms axiomatizable. ↩

  8. The trick is due to Craig (1953). ↩

  9. A set that a program can list in this way is called recursively enumerable, or computably enumerable. ↩

  10. Turing completeness is stated for the functions that combinators compute. The form used here, for programs that may run for ever, is the one proved with it, and it is what the Church–Turing thesis says of the pseudocode of this chapter. ↩

  11. The structure is one of the family described in Subercaseaux and Przybocki (2026, §7), with particular values given to the cells that the template leaves as parameters; the script inc_wilkie.py in the course’s support folder checks the eleven identities in it and finds the one pair at which Wilkie’s identity fails. ↩

  12. Macintyre (1981); see Burris and Yeats (2004) for the history. ↩

  13. The fact is called the Σ1-completeness of arithmetic. It applies to HaltsA written with every universal quantifier bounded, as it can be: the optional Section 8.5 shows how, and the main line uses only that it can be done. The fact then holds even for the part of PA whose only induction axiom is the one for the formula x=0∨∃y(x=s(y)), which is needed to pass from φ(0―),…,φ(n―) to ∀i≤n―φ(i). With that sentence as an axiom in place of induction, the part is Robinson’s arithmetic, for which the fact is proved in Open Logic Project (2026, §35.11). ↩

  14. The trick is due to Rosser (1936); Gödel’s original theorem assumed a condition between consistency and soundness, called ω-consistency. ↩

  15. Parts (ii) and (iii) are this chapter’s forms of what are called the derivability conditions, and (iii) is known as the formalised Σ1-completeness of arithmetic. Open Logic Project (2026, §37.6) states them for a proof predicate written directly in arithmetic, and asks the reader to take them on faith; Hájek and Pudlák (1993, Chapter I) prove them in full. ↩

  16. The script ks_strings.py in the course’s support folder checks that Wf holds of exactly the strings of combinators, among all 349,524 strings of at most nine symbols; that the term stretches are exactly the strings of the parts, for all 550 combinators with at most five leaves; that the replacements of the table are exactly the steps, and a string with no redex stretch exactly a normal form, for all 3238 combinators with at most six leaves. ↩

  17. Presburger (1930). The procedure is expensive: every decision procedure for this structure takes, on some sentences of length n, a number of steps that grows like 22cn (Fischer and Rabin, 1974). ↩

  18. Tarski (1951); the result was obtained by 1930. ↩

  19. Skolem built the first such model in 1934. ↩

  20. Hilbert (1899), Hilbert (1900). ↩

  21. Hilbert (1930); the words are the epitaph on his grave in Göttingen. On the two days see Dawson Jr. (1997). ↩

  22. Gödel (1931). ↩

  23. Rosser (1936). ↩

  24. Gentzen (1936). ↩

  25. Church (1936b), Church (1936a). ↩

  26. Turing (1937a), Turing (1937b). ↩

  27. Hamkins and Nenu (2025); Kleene (1952), p. 382; Davis (1958), p. 70. ↩

  28. The note added in 1963 to the English translation of the 1931 paper, and the postscript of 1964 to his Princeton lectures of 1934; both are in Gödel (1986). ↩

  29. Presburger (1930), Tarski (1951), Fischer and Rabin (1974). ↩

  30. Matiyasevich (1970). ↩

  31. Doner and Tarski (1969). ↩

  32. Wilkie (2000). ↩

  33. Gurevič (1985), Gurevič (1990). ↩

  34. Burris and Yeats (2004), Zhang (2005). ↩

  35. Macintyre (1981). ↩

  36. Subercaseaux and Przybocki (2026). ↩

  37. Hajdari and Niederhauser (2026). ↩