FOM: Urbana Thoughts

[Harvey Friedman]

The year 2000 meeting of the ASL held in Urbana, June 3 - 7, 2000, was
exciting, enjoyable, and thought provoking. There a number a thoughts I had
during the meeting, only a fraction of which came to the surface.

I did distribute an extended abstract on Boolean Relation Theory at the
meeting. It is the same as posting number 88, 10:01AM, 6/9/00.

SAM BUSS.

Buss talked about the future of proof theory and complexity. He mentioned a
lot of interesting things, and cannot be expected to mention everything
that is interesting.

There is one major omission here. And that is the use of proof theory to
establish independence results. (At least I don't remember this being
mentioned). This is an obvious high point of proof theory that provides
clear applications that everyone in logic and many people outside logic
appreciate. lt is obvious to me that this will be a major topic in the
coming century.

Also, there has recently been considerable work on the connections between
proof theory and term rewriting. This will also expand in the coming
century.

ANAND PILLAY.

Anand presented a picture of model theory that centered on

definability

and

interpretability.

Anand also correctly emphasized tame systems. So he means

interpretability between tame systems.

I wanted to mention that a lot of FOM, and in particular, reverse
mathematics, concerns

interpretability between non tame systems.

There is incredible structure here. The FOM/reverse math people are at
least as excited about interpretability as the Pillay model theorists.

In particular, there appears to be a fundamental linearity of formal
systems (above the tame level) under interpretability that occur in nature.
And because of reverse mathematics, basically there appears to be a
fundamental linearity under interpretability of mathematical statements
occurring in nature.

Anand also said that a key point about tame systems is that they avoid the
Godel phenomena.

This is only largely true, and the senses in which this is false is quite
interesting.

