[FOM] Comments on Feferman on Hellman

[Harvey Friedman]

These are comments on an article by Solomon Feferman entitled:

Comments on "Predicativity as a philosophical position" by G. Hellman

This Feferman article can be downloaded from the page

http://math.stanford.edu/~feferman/papers.html

article number 36.

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

My overall assessment of Feferman's article, as well as his other articles
in which he criticizes what he calls the "Godel-Friedman program", is that
there is a failure to recognize the long term incremental nature of the
major advances that span roughly 40 years.

Some criticisms apply better to early stages of the program. To his credit,
criticisms are sometimes adjusted as the program develops.

However, the adjusted criticisms are not sufficient to fairly reflect the
changing situation. The result is that there remain contrived complaints,
and glaring double standards that are readily apparent to knowledgeable
experts. 

There are also somewhat significant mathematical errors that could have been
easily corrected if I had been sent drafts before publication. This has been
a continuing problem.

There is a common trap when criticizing someone's long term research
programs. It is all too easy to come to some negative conclusion early on,
when results are comparatively weak and particularly vulnerable. Then, when
they strengthen, perhaps greatly, one tends to try to justify earlier
negative critiques, and grudgingly adjust to the new developments - only
when forced to.

Several notable people have fallen into this kind of trap when criticizing,
say, reverse mathematics. That it is not robust, that it doesn't apply to
hardly any mathematics, that it is all trivial, that mathematicians can't
relate to what is being accomplish, etcetera, etcetera. All of these
criticisms have been demolished.

The same is happening with the forty year program of mine under discussion.

When you get on the wrong side of history in this way, it can be rather
painful to admit openly that you have been fundamentally wrong. A few, but
not most, of the people who criticized reverse mathematics in this way have
recanted. So it is for the 40 year program under discussion.

It is even the more painful when you realize that had your advice been
taken, crucial advances might not have occurred and the field may have been
irreparably damaged - or at least progress delayed by perhaps a century or
more. Certainly if the prominent people who complained about reverse
mathematics from the outset were seriously listened to, then in my opinion
there would be a gaping hole in f.o.m. I do admit that this point has to be
carefully argued. 

However, in the case of the 40 year program under discussion, the huge
difference in the f.o.m. situation that would result if prominent
criticizers were taken seriously, has become obvious, and will become much
more obvious still as recent developments unfold.

Below you will see a lot of information about work that is much more than a
few weeks old. I will write in general terms about very recent work, which
has again changed the picture very considerably.

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

Let me state at the outset what my 40 year program is and where it is now. I
am not going to be comprehensive here. Nor am I going to be very polished
here. As you shall see, I am just too busy right now for that, SINCE RIGHT
NOW THE PROGRAM IS ADVANCING DAILY AT AN ALARMING RATE THAT IS YET TO BE PUT
UNDER CONTROL. But nevertheless it is not hard to respond to the article in
question.

It started with my conviction already 40 years ago that

1. An absolutely crucial issue for the foundations of mathematics is whether
there is any significant use of set theoretic methods for "real
mathematics". Put productively, can substantial set theory be used in any
essential way to obtain interesting, valuable, productive, ... ,
mathematical information.

2. In particular, I was entirely convinced that the future of at least a
very substantial portion of f.o.m. depends on appropriate examples of 1. The
future of set theory as a subject of great intellectual visibility and
importance depends on this.

3. Put another way: f.o.m. will be at least crippled without appropriate
advances in 1.

4. It was well known from Godel that the answer to 1 is yes if "mathematical
information" is replaced by "information about formal systems of abstract
set theory". It was also well known from Godel and Cohen (and successors),
that the answer is yes if fundamental abstract set theory, and overtly set
theoretic mathematical problems involving uncharacteristically unruly
uncountable sets are included in 1.

5. I was convinced already 40 years ago that no amount of results showing 1
for assertions involving unruly uncountable sets will provide the kind of
mathematical information needed for 2,3.

