FOM: sIncompleteness program/gii

[Harvey Friedman]

Reply to Shoenfield 12:23PM 9/17/98.

>      About Godel: I think there is no doubt that Godel was very
>interested in the consequences of large cardinal axioms.    As to
>what kind of consequences, he says the should be "far outside the
>domain of [large cardinals]" and "where the meaning and ambiguity
>of the concepts entering into them can hardly be doubted".   Of
>course, he did not intend these quotes to delineate the conse-
>uences exactly; but I think that any consequence expressible in the
>language of PA would satisfy his conditions.   Because of this, I
>do not think the quotations support the incompleteness program
>which you and Steve favor.

You neglect to acknowledge Godel's explicit mention of "even in the field
of Diophantine equations" and "... finitary number theory ... where the
meaningfulness and unambiguity of the concepts entering into them can
hardly be doubted." Thus you are biasing your reading of Godel **by leaving
out the crucial passages that indicate some of his very major highlighted
concerns**. It is obvious that Godel was very concerned with many of the
same drawbacks that Steve and I have emphasized in connection with the
independence results that reside in the more set theoretic contexts.

Another component, which we emphasize, is admittedly not explicit in these
quotes from Godel; that is, the utterly crucial distinction between
mathematical and metamathematical/formal. But it seems clear from the tone
of these quotes that Godel was interested in potential impact on
mathematical practice. Experience in talking to mathematicians makes it
clear that potential impact on mathematical practice depends crucially on
the statements in question being mathematical rather than metamathematical
or formal.

Godel was not very gregarious, and certainly didn't spend much time getting
feedback for his views and ideas by talking to mathematicians with any
frequency. I spend a lot of time doing this. I have no doubt that if, by
chance, Godel did not recognize the crucial distinction - which is now so
obvious - between mathematical and metamathematical/formal for potential
impact on mathematical practice, then he certainly would have after
extensive discussions with mathematicians.

Thus, I take the position that using these Godel quotes in connecetion with
a discussion of this program is legitimate, provided that it is accompanied
by some caveats, such as the ones I have continued to offer.

But you must take into account the rather pointed language in the words
"even in the field of Diophantine equations" and "... finitary number
theory ... where the meaningfulness and unambiguity of the concepts
entering into them can hardly be doubted."

Of course, the utter obviousness of the central importance of this program
for f.o.m. - which is very widely acknowledged - is not dependent on
Godel's explicit remarks. But his remarks are relevant enough for me to
mention in this connection.

What is of course less obvious is: how strong will the results get in this
program - in light of the nearly continuous set of improvements over the
last 30 years. It is clearly an evolutionary process.

Here are the Godel quotes yet again:

"It can be proved that these axioms (Mahlo cardinals) also have
consequences far outside the domain of very great transfinite numbers,
which is their immediate subject matter: each of them, under the assumption
of its consistency, can be shown to increase the number of decidable
propositions even in the field of Diophantine equations."

