## 117b – Undecidability and incompleteness – Lecture 11

February 27, 2007

Let $T\vdash 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 $T\vdash\mathsf{PA}$, there are recursive functions that are not provably recursive in $T$. The statement that $f$ is total,

$\forall x\,\exists y\,(f(x)=y)$,

is easily seen to be $\Pi^0_2$ and for $T=\mathsf{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 $\mathsf{PA}$, like $\mathsf{ZFC}$, and Harvey Friedman has provided several such examples.

For $\mathsf{PA}$, the most famous examples are perhaps the following:

• Goodstein (1944). The pure base-$n$ representation of a number $m$ is obtained by writing $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 $n\ge2$ let $G_n(0)=0$ and for $m\ge1$ 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 $\mathsf{PA}$. In fact, given any $f$ provably recursive in $\mathsf{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 $\mathsf{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|\ge\min(C)$. Ramsey’s theorem, provable in $\mathsf{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 $\mathsf{PA}$.