FOM: Midwest Model Theory Meeting

[Harvey Friedman]

Chris Miller ran a very successful midwest model theory meeting over this
past weekend. I was involved in a number of mathematical issues, some of
which were generated by the talks, and some of which were not.

The following is from the program announcement, and includes some of my
brief comments. And also a summary of some additional issues that were
discussed. This will be followed by some postings on some of the topics.

NOTE: My comments are not meant to be an evaluation of these talks. They
are just some thoughts that occurred to me during the meeting. The length
of comments has nothing to do with the quality of, or perceived quality of,
the talk.

SPEAKER: Eric Rosen (UIC)
TITLE: Finite model theory and the model theory of finite structures
ABSTRACT: In this talk we will discuss some aspects of the model theory
of finite structures, considering also connections between the finite
and the infinite.  We will begin with an overview of the central
areas of finite model theory, including descriptive complexity theory,
0-1 laws, and classical finite model theory, which investigate the
expressive power of logical languages, including finite variable logic
L^k, from different points of view.  We will then  discuss some recent
work developing stability theory for L^k.  Finally we look briefly at
connections with work in pure model theory which involves finite
structures, e.g., on totally categorical structures, which are
pseudofinite.

Comments: Among the problems discussed was: is there a "logic" for the
complexity class P? A nice one for NP was given. Also Baldwin told me about
the open problem: is there an axiomatization of algebraically closed fields
where there is a bound on the number of distinct variables that each axiom
has?

SPEAKER: Lou van den Dries (UIUC)
TITLE: Gromov's generalizations of Ax's theorem on injective maps
ABSTRACT: Two results from the 60's in quite different subjects are: (1)
Ax's theorem that injective endomorphisms of algebraic varieties are
surjective. (Algebraic geometry) (2) Hedlund's theorem that injective
continuous maps from the  Cantor space of biinfinite sequences of zeros
and ones to itself that commute with the shift map are surjective.
(Symbolic dynamics) Gromov's recent paper "Endomorphisms of symbolic
varieties" contains results that generalize both (1) and (2). Model
theoretic arguments play a key role in the proofs. I will give a survey
of this work and discuss some open questions.

Comments: The proofs of 1 and 2 depend on the successful approximation of
the given infinite context by a hierarchy of finite contexts, where
surjectivity is completely trivial (injective maps on finite sets are
surjective). However, according to the speakier, this Ax result also holds
for the reals (and hence real closed fields), apparently for quite
different reasons. And, according to the speaker, the proof is done for R
first via topology; there is no  "elementary" or "algebraic" proof known.
But can we rigorously ask for an "elementary" or "algebraic" proof?

One way to get at this is in terms of bounds. I.e., for injective
polynomials of degeree <= n in <= k dimensions, we can look for some
quantities. Firstly, we can ask for m(n,k) so that for every x, x has an
inverse of degree at most m(n,k) in x. Secondly, we can ask for r(n,k) so
that the statement of surjectivity is true for n-approximate algebraically
closed (or real closed) fields. Thirdly, we can ask for some combination of
these. When this is set up properly, there are roughly double exponential
bounds from general nonsense. But here we can ask for more reasonable
bounds and more precise information.

However, this may still not get at the issue of what the difference is
between "topological/analytic" proofs and "elementary" or "algebraic"
proofs. After all, in each n,k, the theorem is first order, and thus must
have an "algebraic" proof.

Another way to look at this is to look at the Pi-0-1 sentence. After all,
the theorems are Pi-0-1. It is clear that the original Ax proof is doable
in weak systems such as exponential function arithmetic (perhaps relying on
the recent fact that the usual treatment of the theory of algebraically
closed fields can be carried out in EFA). But maybe this is not all clear
in the real closed fields case because of the topology/analysis.

Still another way of looking at this is that we ought to be able to
formalize the usual "algebraic" proofs about all constructible or
semialgebraic sets of all degrees and all dimensions into a formal system
that extends the usual theory of algebraically closed fields and real
closed fields with new primitives corresponding to arbitrary constructible
or semialgebraic sets of all degrees and all dimensions. Perhaps the main
issue is an induction principle with respect to appropriately stated
properties. One has to experiment with a number of existing "algebraic"
facts about such sets. Then one would ask whether these
injective/surjective theorems are indeed provable in such a system. Of
course, a major problem might be that in a natural setup things get
restricted to the point that even the original Ax stuff for algebraically
closed fields is not doable in the system.