6. In particular, it is clear that mathematics at the top level is very
concrete - and when it is not so concrete, it BEGS to be more concrete.

7. In particular, mathematics is really Pi01. YES, Pi01. When it is Pi02 or
Pi03, it BEGS to become Pi01 by placing upper bounds on the existential
quantifiers. Look at Fields medals, prize winning work, million dollar
problems, etcetera. Sure, sometimes there are real numbers and continuous
functions, but usually it is clear by approximation that what is going on is
very finitary. E.g., finite simplicial complexes. And when that is not
clear, time and time again when the problems are solved, there is a Pi01
essence that is the hard part that easily implies the full result. So the
CONTENT is Pi01. And even when that is perhaps debatable, the cases people
are really interested in push us down to Pi01.

8. I became entirely convinced, rather early, that it is very unlikely that
any yes/no problem stated by mathematicians, that is not overtly set
theoretic, requires any substantial use of abstract set theory.

9. It turns out that 8 is almost false! Well, 8 is at least questionable.

10. I found that Kruskal's tree theorem and the Robertson/Seymour graph
minor theorem necessarily use methods that could reasonably be described as
"set theoretic". Of course, it is way below anything like full use of the
power set of N. Nevertheless, it is definitely a weak use of uncountability,
that is in stark contrast with the vast vast vast preponderance of
mathematics.

11. Debs and Saint Raymond, two French functional analysts, studied various
forms of Borel selection, and chose to treat them in the very general
setting of analytic sets. They knew that they had to use highly set
theoretic methods to establish this. This wasn't itself new, since it had
been known for decades that in the context of analytic sets, in order to get
certain basic kinds of results, one needs to use high doses of set theory.
(Opposite answers can be obtained from a different kind of axiom - V = L).
But it is also well known that such results for BOREL sets were already
obtained in the classical literature well within ZFC, with essentially NO
substantial doses of set theory.

12. So this was a twist: I asked Debs what happens if their work is
restricted to Borel sets? So I - the logician - was being the relatively
concrete person. 

13. I soon found that the Debs/Saint Raymond work on Borel selection needs
very substantial abstract set theoretic methods - when stated for (finite
level) Borel sets and functions! One of them is independent of ZFC. This
work has appeared in Logic Colloquium '01, which just came out from ASL. See
Theorem B and Proposition C below under 14.

14. Even well before 13, I published in 1982 the following Borel selection
statement that WAS NOT A PREVIOUSLY CONSIDERED PROBLEM BY MATHEMATICIANS.
However, its quality in the Borel context is so high, that I readily and
reliably impress any working mathematician with it who is open to Borel
sets. When you look at this statement, you see that it could just as well
have been an element of an ongoing program of a working mathematician. How
could you tell a priori whether Theorem A was the stuff I made up, or
Theorem B and Proposition C are the stuff I made up? Let's look at them:

THEOREM A (made up my me, proof heavily uses Tony Martin's BD for the
forward direction; elaborating on earlier work of me for the reversal). Let
V be a Borel set in the plane, symmetric about the line y = x. Then V or its
complement has a Borel selection.

THEOREM B (essentially made up by Debs/Saint Raymond for analytic sets V: I
just replaced analytic by Borel, obvious corollary of Debs/Saint Raymond,
for the forward direction; elaborating on earlier work of me for the
reversal). Let V be a Borel set in the plane, and E be a Borel set in the
line with empty interior. If there is a continuous selection for V on every
compact subset of E, then there is a continuous selection for V on E.

PROPOSITION C (essentially made up by Debs/Saint Raymond for analytic sets
V: I just replaced analytic by Borel, obvious corollary of Debs/Saint
Raymond, for the forward direction; elaborating on earlier work of me for
the reversal, provable using e.g., measurable cardinal (overkill)).  Let V
be a Borel set in the plane, and E be a Borel set in the line. If there is a
Borel selection for V on every compact subset of E, then there is a Borel
selection for V on E.

