FOM: Central Issues in Foundations 2

[Harvey Friedman]

This is a continuation of the Central Issues in Foundations series.
Previous ones include

#1. 4:18AM 9/1/99.

In #1, I announced that I was posting such a series on the FOM, and gave a
brief discussion of a very well known and obviously central issue in
foundations of computer science, which I will refer to simply as focc
(foundations of computational complexity). We will write cc for
computational complexity, which is the mathematical development spawned by
focc. I discussed this foundational topic in the way that I did in order to
set an example. Not of

*some arcane technicalities of interest only to a small number of insulated
specialists*

but rather a topic of great general intellectual interest and of obvious
foundational character. And I chose focc because it is a foundational topic
of a mathematical character, which is not properly construed as a problem
in the foundations of mathematics. There are great foundational issues that
are not issues in the foundations of mathematics.

Even a casual glance at this topic shows that focc is of a fundamentally
different character than the preponderance of typical current research in
mathematical logic, or mathematics generally. It looks more like, say, the
inception of recursion theory, than any current practice of recursion
theory. The proper analogy is that cc looks like mathematical logic today,
but with significant differences. E.g., the biggest open problems in cc are
directly connected with focc.

In fact, when focc originated - say in the 1960's - many voices in the
mathematics community did not really regard it as properly belonging to the
mathematics community. It was all too easy for people to say "I want to
prove theorems, and not study how hard it is to construct something via an
algorithm. Once it is constructed, I move on to the next real mathematical
problem, rather than dwell on side issues." However, the great general
intellectual interest of focc was widely recognized by more reflective
people, and both focc and cc became very well known, and are respected
components of the computer science community.

In fact, a case can be made that the P = NP problem (and close variants) is
currently regarded as the most significant open mathematical question by
the scientific community - although it must be recognized that large
portions of the scientific community probably do not recognize the
significance of mathematical questions.

And how did the P = NP problem and its close variants get its present
status? Through its great general intellectual interest.

DIGRESSION: In fact, focc/cc really got on the map when a kind of "reverse
complexity" was introduced. The analogy with "reverse mathematics" is quite
instructive. Suppose you show that a lot of problems are in NP (i.e., can
be solved in nondeterministic polynomial time on the asymptotic Turing
machine model). You want to know if you can "reverse" these problems. You
show that a surprising number of them are NP complete. This can be viewed
as showing that you can simulate the effect of any NP computation using
that problem as an oracle. Similarly with regard to many other natural
complexity classes. [I leave it to someone else to polish up this rough
statement of an analogy between reverse mathematics and this essential
aspect of focc]. In any case, the "reverse" idea is at the heart of a
variety of mathematical topics of great importance, including the early
stages of recursion theory, focc/cc. END.

Now of course virtually any subject periodically needs to renew itself,
often by returning to the original issues that generated it. Cc has often
renewed itself in this way, and spawned additional areas of investigation
with their own additional foundational issues. E.g., circuit complexity,
computational geometry, cryptography, etcetera. I don't intend to get into
a thorough discussion of foundations of computer science here, but let me
say two things:

1. Many topics in the foundations of computer science form a model of
foundationally driven mathematical work that people in mathematical logic
and many other areas of mathematics could learn from. The volume of
foundationally driven current work in the pure mathematics community is
much lower.

2. Not all topics in theoretical computer science form such a model of
foundationally driven mathematical work. In fact, is to be expected that
over the years, many specialized topics in theoretical computer science
have emerged, with their

*own arcane technicalities of interest only to a small number of insulated
specialists,*

a phrase I have used above.

3. But there is plenty of stuff in 1 to concentrate on, rather than dwell
on 2.

Enough about foundations of computer science in this posting.

**********

A HALLMARK OF FOUNDATIONALLY DRIVEN RESEARCH

