Will Sladek, a student at Caltech, wrote an excellent introductory paper on incompleteness in PA, The termite and the tower. While Will was working on his paper, I wrote a short note, Goodstein’s function, on how to compute Goodstein’s function. Please let me know of any comments of corrections to either article.

## Archive for the ‘Undecidability and incompleteness’ Category

### Goodstein sequences

July 27, 2007### 117b – Some additional remarks on provably recursive functions

February 28, 2007There are quite a few examples of natural combinatorial statements not provable in other than the ones discussed in lecture. The references listed below present several of them and provide a guide to the existent literature; I especially recommend the beautiful expository paper by Stephen Simpson and in general the whole collection where that paper appeared. I will ask you to abstain from looking at the Kanamori-McAloon paper for the time being, since its main result is the content of the last homework set.

There are at least two `combinatorial’ methods for showing that a function is not provably recursive. One is to use *indicators, *this technique, due to Paris, requires a bit of model theory, and is the method of the proof you are asked to provide in the homework.

The other method comes from a careful analysis of which functions are provably total in . For this, one defines a *fast-growing* hierarchy of recursive functions. This requires some understanding of the concept of an *ordinal*. The *fast-growing* (or *Grzegorczyk*) hierarchy is defined as follows:

- .
- , where the superindex means
*iterated times*. - , if is limit.

Here, is some (natural) sequence converging to (if you are not aware of ordinals, ignore for the moment what the last clause means).

For example, , , grows like a stack of powers of and grows like an iterated stack of powers of , there being such iterations. It is easy to see that each is primitive recursive and strictly increasing, that < implies that is eventually dominated by (i.e., that < for all but finitely many values of ), and that every primitive recursive function is eventually dominated by some . Thus, if a function eventually dominates each , it cannot be primitive recursive.

The ordinals provide us with a method for continuing this sequence while preserving that its members are (eventually) increasing and the sequence itself is increasing under eventual domination. Say that a linearly ordered set is* well-ordered* if it has no infinite descending chains. For our purposes, the ordinals are simply a way to talk about well-ordered sets (classically, ordinals denoted the *order types* of the well-ordered sets, i.e., the equivalence classes of these sets under the relation of being order-isomorphic. The modern viewpoint is different and we don’t need it here). We use to denote the order type of any linearly ordered set of elements, and use to represent the order type of the natural numbers. We `add’ two order types and by forming the disjoint union of a set of order type followed by a set of order type . We also say that is smaller than if any set of order type has a (proper) initial segment of order type . We can then continue the sequence of the natural numbers, as follows:

where we use to represent , etc, to represent and so on, and we can continue even beyond:

Call (epsilon-0) the first ordinal obtained this way such that

(so ).