15. So this experience, and the experience with the extended Kruskal Theorem
(EKT), a precursor to the graph minor theorem of Robertson/Seymour, and
readily absorbed by Seymour in discussions with me, shows the following:

IT IS POSSIBLE TO COME UP WITH NEW MATHEMATICAL STATEMENTS WITH PROSCRIBED
INDEPENDENCE PROPERTIES WORKING BACKWARDS AND USING INTIMATE KNOWLEDGE OF
NONSTANDARD MODEL CONSTRUCTIONS, PROOF THEORETIC TECHNIQUES, AND THE LIKE,
WHICH ARE FULLY SATISFACTORY IN THE FOLLOWING SENSE. IT IS A MERE ACCIDENT
OF HISTORY JUST WHEN PEOPLE WOULD COME ACROSS SUCH STATEMENTS WITHOUT ME, IF
THEY HAVEN'T ALREADY.

16. So, with great confidence, I adopted this as my driving method. I don't
give up on the BIG PROGRAM just because I don't believe that there are
arithmetical sentences hanging around in the literature waiting to be proved
to be independent. I only care about discovering concrete sentences that
clearly, in the long run, would have been arrived at, by obvious standard
natural intellectual processes.

17. In particular, as I develop statements, I tell stories to myself (and
sometimes others) about just how their coming up is inevitable if basic
intellectual processes are at work. After all, mathematics has been around
as a serious professional enterprise in a tiny tiny tiny tiny tiny fraction
of a second in geological time. What will it look like 1 billion years from
now? The sun will still be working well.

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

18. Around 1982, I found that the famous Kruskal theorem for finite trees
could only be proved impredicatively (on the Feferman-Schutte treatment of
predicativity). This was a Pi11 sentence independent of predicative systems.

Then I gave a finite form of Kruskal's theorem, which was Pi02, and showed
that it also is independent of predicative systems.

It was evident to me that the way that I gave my finite forms of KT were a
somewhat standard way of giving finite forms of certain kinds of infinite
statements. KT says that something happens in any infinite sequence of
finite trees. My finite form says that the same thing happens in any
sufficiently long finite sequence with a given growth rate - say the i-th
tree has at most c+i vertices. Then you need the length to be large relative
to c. 

19. To my SHOCK, Feferman complained seriously and publicly that my finite
form of KT was not natural mathematically!! He refers to this as FKT
(Hellman refers to it as FFF).

20. To his credit, Feferman has, on page 7 of this item I am reviewing now,
paragraph c), discussed his original negative determination, and refers to
how he has changed views:

"Indeed I have retreated on this to an extent, having written more recently
on p. 46 of my part of the symposium "does mathematics need new axioms?"
(Feferman, et al., 2000) as follows:"

21. What was my reaction to the original - later retreated from - criticism
of Feferman about FKT (FFF)? Fivefold.

a. I checked with several experienced and gifted mathematicians to see what
reaction they had to my finite form(s). To my non surprise, some said that
they were quite familiar with the idea of bounding growth rates of
sequences, to get bounds on their length, and that the whole idea was
entirely natural and well appreciated.

b. I found that Weiermann (and others) studied, very carefully for its own
sake, just what happens when you look at finite sequences of trees and other
objects with various bounds on rates of growth. They found various exciting
threshold phenomena, and this is now a little bit of a cottage industry. If
Weiermann and company would have taken Feferman's negative comments
seriously, I don't see how they would have developed this mathematically
beautiful and intricate threshold theory for growth rates. Weiermann has
written a number of interesting papers and given a number of plenary talks
on this. 

c. I always think that whatever I do, I can do better, since I get smarter
as I get older (unfortunately, this cannot continue forever).

d. So, independently of Feferman, I always wanted to find a finite form of
Kruskal's theorem that was more gripping - say involving only ONE finite
tree! 

e. I succeeded well with this, and the state of the art finite forms - from
many points of view - are published in the volume dedicated to Solomon
Feferman - the Feferfest volume. Unfortunately, I was not invited to the
actual meeting held in his honor.

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

