FOM: Central Issues in Foundations 3

[Harvey Friedman]

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

CIF1. 4:18AM 9/1/99.
CIF2. 3:25PM 9/9/99

In CIF2, I concluded by giving a brief overview of major aspects of the
four standard subareas of mathematical logic. Because of the length of #2,
I was not explicit about what I was referring to in this brief overview,
although I know that many specialists in mathematical logic knew precisely
what I was referring to in every case. My intention is to greatly elaborate
on these brief overviews with successively greater detail in this series.

Because of the length of CIF2, let me repeat brief overviews I gave there,
starting with this important note:

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.

Two definitions, which I have modified a bit from CIF2:

A. 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. Issues in foundations of mathematics that directly impinge on the
suitability of the key constructions that underly the subarea, or suggest
investigations based on new key constructions.

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.

**********

I now want to go through all of these four brief overviews and identify
more specifically what I was referring to. Subsequent postings will greatly
elaborate on all of this, and introduce new elements into the mix.

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

This is reverse mathematics. See my posting "FOM = Reverse Math?" 3:21PM
9/9/99, as well as many other postings related to Reverse Math.

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

There is Church's Thesis. In modern terms, a "proof" of Church's Thesis
asks for a clear and compelling general principle that is behind the fact
that all approahces to general computability (i.e., no resource bounds)
lead to the same classes of sets and functions.

There is the question of whether there is a "natural" recursively
enumerable set of intermediate degree. The prevailing opinion is that there
is no such natural set. Then the crucial problem is to establish that in
some way. In other words, find a relevant compelling property of r.e. sets
that holds only of r.e. sets that are either recursive or of the highest
r.e. degree. There is also the more down to earth conjecture that every
specific set or function (of integers or finite strings) referred to in
every published paper that is not specifically about recursion theory
(e.g., is in analysis, number theory, topology, geometry, algebra,
etcetera) and which is r.e., is either recursive or of the highest r.e.
degree.

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

They involve a search for extremely subtle new definitions. This emphasizes
conceptual power rather than technical virtuosity, although the technical
component is expected to be substantial. [These comments do not apply to
the "more down to earth" conjecture stated above].

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

Chuch's Thesis addresses the appropriateness of recursivity. The
naturalness/intermediate degree issue addresses the appropriateness of
focusing on the detailed structure of such things as the intermediate r.e.
degrees and the lattice of r.e. sets for 40 years.

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

Work of Nabutovsky and Weinberger.

>2. SET THEORY. This subarea was comparatively close to foundations of
>mathematics through the sixties and perhaps seventies.

First independence results from ZF and ZFC. First uses of large cardinals
below the framework of large cardinals.

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

For exmaple, independence results were limited in number as first, and so
new ones often were of a clearly different character than previous ones.

>This is no
>longer the case.

For example: with hundreds of set theoretic independence results of many
many different kinds, the relevance to foundations of mathematics of new
independence results is unclear - unless one has a major new kind of
independence result. One can attempt to make a related point about, say,
Reverse Math; i.e., with enough exact matches with formal systems, what is
gained by having more for f.o.m.? But key reasons why this point does not
apply to Reverse Math will be taken up in detail in later postings.

>Currently, there are some parts of the subarea that are at
>least partly driven by a foundational outlook.

There are a number of people who have a very strong Platonist or realist
view, and strongly feel that they are uncovering an objective reality
similar in spirit to material reality and physicists.

>However, this outlook has
>the appearance of being rather dogmatic and restricted, and not well
>exposited.

Rather dogmatic attitudes towards foundations of set theory have been
common since the late sixties and early seventies. For example, this has
discouraged foundational investigations into such things as set theory
without the axiom of choice, set theory with the axiom of constructibility,
and into ZFC itself with or without small large cardinals.

>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 a new view of what properties new axioms of set theory should
have. The old idea was "does it look and feel true and compelling, and have
lots of consequences?" The new view puts an emphasis on some formal
properties such as "generic absoluteness." This new view needs to be
critically examined by people inside and outside set theory, and needs a
clear exposition for nonexperts in set theory.

>There is also an unrelated ongoing project
>which is quite well conceived, with plenty of points of contact with
>classical analysis.

This is the area generally called "descriptive set theory", centering
around Borel sets and functions.

>But the absolutely crucial issue for the future of this
>field [set theory] 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.

A main concern of mine for over thirty years. Whoever wrote this said it
well (smile).

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

Model theory of fields, o-minimal structures, etcetera.

>Some of the earlier work
>developed in the set theoretic contexts proved useful in the new concrete
>contexts.

E.g., earlier work on stability in set theoretic contexts.

>However, there was a cost associated with this internally
>generated reform.

A cost is a neglect of foundational investigations surrounding model theory
and classical mathematical logic.

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