One can show that any ordinal below admits a unique `pure base ‘ representation, from which there is a natural way of defining the sequence converging to whenever is a limit, which means that it is not of the form for any . For example,

, etc,

are all limits. So, for example, the sequence corresponding to is just and the corresponding function is easily seen to grow as the (diagonal) Ackermann function ; the sequence corresponding to is , etc. As before, each is (eventually) strictly increasing and if < then eventually dominates . Each , for < (and in fact, for many more ) is recursive.

The relation of this sequence with lies in that *any* function provably recursive in is eventually dominated by one of the with <. So, one purely combinatorial way of showing that a function is not provably recursive is to show that it eventually dominates each such . This kind of analysis was developed by Solovay and Ketonen.

There are also other ways of relating to this number , and *proof theorists *have a lot more to say about this relation.

Additional references:

*Lecture notes on enormous integers,*by H. Friedman*. (2001)**Unprovable theorems,*by H. Friedman*. (2005)*See www.math.ohio-state.edu/~friedman/manuscripts.html for additional manuscripts and details.*Unprovable theorems and fast-growing functions,*by S. Simpson. In**Logic and combinatorics**, S. Simpson, ed. AMS*(1987).**On Gödel incompleteness and finite combinatorics,*by A. Kanamori and K. McAloon*. Annals of Pure and Applied Logic***33***(1987),*23-41*.*

### 117b – Undecidability and incompleteness – Lecture 11

February 27, 2007Let be r.e. and suppose there is a sentence such that does not prove . Then is more powerful than in two ways:

- It proves
*more*theorems than ; for example, . - It provides
*much shorter*proofs of theorems of ; for example: For any (total) recursive function there is a sentence provable in but such that in there is a proof of such that no proof of in is shorter than .

This leads to considering those recursive functions of which can prove that they are total. One calls such functions *provably recursive* in . It is easy to show that for any -sound , there are recursive functions that are not provably recursive in . The statement that is total,

,

is easily seen to be and for one can provide natural examples of such recursive but not provably recursive functions , thus providing natural (combinatorial) examples of independent -sentences. Actually, this can also be done for much stronger systems than , like , and Harvey Friedman has provided several such examples.

For , the most famous examples are perhaps the following:

- Goodstein (1944). The
*pure base- representation of a number*is obtained by writting in base , writing the exponents of this representation also in base , writing the exponents of these representations in base , and so on. For let and for let be the result of writing the pure base- representation of , replacing each by , and subtracting . The*Goodstein sequence*of is the sequence This sequence eventually converges to*0*. The function that to assigns the number of steps necessary for this to occur is recursive but not provably recursive in . In fact, given any provably recursive in , eventually dominates . - Kirby, Paris (1982). Define a
*hydra*to be a finite rooted tree. A*head*of the hydra is any node (other than the head) with only one edge connected to it,*together*with this edge. Hercules fights the hydra by chopping off its heads one by one by stages. At stage , the hydra grows new heads as follows: from the node that used to be attached to the head just removed, traverse one edge towards the root and from this node just reached, sprout*copies*of the part of the hydra above the edge just traversed. For any hydra, no matter how Hercules battles it, he eventually wins (i.e., the hydra is reduced to a single node). Moreover, given a hydra there is an absolute bound on the number of stages that it takes Hercules to win. Coding (in any reasonable fashion) hydras by numbers, the function that assigns this number to a given hydra is recursive but eventually dominates all functions provably recursive in . - Paris, Harrington (1977). Given a set , let denote the collection of its subsets of size . Given a function , say that a subset of is homogeneous for iff restricted to is constant, and say that it is
*large*if . Ramsey’s theorem, provable in , states that for any there is an such that given any of size , any of size and any , there is a homogeneous for and of size at least . The function that to assigns the least such is well known to be primitive recursive (just about any standard proof of Ramsey theorem in any combinatorics book shows that it roughly grows exponentially). Paris and Harrington showed that if we also require that the homogeneous set be large, then the new statement is also true but the resulting function (clearly recursive) eventually dominates all functions provably recursive in .

### 117b – Undecidability and incompleteness – Lecture 10

February 22, 2007A theory *T* (r.e., extending *Q*) is *reflexive* iff it proves the consistency of all its finite subtheories. It is *essentially reflexive* iff each r.e. extension is reflexive.

Then *PA* is essentially reflexive and therefore no consistent extension of *PA* is finitely axiomatizable. This is obtained by showing that, in spite of Tarski’s undefinability of truth theorem, there are (provably in *PA*) *S ^{0}_{n}*–

*truth predicates*for all

*n*.

We define Rosser sentences and show their undecidability. We also show Löb’s theorem that if *T|-PA* is an r.e. theory and* T*|-Pr_{T}(j)®j, then *T*|- j. This gives another proof of the second incompleteness theorem.

Finally, we show that the length of proofs of P* ^{0}_{1}*-sentences is not bounded by any recursive function: For any

*T|-Q*r.e. and consistent, and any recursive function

*f*, there is a P

*-sentence j provable in*

^{0}_{1}*T*but such that any proof of j in

*T*has length >

*f(*j

*).*

### 117b – Undecidability and incompleteness – Lecture 9

February 20, 2007Let *S* and *T* be r.e. theories in the language of arithmetic. Assume that *S* is strong enough to binumerate all primitive recursive relations. This suffices to prove the *fixed point lemma*:

For any formula g(x) there is a sentence j such that *S* |- (j ↔g(j)),

moreover, j can be chosen of the same complexity as g.

The *(Löb)* *Derivability conditions* for *S,T* are the following three statements:

- For any j, if
*T*|-j, then*S*|- Pr_{T}(j). *S*|- For any j, y ( Pr_{T}(j®y) Ù Pr_{T}(j) ® Pr_{T}(y) ).*S*|-For any j ( Pr_{T}(j)®Pr_{T}(Pr_{T}(j)) ).

For example,* S=Q* suffices for the proof of the fixed point lemma and of the first derivability condition and *S=PA *suffices for the other two.

**Gödel incompleteness theorems: **

- Let
*S*be r.e. and strong enough to satisfy the fixed point lemma and the first derivability condition. Let*T*|-*S*be r.e. and consistent. Then there is a*true*P^{0}_{1}sentence j such that*T*does not prove j. If*T*is S^{0}_{1}-sound, then*T*does not prove ¬j either. - If in addition
*S*satisfies the other two derivability conditions, then*T*does not prove Con(*T*), the statement asserting the consistency of*T*.

As a corollary, *Q* is essentially undecidable: Not only it is undecidable, but any r.e. extension is undecidable as well. Gödel’s original statement replaced S^{0}_{1}-soundness with the stronger assumption of w–*consistency*.

### 117b – Undecidability and incompleteness – Lecture 8

February 15, 2007We introduce **Robinson’s arithmetic** *Q*. It is a weak (and *sound*) theory that proves all true S^{0}_{1} sentences. We also introduce **Peano Arithmetic** *PA*. *PA* is sound and designed to “capture” all true first order statements about **N**. (The incompleteness theorems will show that it does not suceed: There are true statements that *PA* does not prove.)

We show that *Q* represents all c.e. sets and binumerates all recursive sets, in particular all primitive recursive functions. *PA* actually proves that the representations of primitive recursive functions define functions, so in any (maybe non-standard) model of *PA* it makes sense to talk, for example, of the exponential function, or the function enumerating the primes.

We prove the *fixed point lemma* and deduce from it Tarski’s theorem on the *undefinability* of truth, thus formally solving the liar’s paradox.

### 117b – Undecidability and incompleteness – Lecture 7

February 13, 2007We define *essentially undecidable* theories as those theories (of arithmetic) that are recursively axiomatizable but such that *any* recursive extension *T* is undecidable and therefore incomplete. We show that if *S *is* essentially undecidable* then there are continuum many complete extensions of *S*, none of which are c.e. The argument gives an example of a complete binary tree recursive in *0*¢ with no c.e. branches.

We show that if j is S^{0}_{0} then its characteristic function is primitive recursive and that if R is a c.e. relation, then it is the range of a primitive recursive function. We use this to prove *Craig’s trick* showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We define *(numeralwise) representability* and *binumerability* of a relation by a formula in a given theory. Next lecture we will show that there is an essentially undecidable finitely axiomatizable theory that represents all c.e. relations and binumerates all recursive relations. This will be the key to the proof of the incompleteness theorems.

### 117b – Undecidability and incompleteness – Lecture 6

February 8, 2007We briefly discuss the problem of generalizing the proof of unsolvability of Hilbert’s tenth problem to other (recursive) rings.

We prove a version of the first incompleteness theorem as a consequence of the unsolvability of the tenth problem: If *S* is any recursive set of axioms strong enough to prove a very weak fragment of arithmetic (the addition and multiplication tables for **N **suffice) then either *S* is not true of **N**, or else *S* is incomplete. The reason is that if *S* is true of **N**, then the set of consequences of *S* is an undecidable r.e. set (by the unsolvability of the tenth problem), but the set of consequences of a complete theory is decidable.

Additional references:

*The incompleteness theorems*, by C. Smorynski. In**Handbook of mathematical logic**, J. Barwise, ed., North-Holland (1977), 821-865.**Models of Peano Arithmetic**, by R. Kaye. Claredon Press (1991).**Aspects of incompleteness**, by P. Lindström. Springer (1997).*On formally undecidable sentences of*(German:**Principia Mathematica**and related systems*Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.*), by K. Gödel. Monatshefte für Mathematik und Physik**38**(1931), 173-198. Reprinted in several places. See for example**Collected Works, vol. I,**K. Gödel. Oxford University Press (2001).

### 117b – Undecidability and incompleteness – Lecture 5

February 8, 2007We complete the proof of the undecidability of Hilbert’s tenth problem, and discuss some of its consequences, tying up with the general theory of the degrees and leading directly into the second part of this topic: The incompleteness theorems.

### 117b – Undecidability and Incompleteness – Lecture 4

February 1, 2007We show that *a=n!* is Diophantine*.* This implies that the prime numbers are Diophantine. Therefore, there is a polynomial in several variables with integer coefficients whose *range,* when intersected with the natural numbers, coincides with the set of primes. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.

We prove the *bounded quantifier lemma, *the last technical component of the proof. It implies that the class of relations definable by a S^{0}_{1} formula in the structure (**N**,+,´,<) coincides with the class of S_{1 }relations (i.e., the Diophantine ones).

To complete the proof of the undecidability of the tenth problem, we will show that any c.e. relation is Diophantine. For this, we recall that a set is c.e. iff it is the domain of a Turing machine and proceed to code the behavior of Turing machines by means of a Diophantic representation. This involves coding configurations of Turing machines and it remains to show how to code the way a configuration changes into another one.