22. I did more in wqo theory. Various people complained about EKT - extended
Kruskal's theorem - which I "cooked up" in order to get past Pi11-CA0. So
what was the fate of the EKT complainers?

23. I showed EFK and its proof to Seymour, who liked it. It later figured in
some way in the graph minor theorem, where the unique place in the entire
long proof that has any logical strength - just a few pages - is closely
related to EKT. 

24. After the graph minor theorem was announced, I exploited this close
relationship with EKT to write a joint paper with Robertson and Seymour
establishing, with their help, that the graph minor theorem cannot be proved
in Pi11-CA0. 

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

25. Let us fast forward. I knew what HAD to be done. There MUST be suitably
beautiful results in DISCRETE MATHEMATICS that require big doses of set
theory. Without this, a huge portion of f.o.m. is doomed. Even better would
be FINITE MATHEMATICS, and ultimately, a huge portion of f.o.m. is doomed if
we cannot get to Pi01. In fact, Pi00 would be better - stay tuned.

26. Wqo theory is terrific discrete mathematics, but it just doesn't seem to
require really big doses of set theory. So one MUST look elsewhere. It seems
that it was best to work with infinite discrete mathematics.

27. The most basic objects in infinite discrete mathematics are of course
the infinite sets of natural numbers. The search for independent statements
here was a rather daunting task, as there are no Borel functions to code
stuff up so as to apply omega models. In the Borel work - Borel determinacy,
Borel diagonalization, Borel selection (including Debs/Saint Raymond), I was
always able to manipulate nonstandard models of set theory - but they were
always omega models. The integers were standard.

28. But, in the realm of infinite sets of natural numbers, I must face the
manipulation of non omega models of set theory. There are nonstandard
integers. 

29. I had ideas of how to do this kind of thing with long towers for some
years, but was not satisfied that the resulting statements were anything
more than isolated curiousities.

30. So I made a big effort in the 90's to put these towers into a clearly
natural broad mathematical context.

31. I succeeded well in doing this. The result is a subject called BRT =
Boolean Relation Theory, the title of a forthcoming book, which is well on
its way, and will be put up on the web when completed.

32. It is completely obvious that BRT is an entirely inevitable mathematical
development, since one can clearly state an entirely natural intellectual
process that arrives at BRT.

33. At the moment, there is no specific BRT statement that is appropriately
natural - there is some ad hoc choice present in these BRT statements. (This
could change).

34. However, there are very natural FINITE CLASSES of statements in BRT,
which form CLASSIFICATION CHALLENGES.

35. In general, these classification challenges are too difficult (at least
for me). But I found one of them, a very natural one, which has 6561
statements, that I could handle. Here 6561 = 3^8.

36. I proved that all of these 6561 statements are provable or refutable
using large cardinals. I prove that this cannot be done without using these
large cardinals. 

37. Upon examination of the classification, I found very striking features,
which I describe below in 44.

38. Now Feferman has SHOCKED me again!! Recall how I was shocked by 19
above, and see 20 (his "retreat") and 21.

39. First Feferman questions the "mathematical naturality of (*)". (page 8).
The whole point of the 6561 classification is that (*) is not mathematically
natural in and of itself, but only as part of the whole 6561, which is
mathematically natural. Feferman perhaps has not realized that a sentence
may have ad hoc features, but be an element of a finite set of sentences
that do not have ad hoc features.

40. Second, Feferman writes a footnote as follows!

9 I am made suspicious in that respect [naturalness] by the fact that (*) is
strangely unrobust in that - as shown by Friedman and mentioned by Hellman -
any alteration of the pattern of letters A,B,C in its statement leads to a
statement that is provable in a finitarily reducible system RCA0.

TECHNICAL CORRECTION: Feferman needs to replace "provable" here by "provable
or refutable". Also, there are 11 exceptions to this - all symmetric with
(*).