Another cost. At the most extreme, this group does not think that Godel's
work is among the most important mathematical events of the 20th century. I
like to draw a distinction between "mathematics" and "mathematical
thought." It makes sense to take "mathematics" to exclude, say, foundations
of mathematics. But f.o.m. is obviously part of "mathematical thought," and
as such, many people in mathematics and mathematical logic freely concede
that Godel's work is at the highest level of mathematical thought. However,
the most extreme of this group would not concede that point.

>On the constructive side, this serves as a
>kind of antidote for some of the worst features of the other three
>subareas.

Features such as the deliberate rejection of the idea that their work
should be of interest outside of the subarea of mathematical logic in which
it lies, or should have a clear motivation in terms of some clearly stated
issue or goal.

One good way of delineating the difference between the applied model
theorists' perspective and that of f.o.m., is this: The applied model
theorist uses
"interest among mathematicians" as a motivator in much the same way as
f.o.m. uses "general intellectual interest" as a motivator.

>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 is the investigation of tame structures. I.e., how much mathematics
can be cast in terms of tame structures? The notion of tame is not yet
appropriately explicated, although many important examples have been given
that everybody agrees are "tame." And there is as of yet no systematic
development of what might be called "tame foundations of mathematics." But
the ingredients are being assembled for this, through the model theoretic
investigation of clearly tame structures. And there is a close relation
between tame systems and systems which can be proved consistent using
extremely weak axioms of arithmetic. See, e.g., my posting "56:Consistency
of Algebra/Geometry" 3:01PM 8/27/99.

>This recasting leads to problems of type A that are beginning to have a
>following.

There is a preprint of a paper with C. Miller available from C. Miller in
Tex form. It scratches the surface of a potentially large investigation of
tame structures that are not necessarily o-minimal.

>It is expected that other parts
>of the subarea can be so [foundationally] recast with a similarly
>productive outcome.

Speculative, of course.

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

An example just for the moment is "A complete theory of everything:
satisfiability in the universal domain", on my website, where one looks at
structures whose domain is absolutely everything. One finds that
satisfiability/validity can be determined from merely a single unifying
principle about the nature of relations and functions on "everything." But
I hope to elaborate on many others later.

>At this time, such foundational topics are ignored because of
>the predominant dismissal of foundational thinking by the practitioners.

One could suck out the purely technical content of such a development as
referred to above, and it would correspond to a somewhat sensible ordinary
model theoretic situation. But it would lose its connections with contexts
in philosophy going back to Frege. It looks a lot more relevant and
important in the philosophical context than it does when distilled for
model theory.

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

For instance, I was recently at the 1999 Federated Logic Conference in
Trento, a computer science meeting. I found out about a whole line of
investigation connecting proof theory and term rewriting. European proof
theorists and computer science people were both involved. The result of my
trip was my posting "55:Term Rewriting/Proof Theory" 3:00PM 8/27/99.

>This subarea is certainly the closest to foundations of
>mathematics, at least in terms of the perspective of the researchers.

And at least in the U.S., a much higher percentage of the proof theorists
have full time or part time appointments in a Philosophy Department than
for the other subareas of logic.

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

There is the pressure to produce "hard" technical results, especially in
Mathematics Departments. A big preoccupation for decades has been the
project of coming up with bigger and bigger ordinal notation systems to
establish the consistency of stronger and stronger systems. Originally,
with Gentzen, there was a clear foundational point to this because of the
simplicitly of the notation system (epsilon_0) involved. As this work
progressed upward, the foundational point became less and less obvious, and
in greater need of explication. However, an unexpected foundational point
in a different direction emerged, which greatly vindicates some of this
work - its use for establishing independence results of a new kind. Yet the
more recent work on ordinal notations does not have such applications - at
least yet. There needs to be some fundamental work starting with the
original foundational points made by Gentzen's work, which gets to the
bottom of what kind of object an ordinal notation system really is - say
from the point of view of visualizable systems, or some such thing.

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

Specifically, getting rid of complicated cut elimination in favor of robust
structural or model theoretic constructions.

>As for A, there seem to be many opportunities for building on the
>known intimate connections with combinatorics, and bounds in core
>mathematics.

For example, see my postings

22:Finite Trees/Impredicativity  10/20/98  10:13AM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM

about new finite combinatorial statements about trees that require
impredicative proofs, and

56:Consistency of Algebra/Geometry  8/27/99  3:01PM

which uses proof theory, and which gives bounds for Hilbert's seventeenth
problem (more details will be posted later). The consistency proof uses cut
elimination for predicate calculus at a crucial place.

>There are also substantial interactions with topics in
>theoretical computer science, which are well underway, particularly in
>Europe.

I mentioned term rewriting above, but there are many more, including the
formalization of mathematics via automated theorem proving projects.

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

Topics reserved for future postings.