"The mere psychological fact of the existence of an intuition which is
sufficiently clear to produce the axioms of set theory and an open series
of extensions of them suffices to give meaning to the question of the truth
or falsity of propositions like Cantor's continuum hypothesis. What,
however, perhaps more than anything else, justifies the acceptance of this
criterion of truth in set theory is the fact that continued appeals to
mathematical intuition are necessary not only for obtaining unambiguous
answers to the questions of transfinite set theory, but also for the
solution of the problems of finitary number theory (of the type of
Goldbachs's conjecture), where the meaningfulness and unambiguity of the
concepts entering into them can hardly be doubted."

>     I now understand the reasons for your remarks about quotes B
>and C; but I do not think these reasons imply that B and C are
>either false or misleading.

I said "Hilbert's 10th problem was not solved until about 1970, and so even
without *reasonable* the claim seems to involve an unconventionally broad
notion of Diophantine equation."

>I do not think people take "propo-
>sition about Diophantine equations" to imply that the equations
>must be "reasonable",
>nor do I think that restrict such propositions
>to be statements that a particular Diophantine equation has a
>solution.

It is fairly clear that what Godel had in mind was only the existence of
particular sigma-0-1 sentences whose matrix has a universal bounded
quantifier, or possibly the existence of a particular sigma-0-1 sentences
whose matrix is an exponential Diophantine equation. In neither case does
this qualify as a "proposition about Diophantine equations" in any normal
sense of these words.

To this day, there is no known independent statement which is a "reasonable
proposition about Diophantine equations."

>     What I meant by "better" in my remarks on Paris-Harrington is
>not precise, much less formalizable.   In this particular case, it
>means that P-H is a simple generaliztion of a well-known theorem
>provable in PA.

Why didn't you follow the Shoenfield caveat about the use of such concepts,
and instead simply say "a simple generaliztion of a well-known theorem
provable in P" as you have said here?

My point about mentioning

THEOREM. For all k,r,p >= 1 there exists n so large that the following holds.
Let F:{1,...,n}^k into {1,...,n}^r be regressive in the sense that
F(x_1,...,x_k) <= min(x_1,...,x_k). Then there exists A contained in
{1,...,n} of cardinality p such that F[A^k] has cardinality <= k^k(p).

(This is independent of PA, and in fact equivalent to the 1-consistency of
PA over exponential function arithmetic).

is that this statement avoids the use of "relatively large" which has the
drawback of being a concept which is of a different character than normal
combinatorial concepts. I.e., the dual use of an integer as both an element
of a set of integers and a cardinality. It also involves ordinary tuples
instead of unordered tuples.

>     I don't think we have any disagreement about CH.   I thought
>your previous posting implied that all the interesting consquences
>of PA were in abstract set theory; but apparently you did not
>intend this.

Correct. (Incidentally, you wrote PA where you must have meant CH). I would
say, however, that the consequences of CH to which we both refer are for
"set theoretic statements in real analysis" or "set theoretic statements in
group theory" etcetera. This is different than saying that they are
statements in abstract set theory.

>     I am sorry that we are still not communicating about regularity
>conditions.   It would certainly help if you would answer a question
>which I have posed in two previous postings.  You want to find
>unprovable sentences satifying strong regularity conditions, so a
>regularity condition must be a condition on sentences.

I want to find unprovable sentences involving only objects satisfying
strong regularity conditions. In particular, pi-0-3, pi-0-2, pi-0-1 are
most appropriate. Let's start again from here, if you want.

Reply to Shoenfield 11:37PM 9/16/98.

>For both, the main point is that the problems of set theory
>which I described are less important than certain other problems.

This is not exactly what I said. I said that some programs are more
important than others for f.o.m. and some programs have more general
intellectual interest (gii) than other programs.

>These are the problems which are of interest to core mathematicians;
>interest here means more than curiosity, and implies a feeling that
>the solution of the problem has significance for the kind of mathe-
>matics which they do.   This feature can also be described (in terms
>which both Steve and Harvey have used) as: the problem has interactions
>with core mathmatics.

This does not take into account my posting 12:11 AM 9/15/98, "script: can't
runj away." Here I discuss some interactions with core matheamticians (and
other mathematicians) regarding a problem that exhibits significant
metamathematical phenomena but where the "significance for the kind of
mathe-
>matics which they do" is explicitly downplayed by me. The fundamental
>character and the concreteness and the simplicity are sufficient here.

>     What reasons do Steve and Harvey have for saying these problems
>are particularly important? Steve says that this results from the
>foundational perspective.

Are you talking about the program or some specific independence result?

>  If I have learned anything from the dis-
>cussions on fom, it is that the various participants have quite
>different ideas of where the fom perspective leads.

If you take the general intellectual perspective seriously and ponder what
is fundamental from first principles in the f.o.m. context, you will be
lead to the essentially the same directions and values that I have. I have
plently of evidence of this through my extensive and continual discussions
with nonlogicians and nonmathematicians. There is a lot of common ground
out there, when it is not clouded by technical parochial issues. Don't get
me wrong - a mastery of technical parochial issues is essential for making
deep progress in genuine f.o.m. of permanent value. It just that one should
keep the big picture in mind at all times - even when one is correcting
typos in a 100 page manuscript (actually it is OK if the big picture comes
back immediately after the corrections are made).

>I see no
>reason to think that it leads to working on problems with interactions
>with core mathematics.