A constant critical examination of mathematical constructions and projects
in light of well defined purposes and goals of general intellectual
interest. E.g., this kind of reflection led to the placing of resource
bounds on the action of Turing machines, where one moves from recursive
sets to, e.g., polynomial time recognizable, nondeterministic polynomial
time recognizable, and polynomial space recognizable sets of finite
strings. Nobody knows for sure whether these classes are all the same or
whether they are all different. People really care - because of the general
intellectual interest.

GENERAL REMARKS ABOUT THE BRANCHES OF MATHEMATICAL LOGIC

As I have stressed many times in previous postings, the current subject
called mathematical logic, with its fairly representative division into
four subareas, arose out of work on specific mathematical problems
emanating out of the consideration of issues in the foundations of
mathematics. Mathematical logic, through its four subareas, has developed
over the years with steadily less connections to issues in the foundations
of mathematics. This is a trend that has been going on for many decades,
and by now, the connections with f.o.m. are typically remote to nonexistent.

In particular, there have been several open challenges on the FOM to the
effect of asking for a clear statement as to specifically what foundational
issues are being addressed by specifically what developments in
mathematical logic? I think that no one has attempted to meet these
challenges to date. This challenge has been most frequently made with
respect to recursion theory. However, this challenge is also appropriate
for the other three subareas - set theory, model theory, and proof theory.

Now let me say right off the bat that all four of these subareas share the
following feature: that the preponderance of the current work is not
foundationally driven. I.e., not motivated by issues in the foundations of
mathematics. And that the evaluation of research is not made with reference
to issues in the foundations of mathematics.

In fact, the tendency is to evaluate whatever foundationally driven work
there is in mathematical logic solely with regard to its purely technical
content, divorced from its foundational purposes. For example, this is like
dismissing the original work on the verification that many different models
of computation lead to the same class of partial recursive functions as
"simply routine" without regard to the crucial foundational issue being
addressed. Or dismissing the original work formulating the standard axioms
and rules of inference for intuitionistic predicate calculus as "trivial"
because there is no nontrivial theorem involved in this formulation. Or
dismissing the Godel 2nd incompleteness theorem as "good but not
outstanding" because the technical complexity of the proof is significant
but not great compared with outstanding results from number theory. Another
way of dismissing such foundationally driven work is to cite the lack of
applications of these developments to the ongoing practice of core
mathematics.

The previous paragraph illustrates a principal way in which the
foundational aspects of mathematical logic get expunged from the practice
of mathematical logic. What gifted person is going to spend their career
pursuing foundationally driven research when, in the evaluation process,
the foundational component is going to stripped clean in favor of the
technical component (or the applied component)? In foundationally driven
research, the technical component is there simply to serve the foundational
purpose.

Having said that, the situations in these four subareas definitely differ
in detail. For all four subareas, there are central issues in foundations
of mathematics that are closely connected to that subarea, at least in one
or more of these senses:

A. There are many mathematical problems generated by issues in foundations
of mathematics for which the practitioners of that subarea are best
qualified, or at least highly qualified, to work on them.

B. The issues in foundations of mathematics directly impinge on the
suitability of the key constructions that underly the subarea.

The consequence of A is that there may be a large accessible set of
specific problems which are of more general intellectual interest than what
is being commonly being worked on. The consequence of B can be put in a
positive and a negative way. The positive is that there may be an
opportunity to overhaul the basic setup, using experience with the existing
framework, to increase the general intellectual interest of work in that
subarea. In the vernacular, this is called "reinventing oneself." The
negative is that the subarea may become obsolete in favor of a new, related
area of greater general intellectual interest.

Here are some general remarks about the branches of mathematical logic as
currently practiced.

PLEASE NOTE: These general remarks are fluid, and I expect to modify and/or
amplify on them from time to time as I receive comments from people. I
welcome your comments. In particular, if you feel that I have not properly
taken into account certain work in mathematical logic, please let me know.

