117b – Some additional remarks on provably recursive functions

February 28, 2007

There are quite a few examples of natural combinatorial statements not provable in $\mathsf{PA}$ other than the ones discussed in lecture. The references listed below present several of them and provide a guide to the 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. The list is far from exhaustive, however. There are many more recent results by Harvey Friedman, the literature on hydras goes much further than suggested (see here, for instance), and there is significant work on phase transitions not discussed in the papers I suggest.

There are at least two basic 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 $\mathsf{PA}$. 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:

• $F_0(n)=n+1$.
• $F_{\alpha+1}(n)=F_\alpha^n(n)$, where the superindex means iterated $n$ times.
• $F_\lambda(n)=F_{\lambda(n)}(n)$, if $\lambda$ is limit.

Here, $\{\lambda(n): n =0,1,\dots\}$ is some (natural) sequence converging to $\lambda$ (if you are not aware of ordinals, ignore for the moment what the last clause means).

For example, $F_1(n)=2n$, $F_2(n)=2^n n$, $F_3(n)$ grows like a stack of $n$ powers of $2$ and $F_4(n)$ grows like an iterated stack of powers of $2$, there being $n$ such iterations. It is easy to see that each $F_n$ is primitive recursive and strictly increasing, that $n$< $m$ implies that $F_n$ is eventually dominated by $F_m$ (i.e., that $F_n(k)$< $F_m(k)$ for all but finitely many values of $k$), and that every primitive recursive function is eventually dominated by some $F_n$. Thus, if a function eventually dominates each $F_n$, 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 $X$ is well-ordered iff 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 $n$ to denote the order type of any linearly ordered set of $n$ elements, and use $\omega$ to represent the order type of the natural numbers. We add’ two order types $\alpha$ and $\beta$ by forming the disjoint union of a set of order type $\alpha$ followed by a set of order type $\beta$. We also say that $\alpha$ is smaller than $\beta$ if any set of order type $\beta$ has a (proper) initial segment of order type $\alpha$. We can then continue the sequence $0,1,2,\dots$ of the natural numbers, as follows: $\omega,\omega+1,\omega+2,\dots,\omega 2,\omega 2+1,\dots,\omega 3,\dots,\omega^2,\dots,\omega^3,\dots$

where we use $\omega2$ to represent $\omega+\omega$, etc, $\omega^2$ to represent $\omega\omega$ and so on, and we can even continue  beyond all these ordinals: $\omega^\omega,\dots,\omega^{\omega^\omega},\dots\,$.

Call $\epsilon_0$ (epsilon-0) the first ordinal $\alpha$ obtained this way such that $\alpha=\omega^\alpha$ (so $\epsilon_0=\omega^{\omega^{\omega^{\dots}}}$).

One can show that any ordinal below $\epsilon_0$ admits a unique `pure base $\omega$‘ representation, from which there is a natural way of defining the sequence $\{\lambda(n):n=0,1,\dots\}$ converging to $\lambda$ whenever $\lambda$ is a limit, which means that it is not of the form $\alpha+1$ for any $\alpha$. For example, $\omega,\omega 3,\omega^{\omega^2 3+\omega 17+8} 5+\omega^3 2$, etc,

are all limits. So, for instance, the sequence $\{\lambda(n): n =0,1,\dots\}$ corresponding to $\lambda=\omega$ is just $\lambda(n)=n$ and the corresponding function $F_\omega$ is easily seen to grow as the (diagonal) Ackermann function $A(n,n)$; the sequence corresponding to $\lambda=\omega^3 4$ is $\lambda(n)=\omega^3 3+\omega^2 n$, etc. As before, each $F_\alpha$ is (eventually) strictly increasing and if $\alpha$< $\beta$ then $F_\beta$ eventually dominates $F_\alpha$. Each $F_\alpha$, for $\alpha$< $\epsilon_0$ (and in fact, for many more $\alpha$) is recursive (in the natural sense that there is a recursive well-ordering of $\omega$ of this order-type).

The relation of this sequence with $\mathsf{PA}$ lies in that any function provably recursive in $\mathsf{PA}$ is eventually dominated by one of the $F_\alpha$ with $\alpha$< $\epsilon_0$ (the proof of this fact is proof-theoretic rather than combinatorial, but once we have it we can use it as a black box). So, one purely combinatorial way of showing that a function is not provably recursive is to show that it eventually dominates each such $F_\alpha$. This kind of analysis was developed by Solovay and Ketonen.

There are also other ways of relating $\mathsf{PA}$ to this number $\epsilon_0$, and proof theorists have a lot more to say about this relation.