FOM: background on incompleteness I

[Harvey Friedman]

In light of the numerous postings on the FOM that, at least tangentially,
regard the incompleteness program I have been working on for thirty years,
I thought it would be best to make a careful statement about the background
and current status of this program. This will be done in a series of
postings.

The way that I present this material is somewhat colored by the persistent
objection made on FOM that certain concepts and distinctions are not
"formalized." This view is of course crippling for the appropriate
development of f.o.m. Some have urged me to avoid wasting time by ignoring
this view; but I have chosen to take it half seriously, as you can see.

Let me first summarize my major points about this program:

1. The program is an entirely inevitable outgrowth of work of Godel, and
secondly Cohen.
2. Godel in his writings, and Cohen in oral communication expressed clear
interest in the program.
3. The long term status of set theory rests on progress in this program.
4. Progress has been far more incremental than the early work of Godel and
Cohen.
5. Progress will continue to be incremental.
6. Progress is already more than sufficient to expect continuing long term
success of the program.
7. Progress is sufficiently clear so that lack of formal criteria for
progress is not serious nor is it an impediment to progress.
8. Some formal criteria for progress can be given, but is not as important
as continued progress.
9. Progress has been, and will continue to be informally tested by
interaction with mathematicians outside f.o.m. and mathematical logic.
10. There are prototypical results (unfortunately, demonstrably false)
which indicate anticipated future stages of progress.
11. Over the next couple of months I will make some announcements which
represent a next stage of progress.
********

The program has its origins in the incompleteness theorems of Godel. It is
clear that the first incompleteness theorem does not provide an
intelligible example of an independent statement, and that the second
incompleteness theorem does provide an intelligible example - namely the
consistency statement. All of this is obvious, even without any formal
criteria for intelligibility. It also was clear that the example provided -
the consistency statement - was metamathematical rather than mathematical,
again without any formal criteria for mathematical.

Why is the distinction between mathematical and metamathematical a crucial
one, even though it has never been made formal? One reason is that it did
not affect - or even threaten to affect - mathematical practice. Anyone who
doubts this can test the significance and legitimacy of this distinction by
talking to a range of mathematicians. Obviously, it has deeply affected
mathematical culture, which is something quite different.

But for me, the significance of the distinction is very clear and very
striking, and I certainly do not need such confirmation.

The natural outgrowth of the incompleteness theorems is: is there a
mathematical statement that is independent of the usual axioms for
mathematics (i.e., ZFC)? Conveniently, there was a prime candidate, which
was of independent vital interest for set theory. Namely, CH = continuum
hypothesis. Godel (1938) proved that if ZFC is consistent then ZFC + CH is
consistent. Cohen in 1962 proved that if ZFC is consistent then ZFC + notCH
is consistent.

Thus CH was the first example of the demonstrable independence of a
mathematical statement from ZFC. In fact, a statement vitally important for
abstract set theory.

But abstract set theory, and in particular, arbitrary sets and functions of
a real variable, is upon reflection of a very different character from the
ordinary mathematical objects of everyday practice. Again, is this
distinction significant and/or formalizable?

The distinction is significant, as can be seen by considering, for example,
the following series of concepts. Arbitrary real functions, projective real
functions (sets), analytic sets of reals (sets), Borel real functions,
limits of continuous real functions, continuous real functions, infinitely
differentiable real functions, continuously differentiable real functions,
real analytic functions, algebraic real functions, polynomial real
functions, linear real functions, polynomials over the integers, integral
linear functions.

Also, the distinction is formal. However, one does need to rely on
"mathematical" which is not formalized, becuase there are various ways to
unnaturally encode some of these classes in others. But at the extremes,
the distinction is formal - usually made by discussing third order, second
order, and first order arithmetic concepts.

As the list continues, it represents stronger and stronger regularity
conditions. Generally, mathematicians work within the confines of the
stronger regularity conditions. Special recognitions are awarded for
mathematics involving the stronger regularity conditions. The stronger
regularity conditions are also considered closer to applications - also
considered highly desirable.

So now we have a first statement of the program: find a mathematical
statement independent of ZFC which lies within the confines of stronger and
stronger regularity conditions.

Why is this significant? For me, it is obvious. But one can test the
significance of this by looking at Journal articles, and talking to a range
of mathematicians. It is remarkable to what extent mathematician's eyes
glaze over once it is seen that you are talking about a weaker regularity
condition then they are used to thinking about. There is also the polite
smile.

If the incompleteness phenomenon is going to touch mathematicians, it must
connect up with the stronger regularity conditions.

Now what does "touch" mean? Well, there is the very strong notion of
"touch." And that is, where one shows that some problem that core
mathematicians actually work on is independent of ZFC.

I have always backed off from stating the program that strongly. Here is
the background behind that judgment.

First of all, set theorists were working on the continuum hypothesis
(before giving up), and that was shown to be independent of ZFC. And, to
varying extents, certain problems concerning projective sets of reals and
analytic sets of reals were also worked on before they were shown to be
independent of ZFC. So why not expect this to happen with the stronger
regularity conditions?

The mathematics involving strong regularity conditions is clearly of an
essentially different character than mathematics involving the weakest
regularity conditions. For one, there exist orders and orders of magnitude
more mathematics with strong regularity conditions. This already shows that
a vast amount can and was done without regard to extending the axioms of
mathematics beyond ZFC. This is simply not the case with the weakest
regularity conditions. One comes up against suspicious situations with no
structure extremeley quickly. And soon after Cohen, various independence
results concerning projective sets and analytic sets were obtained, which
were considered by descriptive set theorists previously. Not all that much
can be done in ZFC with these very weak regularity conditions, in stark
contrast to the situation as we strengthen the regularity conditions.

Furthermore, there isn't to this day any firm candidate at the stronger
regularity conditions for a mathematical independence result from ZFC -
among the existing open problems of mathematics. One can of course just
list all open problems of core mathematics and state that they are all
candidates. But this is unconvincing, and to my knowledge, absolutely no
one even contemplates on working on the independence of such problems. The
reason why set theoretic problems looked suspicious was because they were
particularly elemental and had no - or very little structure. (Much later,
people were able to show the independence of set theoretic problems with
more structure).

So if "touching" the mathematician with this strong notion of "touch" is
way out of reach, then what is within reach?

a. Proving the independence of existing problems or theorems based on
strong regularity conditions from strong subsystems of ZFC.
b. Developing new subareas of mathematics based on strong regularity
conditions which are independent from all of ZFC.
c. Mixtures of a and b.

Again, what is the significance of such work? Well, for me, it is
completely evident. But again, one can test such work with discussions with
a range of mathematicians. I do this on a continuing basis.

Each of a,b,c have met with continuing progress, and I have been involved
with all 3. In particular, my work on b is more clearly reflected in the
following restatement:

b'. Developing new subareas of discrete/finite mathematics in which the
main theorems can be proved with large cardinal axioms (extending ZFC), but
not without them.

Until recently, my examples in b' required familiarity with Ramsey theory
(a classical area of combinatorics) to appreciate their simplicity. New
examples no longer require such familiarity. Is this a formal distinction?
Of course not. But easily tested with the help of mathematicians.