If the issue is the incompleteness phenomena, and mathematicians actually
think and act like it is appropriately ignored, then this surely is an
indication that  the extent or range of the incompleteness phenomena is a
crucial issue?

>Harvey says that these problems have general
>intellectual interest (gii).   I am not sure what this term means;
>I take it to mean intellectual interest which is not tied to any
>particular field.

Right. What I said in the previous paragraph is typical of gii talk. It is
understandable and intriguing to a huge range of people - or at least
intellectuals.

>I see no reason why problems of gii should be
>more important than problems of special intellectual interest; I
>think that in practice, the reverse is true.

Most of the biggest epochal advances in science surround investigations of
general intellectual interest.

>Problems with inter-
>actions are of slightly more gii than problems without, since they
>deal with 2 fields instead of 1; but I see no reason why interactions
>with core mathematics have more gii that interactions with non-core
>mathematics.

You misunderstand me. The issue of gii is the extent of the incompleteness
phenomena. Is there any permanent barrier to finding an incompleteness in
something either in existing normal mathematics, or something that is
regarded as a new part of normal mathematics? How about, just involving
normal mathematical concepts in their normal contexts? If the answer is NO,
then that has the most profound implications for the future of set theory.
These are the issues of general intellectual interest.

>     As the above shows, it is very diffucult to convince a person
>that a criterion for the importance of a mathematical problem is
>particularly significant if he does not alread believe this.

I am, instead, talking about the significance of a program or project.

> I
>think that this is fine, and that each person should choose the
>problems he works on according to his own criteria of importance.
>If (as seems unlikely) I convinced Steve and Harvey to stop working
>on problems with interactions with core mathematics, the result would
>be a loss of interesting results of the type which they have produced
>in recent years.   If (as seems even more unlikely) Steve and Harvey
>convinced the leading set theorists to spend their time working on
>such problems, the result would be a disaster for set theory.

I never said that the set theorists should stop working on what they do.
You more or less explicitly compared the work I was doing on the
incompleteness phenomena unfavorably to certain developments in set theory.
I responded by indicating that the program I work on has greater
significance for f.o.m., and also the future of set theory depends on the
level of success acheived, and that it has greater general intellectual
interest. This is because of the CRUCIAL ISSUE that it addresses - not the
FACT of interaction with core mathematicians and mathematics.

>     Harvey also touches on a question which I barely mentioned: how
>does one decide which new axioms of set theory are acceptable?   As
>he remarks, V=L solves more unsolved problems than any other new axiom
>which has been considered.   It is, as he said, rejected by set theor-
>ists because it limits the sets which one can consider.   If one
>is only interested in constructible sets, one does not need such an
>axiom; one simply decides to only prove theorems about constructible
>sets.

Right.

>     Early large cardinals had a justification similar to that of the
>axiom of infinity.   The latter postulates a set containing 0 and
>closed under the sucessor operation.   Similarly, the existence of
>an inacessible cardinal postulates the existence of a set closed
>under certain set-theoretic operations.   I once suggested to Solovay
>in a casual conversation that the two axioms were equally justified.
>He disagreed. It is easy to visualize the first set, say as a row of
>telephone poles without end.   But the structure of the second set is
>very complicated.   He suggested it would be an excellent project to
>analyze this structure in a way that makes the existence of an
>inacessible more evident.   In any case, we do not have any such
>closure definition for the interesting large cardinals, such as a
>measurable cardinal.

This is a very good and important project which I think about from time to
time. I did write some manuscripts on reaxiomatizations of set theory in
simpler terms, but it does not directly deal with this project in the way
one could hope.

Are you working on this important project? How many people in set theory
are working on this important projects?

>... It is that one should first decide, using ones
>intuition, what the fundamental concepts of the subject are and then
>concentrate on problems concerning these.   If the set theorists I
>mentioned had adopted this perspective, set theory would have been
>a much less interesting subject than it is today.

I guess I feel more attracted, perhaps, to a modification of this statement
which you may still disagree with:

One should first decide, using one's instinct for general intellelctual
interest, what the fundamental issues in the subject are and then
concentrate on problems and programs that clarify them.