There 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 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 . 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 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 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 even continue beyond all these ordinals:
Call (epsilon-0) the first ordinal obtained this way such that
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,
are all limits. So, for instance, 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 (in the natural sense that there is a recursive well-ordering of of this order-type).
The relation of this sequence with lies in that any function provably recursive in is eventually dominated by one of the with < (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 . 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.
- Lecture notes on enormous integers, by H. Friedman. (2001)
- Unprovable theorems, by H. Friedman. (2005) See https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/ 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.