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
With them you can prove , 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 , , , , 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 , , and :
It is true for every pair of positive whole numbers and . The reason is a hidden common factor: and , so that is times , and in the same way is times . Both sides are then the same product, written in a different order. But the factor 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 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 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 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
REFUTEcertifies 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 halts if for some 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 checks it. Let be the program that, given a combinator , asks whether given itself as input halts, and does the opposite: it loops for ever if says yes, and halts if says no. By Turing completeness is a combinator, and
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 as the string of , and brackets that spells it, that is, as a number, its code (Definition 8.23); and “ given itself” is applied to the numeral of its own code. With these readings the proof is exact: , written in pseudocode, is a combinator by Fact 8.24, and is asked about the combinator , 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
with and . We write as , as application is written, so that every combinator is a closed term; says that steps to , that is in normal form, and that 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,
the letters , and , 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 in Figure 8.1.
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 mentions .
Example 8.5 (a run, twice). The combinator steps to by a step in the function. By the rules of Chapter 1 the step is
and in , from the sentences and of , it is
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 is in normal form, and the rest of the derivation of goes the same way, one line for each rule used:
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 follows from exactly when halts, and questions about halting become questions about first-order consequence.
Lemma 8.6 (a program is a theory). For all combinators and :
if , then ;
if is in normal form, then ;
if halts, then ;
if , then halts.
So halts iff , iff .
Proof. Parts (i)–(iii) read the rules as sentences, as in the example.
(i). By induction on the rules that stack up to : each rule is an instance of one of , , , , reached by (E) and applied by (E).
(ii). By induction on : by the shape lemma, is , , , or with , in normal form, and – cover the five cases.
(iii). Take a run to a normal form. By (ii) and , ; by (i) and , gives , back to .
(iv). Let be the structure whose domain is the set of combinators, in which each closed term means itself, and , and are true of the steps, the normal forms and the combinators that halt. Every sentence of is true in : 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 , then , by the soundness of , and so halts.
The last sentence of the lemma is (iii) and (iv) together, with the soundness and completeness of . □
Theorem 8.7 (validity is undecidable). No program decides, for every sentence of , whether it is valid.
Proof. Write for the conjunction of the eleven sentences of . Given a combinator , a program can write down the sentence , and by Lemma 8.6
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 . 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:
given a finite set of sentences and a sentence , whether ;
given a finite set of sentences, whether it is satisfiable;
given a finite set of clauses, whether it is satisfiable.
Proof. Take and for (i). For (ii) and (iii), , a set of clauses once the quantifiers are dropped, is unsatisfiable exactly when 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 elements, for a given , 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
REFUTEdoes.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 , computation is the structure of the proof of Lemma 8.6: its domain is the set of combinators, each closed term means itself, and
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 , and the combinators express everything there is to compute.6
Does expressing everything mean that says everything? The theory proves only truths about , since is a model of it, and it proves for every combinator that halts. But it does not prove everything true there. The Monster of Chapter 1 has no normal form, and
since in the structure where every combinator halts the sentences of are true, and so is (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 proves every truth about , 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 . 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 ,
For every sentence , exactly one of and is in , since exactly when : 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 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 , then the sentences , with copies of , form a specification with the same theorems. Each is equivalent to , 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 if, for every -sentence ,
The definition has two halves, of very different weight.
Only truths: if then . When this half is free, by the soundness of .
Every truth: if then . 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 : it proves only truths about , but not . The set proves exactly the truths about , trivially, and would capture if it were a specification. The question is whether some specification captures .
Remark 8.14 (three senses of “complete”). The word “complete” has three uses nearby, and they are easy to confuse.
The completeness of 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 is true in every model of , the completeness of 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 .
Proof. A derivation of 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 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 , there is a program that, given a sentence , always halts and says correctly whether .
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 or , and proves every truth about , so one of the two is printed. Its answer is correct.
If is printed, then . Since captures , it proves only truths, so , and the answer is yes.
If is printed, then in the same way , 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:
That answers the question about computation.
Corollary 8.17 (computation cannot be captured). No specification captures the structure of computation. In particular, is not a specification.
Proof. For every combinator , exactly one of and is true in , according as halts or not. A program that decided the truths of would therefore check whether a given combinator halts, and there is none (Theorem 8.2). So by Theorem 8.16 no specification captures , and since proves exactly the truths about , it is not a specification. □
For we can watch the mechanism. The listing of its theorems prints for every combinator that halts, and never prints . A specification that captured would also print for every 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 is captured by some specification if and only if some program, given a sentence , always halts and says correctly whether .
Proof. One direction is Theorem 8.16. For the other, suppose a program decides the truths of . Then is a specification, and it captures .
Only truths. Whatever it proves is true, by the soundness of , since .
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 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 and so, because captures , is entailed by .
So one of the two runs stops, and which one says whether .
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 nested quantifiers on elements takes about 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 a new name , and write down
distinctness: for each pair of different elements and ;
closure: , where are all the elements;
the tables: whenever sends to , and or its negation, for each relation symbol other than and each tuple.
These sentences, the description of the structure , together with the equality axioms, capture 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 , and proves for every that halts; but it does not prove for every that does not.
Proving everything, with some theory. The set of all truths proves exactly the truths about any structure , trivially. It captures 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
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 .
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,
with and arity for the others. The standard model of arithmetic , as the structure is traditionally called, has the domain , and interprets
as zero and as the successor, ;
and as addition and multiplication;
as less than and as identity.
The language has no symbol for , or for . 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 .
Formally, for each number the numeral is the closed term of defined by recursion on :
So is , and in general has copies of . Its value in is , by induction on .
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 for , “ divides ”, and
With these abbreviations, the sentence says that there are infinitely many primes, which is true. The sentence
is Goldbach’s conjecture. A specification that captured 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 , , and , once every application is bracketed; a string of four symbols is a sequence of the digits to ; 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 of a combinator is the number whose digits in base are the symbols of written with every application bracketed, read with for , for , for and for .
Here are three combinators and their codes.
| Combinator | String | Digits | Code |
|---|---|---|---|
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 is Chapter 1’s numeral of , written here with a bar beneath, , since the bar above is taken by the numerals of arithmetic. A combinator halts on if halts, and for numbers and we say that program halts on if is the code of a combinator that halts on .
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 such that, for every number , halts on exactly when the pseudocode halts on .10
We call 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 of -tuples of numbers is definable in if there is a formula of whose free variables are among such that, for all numbers ,
The even numbers are definable, by , and so are the primes and the pairs with .
Definability is a matter of truth in , 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 to , for instance, the strings are
where the stretch , with and , has been replaced by . So “ steps to ” says something about the digits of and 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 “ is the remainder of on division by ” is the formula
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 and , with the entry at position , counting from , the remainder of on division by . Then “there is a run that ends” is “there are numbers and 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 is packed by and , with the divisors , and :
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 , , , and of such that, for every number and all combinators and :
iff is the code of a combinator;
iff ;
iff ;
iff is in normal form;
iff 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 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 and by application, and of the relations , and ; 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 of and each variable not in , the formula , “ is the code of ”, is given by
with and new variables. The translation of a formula of is given by
The quantifiers are cut down to the codes of combinators, and everything else is said of codes. For instance, is true in of alone, so says that is true of ; and since is , the translation of is .
Lemma 8.29 (arithmetic contains computation). For every sentence of ,
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 in , which gives each variable a combinator, let give each variable the code of that combinator. We show that exactly when .
Terms. For each term , the formula is true in , under , of exactly one number, the code of the value of under . This is by induction on , 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 is true are exactly the codes of combinators, so “for every number that is a code” in is “for every combinator” in , 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 : 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 , whether .
Proof. A program that decided truth in would decide truth in : given , it would compute and decide that (Lemma 8.29). In particular, given a combinator , it would decide , that is, whether halts, and no program does (Theorem 8.2). □
Corollary 8.31 (nothing captures arithmetic). No specification captures . In particular, for every specification with , there is a sentence with and .
Proof. A specification that captured would make the truths of decidable, by Theorem 8.16, and no program decides them, by Theorem 8.30. If , then proves only truths, by the soundness of ; since it does not capture , it must miss a truth. □
So , 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, , 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 is sound if implies , for every sentence .
Here the word names a property of a specification, not to be confused with the soundness of , a property of the proof system: whatever derives from true premisses is true. The two are connected: by the soundness of , a specification is sound exactly when . A sound specification has the “only truths” half of capturing (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 . The diagonal program 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 for its code, and , or , for the sentence .
On the input , the program waits for to prove that program does not halt on , and halts if that ever happens. The interesting input is the program’s own code, and the sentence says, in arithmetic, that run on its own code does not halt.
Theorem 8.34 (the first incompleteness theorem). If is a sound specification in , then
Proof. Write for the diagonal program of and for its code, and run on :
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 was for .
Figure 8.2 draws the theorem. Among the sentences of , 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.
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 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 halts. Read in , the sentence says that 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 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 did this to a predictor of halting, and the program 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 and two-place function symbols , and , where is ; let be the positive integers with their usual operations; and let be the equality axioms together with the eleven identities on the board, each with in front of its variables. Then is a specification, and , so it proves only truths. It does not prove every truth: Wilkie’s identity, with in front, is true in and not provable from . The certificate is a structure of twelve elements, with tables for , , 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 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 , its true identities, which no finite list does. It does not capture , since capturing (Definition 8.13) asks about every sentence, with its connectives and quantifiers.
Nothing captures in that sense. Let each positive integer stand for the counting number . Then , , and can be defined from , and ; for instance, the counting numbers for which are those for which holds in . So a program that decided the truths of would decide those of , and none does (Theorem 8.30). By Theorem 8.16, no specification captures . 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 , 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 , 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 proves: every true sentence about halting. Then we carry the proof of the first theorem out inside . That step rests on three facts about what 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, , is the set of sentences of consisting of the equality axioms and the following sentences, each with in front of its free variables:
and ;
and ;
and ;
;
for every formula with a free variable , the induction axiom .
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 is a specification. Since , 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, 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 . In words: the theory never leads to a contradiction. Equivalently, there is no sentence with both and , 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 . The converse fails (Remark 8.49).
To trade soundness for consistency, we need one fact about what can prove: that it can check a finished calculation.
Fact 8.39 (true halting is provable). For every combinator : if halts, then .
The reason is that a halting run is a finite calculation. If halts, there are particular numbers , and that pack its run, and 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 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 . The specification 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): , like , proves every true fact about halting. What neither proves is every true fact about not halting.13
So every specification that contains proves for every combinator 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 that proves for every combinator that halts. Then
Proof. Write for the diagonal program of and for its code. As in the proof of the first incompleteness theorem (Theorem 8.34),
We show first that does not prove the sentence, and then that it is true.
does not prove . Suppose it did. Then halts, so proves , by the hypothesis. The sentence is the negation of that one, so proves a sentence and its negation, and therefore , which contradicts its consistency.
The sentence is true. By the first step and the display, does not halt, so , and 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 , 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 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 , let 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 be the combinator that runs it on . The consistency sentence of is
The program ignores its input, so
The sentence thus says “ is consistent” in the language of arithmetic. Like 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 itself, and not of any combinator that halts on the same inputs. When is consistent, halts on no input, like every combinator that never halts. For some of those, such as the translation of “loop for ever”, proves that they never halt, and with such a combinator in place of 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 . 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 , 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 , let be a sentence of , and let 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
In words, says “ proves ”: by Lemmas 8.15 and 8.29, exactly when . The program of the consistency sentence is , and the translation of a negation is the negation of the translation, so is .
The sentence also says “ proves ”, through the diagonal program. Write for it, so that is . Three facts about these sentences carry the proof of the first theorem into . Each is a true sentence, and each says something that proof used; what is needed is that proves it.
Fact 8.45 (what arithmetic proves about provability). Let be a specification in with . Then proves each of the following.
The diagonal program does what it says: .
The theorems are closed under (E): , for every sentence .
True halting is provably provable: , for every combinator .
Each part is true for a reason that can follow, and the work is in checking that it can. In each the reasoning is an induction inside , on a number about which 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 do work that the fact that true halting is provable (Fact 8.39) does not need.15
(i). The formula follows the leftmost run, and proves that this run is unique: two tables with the same first row agree row by row, by induction on the row number. So speaks of one definite run of on its own code, and of one definite run of on . Each run carries out the search of
LIST, one string at a time, and stops at the first theorem that equals , which for 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, proves that each halts exactly when some string is a derivation of from . So the two halt together.(ii). If
LISTprints and , it has met derivations of both. The tree that joins them by (E) is a derivation of with its open hypotheses in , andLISTmeets 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 .(iii). The reason for the fact that true halting is provable (Fact 8.39) is a recipe: from numbers that pack a run of , it writes down a derivation of from , one calculation for each row. The recipe is a program, and part (iii) says that 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 is used: the derivations that the recipe writes have their open hypotheses in , so they are derivations from .
With the three facts, the proof of the first theorem from consistency can be carried out inside .
Lemma 8.46 (arithmetic knows the first theorem). If is a specification in with , then
Proof. From and the hypothesis , the parts of Fact 8.45 give, in turn,
These are the three moves of the first step of the proof of the theorem from consistency, said in arithmetic: halts, so proves ; it then also proves that halts; and a sentence with its negation gives . The sentence is , so (E) derives from , and . Discharging by (I) gives , which is , and discharging gives . □
Theorem 8.47 (the second incompleteness theorem). If is a consistent specification in with , then .
Proof. Suppose . Since , the lemma that arithmetic knows the first theorem (Lemma 8.46) gives , and (E) gives . Since contains , it proves for every combinator that halts (Fact 8.39), so this contradicts the first incompleteness theorem from consistency (Theorem 8.40). So does not prove . □
In words: a consistent specification of arithmetic cannot prove its own consistency. By the completeness of , it follows that : some model of makes false. So this is a limit on what a specification entails, and not only on how well it fits . Unlike the theorem from consistency, it needs in earnest, and not only the true sentences about halting: the argument runs inside , 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 , and the finitary reasoning the programme had in mind is usually taken to be far weaker. Even 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 can be proved by an induction that cannot carry out (the History tells the story), and whether that induction is finitary is a matter of judgement, not of proof. Nor does settle the question. It satisfies , so 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 is consistent, since it is sound. So, by the theorem, does not prove . It follows that together with is consistent. A derivation of from it would give, by (I), a derivation of from , and then, since is classical, one of , which the theorem rules out.
But with added is not sound, since says that 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 that is true of the code of a combinator exactly when halts. By definition, halts when it runs to a normal form, and runs to a combinator when a finite chain of steps leads from one to the other. So has to say: there are and combinators with , with for each , and with in normal form. In symbols, pretending for a moment that we may quantify over combinators, and over lists of them of any length,
Four things in this line are not yet arithmetic, and the section deals with them in turn.
The list has a length that is not fixed in advance, and a formula has only a fixed number of quantifiers.
Each is a combinator, not a number.
is a step, a relation between combinators.
and “ 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 for the remainder of on division by , for . The packing uses the function
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
are positive integers, no two of which have a common factor greater than , and
are numbers with for each .
Then there is a number with for every .
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 and they cannot: no number leaves remainder on division by and on division by .)
Proof. The idea is to count: there are exactly as many numbers below the product of the as there are lists of remainders. Let , and send each number to its list of remainders . Two different numbers have different lists. For if the lists were equal, every would divide . Then their product would divide too. To see this, write as a product of powers of different primes. Take one of them, . The prime divides some , since a prime that divides a product divides one of its factors. It divides no other , so all factors of come from that one . So divides , and therefore divides . A number divisible by the powers of different primes is divisible by their product, by the uniqueness of factorisation into primes, so divides . But , so cannot divide . So the map is one-to-one. There are numbers below , and possible lists of remainders, so every list is the list of some , and in particular the list . □
Lemma 8.51 (packing a sequence). For every finite sequence of numbers there are numbers and such that for every .
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 be the largest of , let , and let for . We check the two hypotheses of the Chinese remainder theorem.
. We have , since for every number (for because ).
No two of the have a common factor. Suppose a prime divides and with . Then divides their difference . It does not divide : if it did, it would divide , which is a multiple of . It would also divide , and so their difference . So divides . But , so divides , and then divides after all, which is a contradiction.
The Chinese remainder theorem now gives with , which says . □
Example 8.52 (packing ). For the sequence the proof takes , and the divisors , , ; the Chinese remainder theorem gives , and indeed . The proof’s is generous: the smallest pair that packs the sequence is , .
The function is definable: exactly when makes true
since is .
When appears inside a formula as if it were a term, as in , the formula abbreviates one that says “there is a with and ”. Since is a function, nothing is lost.
We write for , for , and and in the same way; and for . In a sum such as , the number stands for its numeral .
The abbreviations for bring in quantifiers. Every one of them, wherever it stands, can be bounded by , since a quotient or a remainder of is at most . 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, 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, is defined by recursion on the shape of :
Let be a run. Row of its table is , written in the digits used for codes: for , for , for and for . The rows have different lengths, so the table is described by packed sequences of three kinds:
for the length of row , the digit at position of row , and the bracket count of row before position , where is a number at least as large as every length. The bracket count is the number of opening brackets among the first digits, less the number of closing ones.
The clause says that the numbers mean what was just said. It is the conjunction, for all , of:
;
for every , the digit is one of , , , ;
;
for every , the count goes up by one at a digit , down by one at a digit (written ), and stays the same at the others.
(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 is the part from a position up to, but not including, a position . 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 or , 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 :
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:
where is : after the bracket at come two term stretches, from to and from to , 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:
| Redex | Row | Row |
|---|---|---|
Here , and are term stretches, and and are the rest of the row, unchanged. Figure 8.3 shows one step written this way, from to , with , , and . The new row is made of three copies from the old one, and nothing else.
Write , , and so on for the lengths of these pieces, and for the position where the redex starts, which is . A redex at is then described by
A copy of a stretch is described by
which says that the digits of row from are those of row from . A step from row to row is
The three copies are , and , each put in its place in the new row. The formulas and are written in the same way from the line of the table above, with seven fixed digits in row , six in row , six copies (, , , twice and ), and the bound . This bound, like the last line of the formula, keeps every position inside the row, where the digits are fixed by . We do not write the formulas out here; Exercise 8.15 writes the first and lays out the second.
Let be . A redex starts at position of row when
and row has no redex when
A combinator can have many runs, since a step may rewrite any of its redexes, and 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 is a step whose redex starts at a position before which no redex starts. Let be with the clause
added next to , let be obtained from in the same way, and let 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 .
Lemma 8.54 (a step is the replacement of a stretch). For all combinators and :
exactly when is obtained from by one of the two replacements of the table, with , and term stretches;
is in normal form exactly when has no stretch of either form in the column “Row ” of the table, with , and 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 are exactly the strings of the parts of . Two facts about the bracket count are needed, both proved by induction on a combinator .
Along the count never falls below its value at the start of .
At the end of the count is back to that value, and, when is an application, it is not back to it any earlier.
The claim is proved by induction on . If is or , its string has one symbol and has one part. If is , its parts are itself and the parts of and of , and is an opening bracket, , and a closing bracket. The whole string is the string of , and it is a term stretch by the second fact. By the induction hypothesis, the term stretches that lie inside or inside are the strings of the parts of and . There are no other term stretches.
One that begins at the first bracket of ends where the count first comes back to its value at the start, which by the second fact is the end of . So it is the whole string.
One that begins with a bracket inside ends inside . Let be the count just before that bracket. By the first fact, is at least the count at the start of . After the bracket the count is , and at the end of it is back to . Since it moves by one at a time, it comes back to by then.
One that begins with a bracket inside ends inside , in the same way.
A term stretch that is a single or lies inside or , so the list is complete.
It follows that a stretch of either form in the column “Row ”, with , and term stretches, is exactly the string of a part of that is a redex. The two claims of the lemma follow.
(i). A step rewrites one part of that is a redex, by () or (). The rules () and () 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 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, 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 ; the first must be the string of the combinator with code . The digits of row are read off by a fourth packed sequence: is the number that the first digits of row spell in base . Let be the conjunction of
, which says that row is the string of a combinator;
, , and for every , which say that its digits spell .
Putting it together
Let be
The formula says that there is a table of rows whose first row is the combinator with code , 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 and became : the length of the run and the numbers that pack its table;
each is a combinator became , with ;
became ;
for each became , with the step chosen as the leftmost one;
is in normal form became .
The other formulas of the lemma come from the same pieces. The formula says that there is a table of one row with and ; the formula adds ; and asks for a table of two rows, the first spelling , the second spelling , with . For , the string of is an opening bracket, the string of , the string of and a closing bracket, so
where and are the numbers of digits of and ; the powers of form a sequence , which is packed and unpacked like any other.
Proof of part (v) of the lemma that computation is definable. Let be a combinator and its code; parts (i)–(iv) are proved in the same way, from the same pieces.
If halts, the formula is true of . Take the leftmost run of . Since has a normal form, the normalisation theorem for combinators says that this run reaches one, say . Let be the largest of the lengths of the strings , and pack the lengths, the digits, the bracket counts and the values of the first digits of row by the packing lemma (Lemma 8.51), in the orders stated. The resulting numbers make every clause true:
, by the choice of the sequences;
, since row is the string of ;
each , and , by the lemma that a step is the replacement of a stretch (Lemma 8.54): the stretch replaced in row is the string of the redex that the leftmost run rewrites, and no redex starts before it.
If the formula is true of , then halts. Take numbers that make the clauses true for . By and , row is the string of a combinator whose digits spell , so it is . By induction on , row is the string of a combinator with : for the step from to , the clause says, among other things, that row is row with a stretch replaced as in the table. The stretch replaced is the string of a part of , and it is replaced by the string of a combinator, so row is the string of a combinator . By the lemma that a step is the replacement of a stretch, . By and the same lemma, is in normal form. So 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 .
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
, where 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 (for dense linear order) consists of the equality axioms for the signature and the following sentences.
Irreflexive: .
Transitive: .
Linear: .
Dense: .
No end points: and .
The rationals make every one of these sentences true.
Theorem 8.57 (a dense order is captured). The specification admits quantifier elimination, and it captures .
In words: six sentences and the equality axioms say everything true about the order of the rationals.
Proof. By the completeness of it is enough to work in an arbitrary structure that satisfies , so the equivalences below are claims about every such structure. We eliminate quantifiers by induction on . The connectives are immediate, is , and the only case with content is with already free of quantifiers. The case is settled in four moves.
Write in disjunctive normal form and move inside the disjunction, so that it remains to treat with literals .
Remove negations: is equivalent to , and to , by the order axioms; distribute again. Conjuncts that do not mention move outside the quantifier.
If is a conjunct, the conjunction is false. A conjunct can be dropped. If or is a conjunct for a variable other than , then is equivalent to .
What remains is , and it is equivalent to the conjunction of all . In one direction this is transitivity. In the other, take the largest and the smallest , which exist since the order is linear. By hypothesis the first is below the second, and density gives an between them. If there are no , or no , the absence of a least or greatest element gives , 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 proves or proves . As satisfies , the specification proves only truths about , by soundness. So a true sentence is proved, since otherwise would be proved and true. Hence captures . □
The proof is an algorithm: each move rewrites a formula, and the rewriting ends. So it decides the truths of directly, without the listing of theorems.
Quantifier elimination reaches further than orders.
Remark 8.58 (addition without multiplication). The counting numbers with , , and but without can also be captured, by the axioms of 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 and , a symbol for “ leaves remainder on division by ”, 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 , , , 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 some model of makes it false. In it is true, so is not , nor a copy of it: it satisfies every sentence of and still disagrees with about whether halts on its own code. Both are models of , since is sound, and a model of that is not a copy of is called a non-standard model of . This one is not a model of , since it makes the true sentence false.
The disagreement has to live somewhere. In the sentence is true, and it claims that a halting run exists. When contains one can show, though we do not here, that the numerals of 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 it is an infinitely long “run” that no machine performs.
Non-standard models are not only the price of incompleteness. Even , which leaves no truth unproved, has them. Add a new constant and, for every , the sentence . Every finite part of this set has a model, namely with read as a large enough number, so by compactness the whole set has one, and in it names an element beyond every numeral. Forget , and the result satisfies every sentence true in without being a copy of : a non-standard model of itself. No set of first-order sentences pins the counting numbers down.19
Figure 8.4 summarises the chapter’s answers.
| Structure or question | Captured? | Truths decidable? |
|---|---|---|
| a finite structure | yes, by its table | yes, by evaluation |
| propositional validity | (no structure) | yes, by DPLL |
| yes, by | yes, by quantifier elimination | |
| yes | yes, at great cost | |
| yes | yes, at great cost | |
| no | no | |
| first-order validity | (no structure) | no; listable by REFUTE |
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 “ is the number of a derivation of the sentence with number ” 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 consistent by an induction longer than any that 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 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 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.
| Who | The list | Each applied to itself | The twist | What follows |
|---|---|---|---|---|
| Cantor, 1891 | infinite sequences of s and s | the th digit of the th sequence | change it | the list misses a sequence |
| Russell, 1901 | all sets | is the set a member of itself? | take those that are not | the sets not members of themselves form no set |
| halting | all programs | does the program halt on its own code? | do the opposite | no program decides halting |
| the program | the theorems of | does say program does not halt on ? | halt exactly then | misses a truth |
| Who | When | What |
|---|---|---|
| Dedekind | 1888 | the eleven identities |
| Hilbert | 1899; 1900 | axioms for geometry; the consistency of arithmetic asked for |
| Presburger | 1929 | addition alone is decidable |
| Tarski | by 1930; 1948 | the real numbers are decidable |
| Gödel | 1930; 1931 | the incompleteness theorems |
| Church | 1936 | having a normal form is undecidable |
| Church; Turing | 1936 | first-order validity is undecidable |
| Rosser | 1936 | a sentence neither proved nor refuted, from consistency alone |
| Gentzen | 1936 | the consistency of , from outside it |
| Kleene; Davis | 1952; 1958 | the halting argument; the name |
| Matiyasevich | 1970 | polynomial equations are undecidable |
| Wilkie | 1981 | a true identity the eleven do not derive |
| Gurevič | 1985; 1990 | a counter-model; no finite list suffices |
| Subercaseaux, Przybocki | 2026 | the least counter-model has twelve elements; all of them classified |
| Hajdari, Niederhauser | 2026 | no eleven-element counter-model, by a second encoding |
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 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 , that is, , 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 be a set of combinators that contains and and contains , and whenever it contains and . Show that 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 interprets by it.
Exercise 8.3. Let be the structure whose domain is the set of combinators, with , and application as in the structure of the proof of Lemma 8.6, in which , and are true of everything. Show that satisfies and makes 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 , and not just any model of ?
Exercise 8.4. Compute the code of . Which numbers below 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 . (Find a reduction: from and , compute the code of a program that ignores its input and does what program does on .)
Exercise 8.6. Say which of the following sets of sentences are specifications, with a reason for each.
The eleven identities of Remark 8.37, each with in front of its variables.
The induction axioms of .
The set of all sentences true in a structure with five elements.
The set of all sentences of true in .
The set of sentences of with fewer than a hundred symbols that are true in .
Exercise 8.7. Let , , , and .
Show that and .
Deduce that for all positive integers and .
Check that for every positive integer , 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 be a structure whose truths are decided by a program. Prove in full that is a specification and that it captures . Which half of capturing uses the soundness of ?
Exercise 8.9. The structure has the domain , and its signature has three symbols.
A one-place function symbol , with , and .
A one-place relation symbol , true of alone.
The relation symbol , interpreted as identity.
Exercise 8.10. Take the equality axioms and the description of Exercise 8.9, and remove the closure sentence. Find a model of what is left in which the sentence is false, although it is true in . What does the example show about the closure sentence?
Exercise 8.11. Write in , using and as abbreviations and with every quantifier’s scope bracketed:
there are infinitely many pairs of primes that differ by ;
every number is the sum of four squares;
every number greater than is divisible by a prime.
Exercise 8.12. Let be a specification in and the sentence of its diagonal program.
Which step of the proof of the first incompleteness theorem fails if is not assumed sound?
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 from a set 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 and with equal to , , for , 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 that Section 8.5 leaves to the reader, in the style of . Then say where, in row of an step, the six fixed digits stand, and where each of the six copies begins.
Exercise 8.16. (Optional.) Eliminate the quantifier from in , 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
The story of this introduction, as far as Hilbert, is adapted from Gheorghiu (2025). ↩
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 is the least size; the History tells the rest of the story. ↩
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. ↩
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. ↩
Textbooks call such a set computably enumerable, or semi-decidable. ↩
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 and , which is how the combinators name its elements. The chapter works with , which speaks the language of . ↩
Textbooks call such a set decidable, or recursive, and a theory with a decidable set of axioms axiomatizable. ↩
The trick is due to Craig (1953). ↩
A set that a program can list in this way is called recursively enumerable, or computably enumerable. ↩
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. ↩
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.pyin the course’s support folder checks the eleven identities in it and finds the one pair at which Wilkie’s identity fails. ↩Macintyre (1981); see Burris and Yeats (2004) for the history. ↩
The fact is called the -completeness of arithmetic. It applies to 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 whose only induction axiom is the one for the formula , which is needed to pass from to . 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). ↩
The trick is due to Rosser (1936); Gödel’s original theorem assumed a condition between consistency and soundness, called -consistency. ↩
Parts (ii) and (iii) are this chapter’s forms of what are called the derivability conditions, and (iii) is known as the formalised -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. ↩
The script
ks_strings.pyin the course’s support folder checks that holds of exactly the strings of combinators, among all strings of at most nine symbols; that the term stretches are exactly the strings of the parts, for all 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 combinators with at most six leaves. ↩Presburger (1930). The procedure is expensive: every decision procedure for this structure takes, on some sentences of length , a number of steps that grows like (Fischer and Rabin, 1974). ↩
Tarski (1951); the result was obtained by 1930. ↩
Skolem built the first such model in 1934. ↩
Hilbert (1930); the words are the epitaph on his grave in Göttingen. On the two days see Dawson Jr. (1997). ↩
Hamkins and Nenu (2025); Kleene (1952), p. 382; Davis (1958), p. 70. ↩
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). ↩
Presburger (1930), Tarski (1951), Fischer and Rabin (1974). ↩