SPEAKER: Gerardo Lafferriere (Portland State U)
TITLE: Model theory and hybrid control systems
ABSTRACT: Hybrid systems consists of finite state machines interacting
with differential equations.  This talk will introduce general
background on hybrid systems including several models discussed in
the literature.  One of the central issues is that of
reachability: whether two states can be connected by a trajectory
of the system.  The decidability of the reachability problem has
attracted attention from researchers interested in extending
automatic verification results from finite automata to hybrid
systems. An important approach to decidability questions has been
the construction of bisimulations.  Bisimulations are finite state
quotients whose reachability properties are equivalent to those of
the original infinite state system.  A recent development in this
direction has been the identification of so-called o-minimal
hybrid systems.  Such systems admit finite bisimulations and in
several special cases provide positive answers to the decidability
problem mentioned above.

Comments: I was previously interested in appropriate mixtures of
discrete/continuous for algorithms/mahines before this talk, and it
motivated me to get more serious about it. There is an old theorem of mine
about undecidability in dynamics of semilinear maps that should be related
to work in this area. In a certain sense, I see how to get a corresponding
undecidability result in 4 dimensions. The speaker talked about a result in
3 dimensions which is somewhat more liberal in certain ways, but highly
relevant; and I obtained a lot of papers in the area starting with those
mentioned. To me, it would be very interesting to get something really
striking in 2 dimensions in the way of undecidability of reachability. This
should be doable.

SPEAKER: Michael Benedikt (Bell Labs, Naperville)
TITLE: The Topological Equivalence Problem for Spatial Relations
ABSTRACT: This talk will discuss a  kind of 'topological model
theory' where one studies first-order topological invariants of regions.
The subject was originated by Kuijpers, Paradaens, and Van Den Bussche,
who define an equivalence relation on two regions in the plane
based on whether they have the same 'first-order invariants' (I'll
explain what this means). This gives a relation that is much much weaker
than homeomorphism, but is quite difficult to characterize. In the
special case of closed relations in two space, I'll present a full
characterization of what the first-order topological invariants are, and
give a decision procedure for the corresponding equivalence relation on
regions.  In the more general case, it is unknown what the first-order
invariants are, or how to classify relations up to first-order
equivalence. I'll present some examples that illuminate the problems
involved in the general case.

Comments: This was about definable classes of definable classes. In the
case of the real field, this is classes of semialgebraic sets that are
definable over R with the ordered field primtives. Particular focus on
those definable classes of semialgebraic sets that respect the equivalence
relation of being homoemorphic by a homeomorphism of the ambient Euclidean
space.

Marker asked whether "being a variety" was definable and Benedikt asks
whether various variants of "being the graph of a C^infinity function" were
definable. I came up with a common argument that settles these in the
negative, using the O-minimality of the real field with exponentiation. But
apparently my argument is closely related to earlier arguments of Wilkie
and others in other contexts.

Benedikt also asked if "containing a bi-infinite line" is definable using
only R,+,-,< among the sets definable using only R,+,-,<. I think I solved
this problem too, but in the affirmative - and will post shortly on it,
making sure it is correct.

These Marker and Benedikt questions do not the involve equivalence relation
that occupied the bulk of the talk.

SPEAKER: Deirdre Haskell (Holy Cross)
TITLE: Grothendieck rings of definable sets.
ABSTRACT: The Grothendieck ring of the collection of definable sets of a
structure is defined analogously to the Grothendieck group in algebraic
topology. I willdiscuss the definition, compare it with Euler
characteristic, and calculate some examples, in particular, the
Grothendieck ring of the $p$-adics.

Comments: Outside my range. Wish it weren't.

SPEAKER: Rami Grossberg (CMU)
TITLE: Classification theory for non-elementary classes.
ABSTRACT: In the last twenty years much progress was made
toward extending stability theory to classes of models that
do not permit a first-order axiomatization.
  Very interesting examples are that of the logic $L_{\omega_1,\omega}$
and abstract elementary classes.  The current stage of development
of this theory is comparable to that of stability theory
in the early eighties.
  In this talk I will attempt to survey some of the achievements and
will discuss some of the fundamental concepts of this relatively
unknown branch of pure model theory.

Comments: The Los conjecture, solved by Morley for countable theories, lead
to very unexpected developments in model theory and ultimately applied
model theory. The obvious analog of the Los conjecture for infinitary
languages is wide open, and the speaker suggests that this should lead to
very unexpected developments as well. However, some in the audience think
that infinitary languages are much different and much less potentially
effective in applications. I pointed out that infinitary languages were
very productive in the discussion of Abelian group theory - Barwise and
Eklof, Advances in Mathematical Logic (now Annals of Pure and Applied
Logic), 1970. The speaker asserted that the deeper aspects of the model
theory of infinitary logic are not reflected in those applications. There
was interesting extended discussion of the speaker's recent interaction
with Shelah, and of the desirability of the use of transparencies in
lectures.

