117b – Undecidability and incompleteness – Lecture 11

Let Tvdash Q be r.e. and suppose there is a sentence varphi such that T does not prove varphi. Then T+varphi is more powerful than T in two ways:  

  1. It proves more theorems than T; for example,  varphi.
  2. It provides much shorter proofs of theorems of T; for example: For any (total) recursive function f there is a sentence theta provable in T but such that in T+varphi there is a proof p of theta such that no proof of theta in T is shorter than f(p).

This leads to considering those recursive functions f of which T can prove that they are total. One calls such functions provably recursive in T. It is easy to show that for any Sigma^0_1-sound Tvdashmbox{sf PA}, there are recursive functions that are not provably recursive in T. The statement that f is total,

forall xexists y,f(x)=y,

is easily seen to be Pi^0_2 and for T=mbox{sf PA} one can provide natural examples of such recursive but not provably recursive functions f, thus providing natural (combinatorial) examples of independent Pi^0_2-sentences. Actually, this can also be done for much stronger systems than mbox{sf PA}, like mbox{sf ZFC}, and Harvey Friedman has provided several such examples.

For mbox{sf PA}, the most famous examples are perhaps the following:

  • Goodstein (1944). The pure base-n representation of a number m is obtained by writting m in base n, writing the exponents of this representation also in base n, writing the exponents of these representations in base n, and so on. For nge2 let G_n(0)=0 and for mge1 let G_n(m) be the result of writing the pure base-n representation of m, replacing each n by n+1, and subtracting 1. The Goodstein sequence of m is the sequence m, G_2(m), G_3(G_2(m)), G_4(G_3(G_2(m))),dots This sequence eventually converges to 0. The function F that to m assigns the number of steps necessary for this to occur is recursive but not provably recursive in mbox{sf PA}. In fact, given any f provably recursive in mbox{sf PA}, F eventually dominates f.
  • 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 n, 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 n 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 M 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 M=F(n) to a given hydra n is recursive but eventually dominates all functions provably recursive in mbox{sf PA}.
  • Paris, Harrington (1977). Given a set A, let A^{[n]} denote the collection of its subsets of size n. Given a function f:A^{[n]}to B, say that a subset C of A is homogeneous for f iff f restricted to C^{[n]} is constant, and say that it is large if |C|gemin(C). Ramsey’s theorem, provable in mbox{sf PA}, states that for any c,n,b there is an M such that given any A of size M, any B of size b and any f:A^{[n]}to B, there is a C homogeneous for f and of size at least c. The function that to c,n,b assigns the least such M 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 C be large, then the new statement is also true but the resulting function (clearly recursive) eventually dominates all functions provably recursive in mbox{sf PA}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: