FOM: regularity conditions, general program

[Harvey Friedman]

This is a reply to Shoenfield 11:20AM 9/14/98:

>      Harvey's posting of 8 Sep under this title answered many of my
>questions on his incompleteteness program.   Here I would like to press
>him on some points which I think remain unaswered, and to make a few
>remarks.

This indicates that the FOM is working.

>     I think it is clear that in his writings, Godel did not indicate
>that this program was important.   I do not think this indicates that
>he did not think it was.   Godel was very careful in his writing; he
>would not publish an evaluation of the importance of a problem unless
>he had something substantial to say about it.

It is conventional wisdom that from these quotes and what is generally
believed about Godel, that the extent of consequences of large cardinals in
concrete contexts - with special emphasis on concrete - is of great
importance. Do you at least agree with this without the emphasis on
concrete contexts? And evidence that the concreteness of the context is an
important component for Godel can be gleaned from the word "even" in the
first quote below, and also in the words "not only" "but also" "where the
meaningfulness and unambiguity of the concepts entering into them can
hardly be doubted" in the second quote below.

"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."

>    You comment about the Godel quotes:
>     >B and C indicate a reluctance to make the distinctions that
>are now commonly made, under which B and C would be regarded as
>either false or misleading.
>    I would very much like to have this statement amplified and
>explained.

B and C are as above. What I  meant to say is this. For B, a *reasonable*
example of a Diophantine equation for which the proof that it has no
integral solutions requires large cardinals has still not been given. So
when *reasonable* is inserted, the claim, B, is not justified. Also,
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.

And in C, again the claim is unjustified even now if *problems* is
interpreted in any normal way for mathematicians.

However by recent results, one can now replace "the solution of the
problems of finitary number theory (of the type of Goldbach's conjecture"
by "the proof of interesting results in finitary combinatorics (of the
logical form of Goldbach's conjecture)".

>     I think everone agrees that Paris-Harrington is better that
>Paris-Kirby; the improvement is Harrington's main contrbution.
>However, I think it a shame that Kirby's role in this seminal
>theorem seems to be ignored.

I didn't know this was your point, and I agree. Incidentally, what do you
mean by "better" and can you formalize it? And how does this compare with
Paris-Harrington and Paris-Kirby in terms of the "better than" relation?

THEOREM. For all k,p >= 1 there exists n so large that the following holds.
Let F:{1,...,n}^k into {1,...,n} 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).

>     I think your two comments on the difference between CH and
>inaccessible cardinals are quite pertinent.   I was surprised that
>in your review of your program, you do not put more emphasis on
>the applicability of CH in fields which are (logically) more ele-
>mentary that abstract set theory.  I don't think such applications
>have disappeared from mathematics; I still see papers which give
>proofs which depend essentially on CH.

I have no idea why you are surprised. I , personally, have been interested
in applications of CH, personally. For instance, I published a paper on
"Fubini's theorem for nonmeasurable functions." It is well known that CH
implies that the iterated integrals go haywire if the multidimensional set
is not assumed to be measureable. I prove some consistency results from ZFC
that say that things can be very nice. See

A Consistent Fubini-Tonelli Theorem For Nonmeasurable Functions, Illinois
J. of Math., Vol. 24, No. 3, Fall 1980, 390-395.

Shipman worked on related matters in his Thesis, which I'm sure he will be
happy to tell us about.

I'm not sure how the applications of CH you speak about affects the
discussion we are having. I can try to respond to a focused point.

In any case, look at the Annals of Mathematics, a highly prestigious
general mathematics journal, and count the number of papers which use (or
even mention) the continuum hypothesis. What do you think the result would
be, and is this a fair test?  It seems clear that mathematics is now very
focused on, as you say, "fields which are (logicaly) more elementary than"
these applications of CH

>     Let me insert here a diversion concerning large cardinals.   It
>has been dogma in set theory since the mid-sixties that there is a
>borderline in the large cardinal hierarchy, and that cardinals below
>this borderderline do not contribute to mathematical (as opposed to
>metamathematical) results.   The line lies above Mahlo cardinals and
>below Ramsey cardinals.   Do you have any results or conjectures which
>might change this dogma into a mathematical theorem?

No. It is true that all of my applications of large cardinals to finite
combinatorics require at least Mahlo cardinals in higher numerical
dimensions. But some of them correspond to substantial fragments of ZFC
such as second order arithmetic and Zermelo, and some of them seem to
correspond to an inaccessible cardinal. I think that natural numerical
parameters can be adjusted to get seriously between an inaccessible and a
Mahlo cardinal, but I am not sure about this.