For example, let us consider RCF = real closed fields. The set of true
sentences in RCF is decidable, but is very very rich from the point of view
of computational complexity. Instead of proving that the set of true
sentences in RCF is complete r.e. (it isn't), one proves that it is
complete for exponential space. Actually, this is not quite known, and
probably not quite right. It is currently trapped between nondeterministic
exponential time and exponential space. Nevertheless, there is plenty of
Godel phenomenon here in full force. Also, with respect to issues about
lengths of proofs. I.e., much of the usual Godel phenomena one expects.

Of course, obviously there is no sentence in RCF which is independent of
ZFC. However, I conjecture that there is an interesting and natural
sentence in RCF (first order abbreviateions allowed) such that any proof or
refutation  in ZFC takes more than the number of electrons in the universe,
even with abbreviations, but there is a proof or refutation in ZFC + large
cardinals which can be done in 5 pages.

I should also add that Boolean relation theory can be focused to talk only
about definable multivariate functions and definable sets in familiar
structures that have QE. One runs right into Mahlo cardinals of finite
order for, e.g., Presburger Arithmetic augmented with base 2 exponentiation
(details not quite finished). I call this tame Boolean relation theory -
even though one quickly runs right up against large cardinals.

In private discussions, Anand insisted that the phrase

applied model theory

is completely inappropriate. In fact, according to Anand, anyone using this
phrase is openly showing gross ignorance of model theory.

Since I use this phrase on a continuing basis, I naturally got interested
in exploring this matter further.

When I think of pure model theory, I think of most work on infinitary
languages, generalized quantifiers, two and several cardinal theorems,
decidability/undecidability of various theories, including computational
complexity of such theories, etcetera. Any kind of model theory that isn't
specifically aimed at getting information about structures familiar to
mathematicians that is in a form that is readily digestible to
mathematicians.

But Pillay regarded most - perhaps all - of these topics as lying outside
of model theory! In particular, infinitary languages and generalized
quantifiers is descriptive set theory, according to Pillay!!

There are also various issues that come up in what I call model theory that
are motivated by philosophical considerations. For instance, logic where
the domain is required to be everything - this goes under the name "a
complete theory of everything" which is a talk I sometimes give for
philosophers. And various investigations concerning why first order
predicate calculus has such a preferred status. There are also preservation
theorems, which I suspect can be revived with new really interesting
theorems. It is obvious that these topics should be called model theory.
But their aims are so different than what I call applied model theory -
that the name pure model theory seems appropriate. At least, saying that
they are not model theory at all makes no sense to me.

There has been a lot of success with applied model theory in recent years,
and it has attracted a lot of new researchers and changed the research of
many model theorists. But this does not mean that other aspects of the
subject no longer exist or are automatically uninteresting.

The pure/applied distinction did not begin with model theory and did not
end with model theory. It makes sense almost everywhere.

JOHN BALDWIN.

John made a remark to the effect that Boolean relation theory was part of
the intrinsic developement of logic and not part of the extrinsic
development of logic.

Judging from the context in which it was said, I assume John was already
taken the position that Boolean relation theory was not going to fulfill
one of its advertised goals - to provide new concrete mathematics that will
be accepted by mathematicians as normal mathematics that is a permanent,
fundamental part of the mathematical landscape. In particular, that it will
be sufficient to seriously join the issue of the status of large cardinals
for the general mathematical community.

John may well come to this mistaken conclusion simply because I introduced
Boolean relation theory - and not the mathematicians. But the real test is
whether mathematicians accept Boolean relation theory as something they are
pleased to know about. Whether things in Boolean relation theory are things
that mathematicians would have wanted to discover themselves. After all,
every important piece of new mathematics is new at one time - and
frequently not anticipated at all.

Nevertheless I am surprised at the remark since any good mathematician can
see that the thin set theorem meets this criterion - at least the critical
mass of serious mathematicians that is completely accepting of all
functions from Z into Z. And I have very carefully gone over every single
step that needs to be taken to go from the thin set theorem to the further
developments in Boolean relation theory that are tied up with large
cardinals - with several very famous mathematicians (and some not so famous
but very well informed and knowledgeable mathematicians). They all agree
that each such step is completely natural and inevitable.

There are certainly some famous mathematicians who are particularly fussy
about what mathematics they admit is interesting. Atiyah completely
rejected any statement involving arbitrary functions from Z into Z as
abnormal. So in particular, the thinness theorem, for Atiyah, is abnormal.
This was not the view of the other famous mathematicians I talked to so
far.

Nevertheless, I am taking Atiyah's position very seriously. It is morally
certain that piecewise linear functions on Z can be used instead in Boolean
relation theory (everything with integer coefficients, and the finitely
many pieces all defined by finitely many linear inequalities). So I asked
Atiyah about piecewise linear functions on Z. He said that they were better
than arbitrary maps, but still disliked them. He still considered them
abnormal.

I am trying to see just what kinds of functions I can use in Boolean
relation theory to get to large cardinals. The max of two polynomials with
integer coefficients is enough. I can probably do even better. I don't know
what Atiyah will think of the max of two polynomials with integer
coefficients. I will eventually be able to deal sensibly with only finite
functions and finite sets, which will put an end to this kind of objection
anyways.

I did tell Anand that Atiyah was not very accepting of these piecewise
linear functions on Z, let alone all Presburger functions. Anand did not
say anything, but did not look pleased. After all, this is Atiyah, and
these are functions definable in one of the great tame structures.

PILLAY again.

Anand frequently says that it is important for logicians to incorporate
mathematics outside logic in their work - and particularly cutting edge
mathematics, and not just classical mathematics.

I certainly agree with part of this remark. But whether classical
mathematics or cutting edge mathematics is appropriate depends on what you
are trying to accomplish.

If one is trying to make direct applications and connections, then what
Anand says makes some real sense. However, if one is trying to join the
issue of new axioms for mathematics, then one should - in fact one must (in
my opinion) start at the most fundamental level possible and build things
up from there. Preferably build things up starting at the high school
level. This is what I am doing. Later, with the benefit of experience, one
can perhaps profitably venture into more modern contexts.