1. Recursion theory. As for A, there is one topic especially which is
absolutely perfect for recursion theory, and has a growing - but still
limited - following among recursion theorists. As for B, there are some
central foundational issues which are quite difficult, and may not be
accessible to techniques from recursion theory. They are lagely ignored.
They seem to require refined intellectual instincts of a sort that haven't
played any apparent role in the subarea since the initial development of
the subarea. Some of them go right to the heart of the appropriateness of
the objects being intensively studied. The later is a crucial issue for the
subarea, since most of the research concentrates on the detailed structure
of these objects, with a forty plus year massive concentrated technical
effort. There is a recent use of work from the 1960's to differential
geometry by geometers, which has not yet been assimilated by the subarea.
There appears to be no reliable discussion by recursion theorists of this
recent work.

2. Set theory. This subarea was comparatively close to foundations of
mathematics through the sixties and perhaps seventies. At that time, the
obvious technical problems and the obvious foundational issues were
naturally closely connected, and its contact with foundations of
mathematics did not require imaginative reflection to maintain. This is no
longer the case. Currently, there are some parts of the subarea that are at
least partly driven by a foundational outlook. However, this outlook has
the appearance of being rather dogmatic and restricted, and not well
exposited. I have asked a principal practitioner with a foundational
outlook to exposit some key points of this outlook on the FOM, but he has
delayed doing this on account of "the technical complexity of an accurate
exposition of these matters." There is also an unrelated ongoing project
which is quite well conceived, with plenty of points of contact with
classical analysis. But the absolutely crucial issue for the future of this
field is whether or not the set theoretic axioms play a significant role in
normal mathematical contexts - where the objects are relatively concrete -
and the extent and nature of this role. This is all the more crucial and
pressing because the general view of the mathematical community - both at
the conscious and the subconscious level - is that the set theoretic axioms
are completely irrelevant in normal mathematical contexts. In summary,
there is plenty of B to consider, but it is largely ignored. And there is
some A that is currently well under way and thriving.

3. Model theory. This area experienced a major rethinking, and by the 80's
it had transformed itself from a focus on set theoretic contexts to a focus
on standard contexts from concrete mathematics. Some of the earlier work
developed in the set theoretic contexts proved useful in the new concrete
contexts. However, there was a cost associated with this internally
generated reform. A principal driving motive for several (not all) of the
key insiders who transformed the focus of this subarea is the largely
indiscriminate minimization of all forms of mathematical research that are
not closely associated with current core mathematics - either literally or
in spirit. This minimization includes not only the preponderance of current
research in mathematical logic outisde model theory, but also the
preponderance of current research in foundations of mathematics and
foundations of computer science. On the constructive side, this serves as a
kind of antidote for some of the worst features of the other three
subareas. Having said this, we believe that one main thread in this subarea
can be productively recast as a project in the foundations of mathematics
of general intellectual interest. This recasting leads to problems of type
A that are beginning to have a following. It is expected that other parts
of the subarea can be so recast with a similarly productive outcome. As for
B, there are foundational topics even at the most rudimentary level of the
subarea that can be productively rethought from the foundational
perspective. At this time, such foundational topics are ignored because of
the predominant dismissal of foundational thinking by the practitioners.

4. Proof theory. This subarea is much larger and more varied in Europe than
in the U.S., and I need to get a more complete understanding of how it
looks over there. This subarea is certainly the closest to foundations of
mathematics, at least in terms of the perspective of the researchers.
However, it has drifted away from issues in the foundations of mathematics,
having to some extent been caught up in the non foundational culture of
mathematical logic as a whole. The proofs of some key results are in an
unattractive state, at least to outsiders, and a project is well underway
to systematically remedy this by introducing new methods that are more
robust. As for A, there seem to be many opportunities for building on the
known intimate connections with combinatorics, and bounds in core
mathematics. There are also substantial interactions with topics in
theoretical computer science, which are well underway, particularly in
Europe. As for B, there are major issues connected with appropriate
formalizations of mathematics, and the search for significant features of
actual mathematical proofs. The latter topic is underdeveloped, at least in
the U.S.

**********

In the next Central Issues posting, I will substantially expand on each of
these four paragraphs with specificity.