>     I don't think I made my problem with regularity conditions clear
>to you.   You say that you want to find unprovable sentences satis-
>fying strong regularity conditions.   What is the regularity condition
>on SENTENCES corresponding to one of the classes of FUNCTIONS which
>you mention?   I also asked if being finite combinatorial is a regu-
>larity condition in your sense; it does not seem to correspond to any
>particular class of functions.

Finite combinatorial corresponds to the domain of finite mathematical
objects. In set theoretic terms, a finite mathematical object is an element
of V(omega), the hereditarily finite sets. Statements about polynomials
with integer coefficients would still be (equivalently) finite or finite
combinatorial. But not statements about continuous functions on the real
numbers.

I still don't quite know what you are driving at. Perhaps the following
definition will help. Let A be a sentence of set theory. We say that A is
"equivalently pi-n-m" if and only if there is a pi-n-m sentence which is
provably equivalent to A over ZFC. Same with sigma-n-m.

I am looking for sentences A which are "mathematical", require large
cardinals to prove, and are equivalently pi-0-3, pi-0-2, or pi-0-1. In
general, as 3 goes to 1, this is better.  (This is not the only criterion.
I also care exactly what kind of objects the quantifiers range over, and
not just that the statement is equivalently pi-0-whatever. But this is
already enough to identify the progoram and distinguish it from other
programs).

Of course there is the strict concept of A being explicitly in pi-n-m
(sigma--n-m) form, which means that A is literally in that form. Of course,
this is usually grossly inconvenient.

In light of this inconvenience, there is also the concept of A being
naturally in pi-n-m (sigma-n-m) form. It is difficult to appropriately fix
the meaning of this, and also not urgnet. One is perpetually simply giving
examples of mathematical statements in natural pi-n-m form.

Of course, it is still interesting to give explanations of this notion of
naturally in pi-n-m form. Basically I just mean that it goes into pi-n-m
form with routine and well understood coding techniques. And since I am
just giving examples of sentences in natural pi-n-m and not contemplating
impossibility theorems, it doesn't seem to a high priority.

It is remarkable how many open problems in mathematics are in equivalent
pi-1-2, pi-1-1, pi-0-3, pi-0-2, pi-0-1. Also, how many open problems and
proved theorems in mathematics are in natural  pi-1-2, pi-1-1, pi-0-3,
pi-0-2, pi-0-1 form,  and therefore known to be in equivalent  pi-1-2,
pi-1-1, pi-0-3, pi-0-2, pi-0-1 form before they became theorems and were
just open problems.

The point is that mainline set theory operates in higher classses than
these, and that there are demonstrable obstructions to operating with these
lower classes. Thus the need for a new approach.

What kind of additional explanation do you need?

>     The problem I suggested ...  had, as far as I was concerned, nothing
>to do with your
>general program.   They were related to a particular result of yours.
>...I realize this leaves
>out what you probably consider the most important feature of your
>result.   But what I wanted to show was that two different people,
>in analyzing a proved theorem and deciding what extensions of it are
>worth investigating, may come to different conclusions.

But a reader is less likely to go astray and move into less interesting
directions if they examine *not just the proved theorem in isolation*, but
also what the author said about what the point of the results is. It also
helps greatly if both the author and the reader pay particular attention to
gii (general intellectual interest).

>     As to the topics considered in the rest of your positing (to what
>extent is fom part of mathematics; how well results in logic are
>regarded by mathematicians; the future of foundations in general
>and foundations of physics), I think we have each expresses our
>views and little could be gained by continuing.

Perhaps others on the FOM will want to weigh in on these weighty issues.

>I think that
>clarifying and explaining one's position is the main object of disputes
>on fom; if one succeeds in convincing his opponent to modify his views
>at least a little, this is an unexpected bonus.

>   You ask how I found out I was wrong about the interest of reverse
>mathematics to logicians outside the field.   The results which
>convinced me are clearly explained in your 9 Sep posting.   In response
>to your request for feedback: I found this posting as useful and
>informative as anything you have sent to fom.

Do you mean my posting "reverse math amplification"? of 13:15 9/9/98?

It didn't mention any particular results, just their form. When I wrote it,
I thought it was perhaps patronizingly elementary for the mathematical
logicians on the FOM. And I thought that every point I made was made 50
times in the literature, with all sorts of examples. E.g., see
http://www.math.psu.edu/simpson/sosoa/
I think Simpson and I may have something to learn from what kind of
explanation is effective for these key points.

Your second paragraph above is an example of what is in your first
paragraph above. It looks like the FOM works.