This footnote of Feferman is entirely wrong headed in that he is using a
very striking feature of the classification as an argument against the
naturality of one of its instances - where naturality is only being asserted
for the collection of 6561 as a whole!!

41. Given what Feferman complains about later, there is no reason why he
just doesn't use for criticism,

"all 6561 statements can be proved using LCA, but not in ZFC"

rather than what he does use for criticism:

"instance *) can be proved using LCA, but not in ZFC".

42. Furthermore, if Feferman wishes, for some inexplicable reason, to be
fixated on a particular sentence being provable in LCA but not in ZFC, then
he can use a special feature of the classification, which is a single
sentence provable in LCA but not in ZFC, and which is natural in a sense
that *) is not:

#) for each of the 6561 sentences, if it holds with "arbitrarily large
finite" then it holds with "infinite". (NOTE: All 6561 are written with
"infinite"). 

I proved that #) is provable using LCA but not in ZFC. (In fact, provable in
MAH+ but not in MAH). In fact, #) is provably equivalent to the
1-consistency of MAH over ACA. This is the same as for *).

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

43. Once again, as in the case of his retracted objections to my FFF (see
19-21 above), I checked with mathematicians. I spoke to a few of the most
famous mathematicians in the entire world - none having any papers in logic.
All with huge reputations.

44. They were all struck by the 6561 classification, and all used, totally
independently, the word "beautiful". They also were very clearly struck by
the uniqueness of the exotic case (*) - up to symmetry - a feature which
Feferman exploited to make a (irrelevant) criticism!

45. I predict that Feferman will again "retreat".

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

46. We now come to a glaring double standard Feferman applies when
discussing the work of others that shows how lots of statements about
projective sets follow from large cardinal axioms.

47. In particular, Feferman complains that

"An essential difference from BRT is that for the set-theorists it is not
the consistency but the very existence of the large cardinals in question
that must be assumed."

48. In fact, there is no essential difference. In the case of the
set-theorists, one does not in fact need the existence of the large
cardinals in question, but only

"every Pi(m,n) sentence provable in LCA is true".

In BRT, one does not in fact need the existence of the large cardinals in
question, but only

"every Pi(0,2) sentence provable in LCA is true".

By the way, consistency is not enough. I.e.,

"every Pi(0,1) sentence provable in LCA is true"

is not enough to prove the BRT statement (*). (An error of Feferman's).

49. To make this point even clearer, I state some easy facts.

a. Every Pi01 consequence of LCA is a consequence of "every Pi01 sentence
provable in LCA is true". The latter is the same as Con(LCA).
b. Every Pi02 consequence of LCA is a consequence of "every Pi02 sentence
provable in LCA is true". The latter is the same as 1-Con(LCA).
c. Every Pi(m,n) consequence of LCA is a consequence of "every Pi(m,n)
sentence provable in LCA is true".

50. Again, I predict that Feferman will "retreat".

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

51. I think it is premature to focus right now on just what will be the
effect on the mathematics community after this 40 year development settles
down. It may not truly settle down while I am alive, and hopefully not
settle down until say 2100.

52. It is true, as Feferman says, that at a panel and in the written
proceedings, on "Does Mathematics Need New Axioms", I made some conjectures
along these lines. That the mathematicians will eventually be led to accept
large cardinals that give them beautiful consequences and round out theories
like BRT.

53. What is not premature is to obviously see that fantastic unexpected
progress has been made concerning the absolutely crucial item 1 above, over
the last 40 years. And this kind of progress is needed to continue in order
to EVEN GET THE ISSUE JOINED in the mathematical community: as to whether
they should or must rethink what the axioms for mathematics should be.

54. In particular, the development of this program has an inevitability to
it, and entirely transcends vacuous debating exercises. Daily advances can
change the picture so radically that such prose loses all relevance.

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

55. In particular, even since my last posting, there has been a sea change.
I will report in detail shortly, and also follow through with a little prose
of my own. 

Harvey Friedman