SPEAKER: Patrick Speissegger (UW Madision & U Toronto)
TITLE: O-minimal open cores
ABSTRACT:  Are there expansions of the real line that are not o-minimal
but "close to being o-minimal"?  For a given expansion M of the real
line, we can make sense of this question by considering the reduct of M
generated by all open sets that are definable in M, called the open core
of M.  If the open core of M is o-minimal, then the interior and the
closure of any definable set has finitely many connected components.  We
will look at various conditions on M, similar in nature to the
o-minimality condition but less restrictive, that guarantee that the
open core of M is o-minimal even if M itself is not.

Comments: The focus was on the sufficient condition that "every definable
set is finite or uncountable." The speaker mentioned that I had earlier
developed a technique that constructs lots of expansions of the real field
with this intruiging property.

INFORMAL DISUCSSIONS.

1. van den Dries asks: can algebraically closed fields be axiomatized by
finitely many schemes? I pointed out that the real closed fields can be.
Use the least upper bound axiom scheme.

2. In this connection, I mentioned an old result of mine that I used to
obtain an independence result from Peano Arithmetic without the axiom S0
not= 0. Namely, that this theory has a very interesting model: the field of
complex numbers.

3. Also in this connection, the open question: is every field of
characteristic 0 that has every definable set (in one dimension) either
finite or cofinite, algebraically closed? This is known to be true in
finite characteristic.

4. I talked to van den Dries and Marker a lot about a "model theoretic
interpretation of reverse mathematics." Here the idea is to recast the RM
program as of the classfication of mathematics in terms of model theoretic
interpretability. I will say much more about this in later postings, and
will discuss it in my paper for the Boulder meeting. Excerpts of that paper
will also appear in postings.

5. Marker asked me what the most strictly mathematical way I know of
getting up to, say, ACA_0 in the reverse mathematics context, once one has
gotten going. I answered with a statement about infinite series. I am
checking details, and will post - the idea is that you can sum any series
of real numbers given by a rational function with real coefficients,
provided the partial sums of absolute values is bounded.

6. In a discussion with van den Dries about the dividing line between tame
and wild mathematics, the topic of how Robinson's Q interprets so many
theories came up.

THEOREM. Let T be a countable theory in a countable language. T is
interpretable in Q if and only if for every finite fragment S of T, there
exists n = n(S) such that EFA (exponential function arithmetic) proves that
S has no inconsistency in a typical Hilbert style proof system in which all
formulas are propositional combinations of formulas each of which have at
most n quantifiers. In particular, T is interpretable in Q if and only if
every finite fragement of T is interpretable in Q.

COROLLARY.  RCF (real closed fields) and ACF (algebraically closed fields)
are interpretable in Q.

It is remarked in a footnote in Hajek, Pudlak, Metamathematics of
First-Order Arithmetic, Springer, 1998, page 366, that Q is interpretable
in the following system:

a) extensionality.
b) x union {y} exists.

COROLLARY. Q and a) plus b) are mutually interpretable.

What about

a) extensionality
b) x union {y} exists
c) separation for all formulas.

THEOREM. PA and a),b),c) are mutually interpretable.

7. Baldwin commented that a lot of nice proofs in mathematics avoid
induction and make good use of intuition. The example he gave was
1+2+3...+n = n(n+1)/2. You can draw a staircase and notice that you have
exactly half of the rectangle of points of width n and height n+1. Voila!
No induction. Baldwin's question: how do we formalize this common approach
to mathematics.

I commented that indeed most mathematicians avoid induction in favor of
other techniques. In fact, Rota was fond of saying that if one has to
resort to induction, then one does not have a good proof.

I proposed a way of dealing with this during the conversation with Baldwin,
but now I don't like it so much after looking into it in detail.

I like the following approach better. One may call it the set theoretic
interpretation of identities, and more generally, inequalities.

Let's look at this identity

1+2+3...+n = n(n+1)/2.

again. We can rewrite this as 2(1+2+...+n) = n(n+1). Now any polynomial P
of several variables with positive integer coefficients can be viewed as
the cardinality of a set built up by disjoint unions and Cartesian products
from finite sets whose cardinalities are nonnegative values of the
variables.

Also, any sum like 1+2+...+n can be viewed also as the cardinality of a set
built up with disjoint unions. More generally, we may have a sum given by a
polynomial with positive integer coefficients indexed over a k dimensional
rectangle of integral points. Then we can form the k+1 dimensional set
whose cardinality (of integer point elements) is nicely the same as the
sum.

We can ask for the equation to be strongly true in the sense that there is
a "simple" bijection between the two sets. Obviously the sum formulation is
more general, so that's what we assume is on both sides of the equation.

We can ask, for example, that for all values of the paramters, the
bijection be semialgebraic, where it is a bijection restricted to integer
points.

So this is a serious move in the direction of defining what an "algebraic"
proof of such an identity is, as distinguished from a proof by induction.