[FOM] PA Incompleteness

[Harvey Friedman]

PA incompleteness is now a reasonably well defined and reasonably well
developed area within mathematical logic. After the initial results (see
below), the focus, for many years, has been on the integration of such
exotic combinatorics into normal professional mathematical activity, with
its normal motivation and normal culture.

It is by no means yet clear just to what extent this can be done. A way of
testing progress is to gauge the interest of normal mathematicians in the
independent statements.

The expression of keen interest in the independent statements by normal
mathematicians, is by no means a sufficient condition for the kind of
integration that is ideal. However, it appears to be a necessary condition -
a condition that is not easily met.

Why should we care about "normal" mathematicians? Mathematics is a subject
with some sort of systematic motivation and modus operandi - although it is
far less clear what this is than it ought to be, as mathematicians do not
seem to want to write or lecture directly about it in any serious way.

So a very legitimate question is whether incompleteness is actually
something that occurs along the path of mathematics according to such
systematic motivations and modus operandi.

Actually, I have no doubt that it does, but demonstrating this in a totally
convincing way is an important and fair challenge. It is a challenge that is
first to be met by at least demonstrating that it does in a moderately
convincing way.

I hope that this illustrates the point behind my use of various evaluative
adjectives used below, such as "recreational".

**************************************

PA Incompleteness started with Goodstein sequences, which has a
"specialized recreational" flavor. It was followed by something more
"serious", by Leo Harrington and Jeff Paris: the finite Ramsey theorem with
"relatively large".

R. L. Goodstein. On the restricted ordinal theorem, The Journal of Symbolic
Logic 9 (2) (Jun., 1944), 33­41.

J. Paris and L. Harrington. A mathematical incompleteness in Peano
arithmetic, in J. Barwise, editor, Handbook of Mathematical Logic.
North-Holland, 1977.

There are other related "recreational" PA incompleteness; most well known is
Hercules and the Hydra. This is less "recreational" and more "mathematical"
than Goodstein sequences:

L. Kirby and J. Paris, Accessible independence results for Peano arithmetic,
Bulletin of the London math. Soc. 14, 1982, pp. 285-293.

In relatively large, an integer is used both as an element of a finite set
and as a cardinality (of that same set).

This is sufficiently unlike standard mathematics, that an effort began, at
least implicitly, to find PA incompleteness that did not employ this
feature, or this kind of feature.

Kanamori and MacAloon published a PA Incompleteness that is essentially
present in Harrington's publication of the Ramsey work:

Akihiro Kanamori and Kenneth McAloon. On Goedel incompleteness and finite
combinatorics.Ann. Pure Appl. Logic, 33(1):23-41, 1987.

I had also been thinking about this for some time, and later published my
own PA Incompleteness in section 1 of

H. Friedman, Finite Functions and the Necessary Use of Large Cardinals,
Annals of Math., Vol. 148, No. 3, 1998, pp. 803-893.

It involves k tuples of integers, rather than k element sets of integers -
this is definitely more "normal":

Theorem 0.3. Let n >> k,r,p > 0 and F: [n]^k into [n]^r obey the inequality
|F(x)| <= min(x). Then there exists E in S_p[n] such that
|F[E^k]| <= (k^k)p.

Theorem 0.4. Let n>> k,r,p > 0 and F: [n]^k into [n]^r. Then F has
<= (k^k)p regressive values on some E^k containedin [n]^k, |E| = p.

Here [n] = {0,...,n}. S_p[X] is the set of all p element subsets of X.

I also found a number of more "local" PA Incompleteness in the sense that
the conclusions don't involve the action of a function on a Cartesian power,
but instead only the action of a function at a few tuples.

I will wait for feedback on this topic before continuing.

Harvey Friedman