# What are some results in mathematics that have snappy proofs using model theory?

I am preparing to teach a short course on "applied model theory" at UGA this summer. To draw people in, I am looking to create a BIG LIST of results in mathematics that have nice proofs using model theory. (I do not require that model theory be the first or only proof of the result in question.)

I will begin with some examples of my own (the attribution is for the model-theoretic proof, not the result itself).

1) An injective regular map from a complex variety to itself is surjective (Ax).

2) The projection of a constructible set is constructible (Tarski).

3) Solution of Hilbert's 17th problem (Tarski?).

4) p-adic fields are "almost C_2" (Ax-Kochen).

5) "Almost" every rationally connected variety over Q_p^{unr} has a rational point (Duesler-Knecht).

6) Mordell-Lang in positive characteristic (Hrushovski).

7) Nonstandard analysis (Robinson).

[But better would be: a particular result in analysis which has a snappy nonstandard proof.]

Added: The course was given in July of 2010. So far as I am concerned, it went well. If you are interested, the notes are available at

http://www.math.uga.edu/~pete/MATH8900.html

Thanks to everyone who answered the question. I enjoyed and learned from all of the answers, even though (unsurprisingly) many of them could not be included in this introductory half-course. I am still interested in hearing about snappy applications of model theory, so further answers are most welcome.

-
The last chapter of the new edition of Courant and Robbins' "What is Mathematics?" has an appendix in which Ian Stewart gives a sketch of nonstandard analysis and spectacular applications to proofs in analysis. – Anweshi Jan 16 '10 at 6:09

## 18 Answers

Hilbert's Nullstellensatz is a consequence of the model completeness of algebraically closed fields.

Edit: I don't have a reference, but I can sketch the proof. Suppose you have some polynomial equations that don't have a solution over ${\mathbb C}$. Extend ${\mathbb C}$ by a formal solution, and then algebraically close to get a field $K$. The field $K$ obviously contains a solution, but by model completeness of algebraically closed fields, a first-order statement is true in an algebraically closed field only if it is true in every algebraically closed field. The existence of a solution to a finite set of polynomial equations is a first-order statement and ${\mathbb C}$ is algebraically closed. QED.

-
Again, could you provide a reference? Thanks. – Pete L. Clark Dec 26 '09 at 14:43
A good, brief reference is the very first pages of David Marker's notes on Model Theory of Fields. See math.uic.edu/~marker/mtf-reading.html Also, Kevin, I'm not really happy with your proof summary: as you note, it is a consequence of model completeness of ACF. But then you say that "a first-order statement is true in an algebraically closed field only if it is true in every algebraically closed field", and this property is NOT model completeness, it is simply completeness. (And moreover, ACF is model complete but not complete, ACF_p is complete though.) – Dan Petersen Dec 27 '09 at 11:43
Let me briefly explain why I like this example best (for now!). First, the application is to a theorem which is important and mainstream (especially here in Athens, where algebraic geometry is popular). Second, the model-theoretic argument seems insightful and in some ways more geometric than the standard proofs: it is essentially a generic points argument. I plan to use it in my lectures, and I'll post notes...several months from now. – Pete L. Clark Dec 28 '09 at 14:20
The conclusion of the proof sketch is incorrect as stated since the coefficients of the given polynomials are not arbitrary. However, model completeness does show that polynomials equations with coefficients in C have common solution in some extension K, then they must have a common solution in C since C is an elementary submodel of K; this gives a correct conclusion. – François G. Dorais Feb 18 '10 at 4:12
I'm a little confused. Isn't char(K)=p a first-order statement which is true of some algebraically-closed fields but not others? – Greg Muller Feb 18 '10 at 15:42

Plane geometry is decidable. That is, we have a computable algorithm that will tell us the truth or falsity of any geometrical statement in the cartesian plane.

This is a consequence of Tarski's theorem showing that the theory of real closed fields admits elimination of quantifiers. The elimination algorithm is effective and so the theory is decidable. Thus, we have a computable procedure to determine the truth of any first order statement in the structure (R,+,.,0,1,<). The point is that all the classical concepts of plane geometry, in any finite dimension, are expressible in this language.

Personally, I find the fact that plane geometry has been proven decidable to be a profound human achievement. After all, for millennia mathematicians have struggled with geometry, and we now have developed a computable algorithm that will in principle answer any question.

I admit that I have been guilty, however, of grandiose over-statement of the situation---when I taught my first logic course at UC Berkeley, after I explained the theorem some of my students proceeded to their next class, a geometry class with Charles Pugh, and a little while later he came knocking on my door, asking what I meant by telling the students "geometry is finished!". So I was embarrassed.

Of course, the algorithm is not feasible--its double exponential time. Nevertheless, the fact that there is an algorithm at all seems amazing to me. To be sure, I am even more surprised that geometers so often seem unaware of the fact that they are studying a decidable theory.

-
This is doubtless rather subjective, but I would call the completeness of geometry a theorem of meta-mathematics. The trouble is, as you point out, that it does not seem to lead to a quicker or better understanding of any particular geometric fact. – Pete L. Clark Dec 24 '09 at 18:53
I am not sure exactly how you would like to divide model theory and meta-mathematics, but surely this topic fits naturally into a discussion of elimination of quantifiers, which would seem to be an important part of model theory, no? About your second comment, alas, it is true. Nevertheless, I shall wax poetic about the significance of our having come to a great enough understanding of geometry that we have a decision procedure. – Joel David Hamkins Dec 26 '09 at 2:55
@Kevin Lin: Tarski proved that there is an algorithm to decide the truth or falsity of any first order statement in the real-closed field (R,+,l,0,<). The concepts of points, lines, planes, circles, conics, spheres, paraboloids, etc. are all expressible in this language, using the usual polynomials. Thus, we have a decision procedure for Cartesian (as opposed to Euclidean) geometry. And the algorithm handles any R^n simply by working with coordinates. – Joel David Hamkins Dec 26 '09 at 13:28
Tarski's concept of plane geometry is both more and less than Euclid's concept. More, because it includes curves other than lines and circles. Less, because it doesn't admit integer variables. A famous open problem implicit in Euclid is: for which n is the regular n-gon constructible? – John Stillwell Feb 1 '10 at 2:15
@John: I agree. Once you allow quantification over integers, then Tarski's theorem breaks down completely, and undecidability reigns again. Indeed, one get undecidability even for assertions having just a single integer quantifier, since this is enough to express the halting problem. – Joel David Hamkins Feb 1 '10 at 13:53

Not sure if this is what you are looking for but Tychonoff's theorem has a snappy two line proof in the non-standard setting once the non-standard characterization of compact is established. The non-standard characterization of compactness says that $X$ is compact if and only if every $x\in X^\*$ is infinitely close to some standard point in $X$ and infinitely close is defined in terms of the monads of the topology.

Edit: (Tychonoff) $X := \prod_{i\in I}X_i$ is compact if and only if each $X_i$ is compact.

The forward direction is easy and does not require any non-standard analysis. Simply use the projection maps.

Now suppose all the $X_i$ are compact and let $y\in X^\*$ then $y(i^*)\in (X_i)^*$. Since $X_i$ is compact there is some $x(i)\in st(y(i^\*))$ and we can take $x\in X$ to be the product of the points $x(i)$. By construction $x^*\approx y$ and this establishes the backward direction.

The above theorem along with its non-standard proof can be found in "Nonstandard Analysis" by Martin V$\ddot{a}$th on page 166 but I'm sure any other book on the subject will include a proof of the theorem using pretty much the same terminology and concepts.

Notation: $(-)^\*$ is the extension map, $st(-)$ is the standard part map, and $\approx$ is the relation defined in terms of the monads of the topology.

-
Could you give some more specifics and/or a reference? – Pete L. Clark Dec 24 '09 at 10:40
The `usual' proof via ultrafilters is very similar, so I do not think that you gain anything here by using non-standard analysis. – Carsten S Aug 11 '10 at 10:00
Also, the 'usual' proof that uses nets instead of ultrafilters is even more similar to this one... – David FernandezBreton Jun 24 '11 at 13:10
The forward direction only holds when all $X_i$ are non-empty. – Martin Brandenburg Apr 12 '13 at 13:28

You can prove Gromov's Theorem on groups of polynomial growth. See ven den Dries and Wilkie, Gromov's theorem on groups of polynomial growth and elementary logic, J Algebra, 89 (1984), 391-396.

-

You can find lots of other applications just by browsing the titles of the papers on the MODNET preprint server (follow this link and look under "Publications" on the left side of the page). For example:

1. "The monomorphism problem in free groups", by L. Ciobanu and A. Ould Houcine (in which they show it is decidable);

2. "An invitation to model-theoretic Galois theory," by A. Medvedev and Ramin Takloo-Bighash -- expository paper explaining how the Galois correspondence can be explained using model theoretic tools;

3. "On algebraic closure in pseudofinite fields," by O. Beyarslan and E. Hrushovski;

etc.

Also, there is a recent book Model Theory with Applications to Algebra and Analysis: v. 1 (LMS Lecture Note series v. 349, Cambridge, 2008) which would probably be very relevant (judging by the table of contents -- unfortunately I haven't had a chance to read it yet).

-

There are many results in Banach space theory that are proved via ultraproducts or non standard hulls, and most books on the subject contain a few. One nice one that is easy to state is that a Banach space that is uniformly homeomorphic to a Hilbert space is linearly homeomorphic to a Hilbert space.

-

Don't forget the beautiful theory of motivic integration, initiated by Maxim Kontsevich at an Orsay seminar, and developed by Jan Denef, François Loeser, Raf Cluckers, Julien Sebag and many others. The theory is becoming increasingly important.

The crucial, first paper by Denef and Loeser:

Denef & Loeser,

"Germs of arcs on singular algebraic varieties and motivic integration" (Inventiones Mathematicae 1999)

Another standard reference which should be readable - "In writing the paper we tried our best keeping it accessible to a wide audience including algebraic geometers and model theorists":

Cluckers & Loeser,

"Constructible motivic functions and motivic integration" (Inventiones Mathematicae 2008)

A very nice overview of some applications:

Loeser's slides for his ECM plenary lecture

-
@AS: I am looking for particular results with relatively elementary statements. I am epsilon familiar with the work of Denef and Loeser but am concerned that it is too advanced/technical to draw out a result which is accessible to a general graduate student audience (perhaps somewhat slanted towards algebra / algebraic geometry / number theory). Can you extract a particular result from one of these papers which meets these requirements? – Pete L. Clark Feb 1 '10 at 9:07
Hm, you could mention the recent applications to the fundamental lemma (Cluckers-Loeser-Hales). The result might be understandable (clearly the proof won't). Or you could mention the rationality result for Poincaré series (see Denef's 1984 paper - this is not motivic integration, strictly speaking, but uses quantifier elimination) or Batyrev's result that birational Calabi-Yau varieties have equal Betti numbers, a big motivation for the development of the theory. – Wanderer Feb 1 '10 at 10:50
You will find a very clear and understandable overview in Loeser's slides for his ECM plenary lecture: dma.ens.fr/~loeser/ecm_fl_final.pdf – Wanderer Feb 1 '10 at 10:51
@AS: The rationality result for Poincare series and the birational invariance of Betti numbers of Calabi-Yaus are both within the scope of understanding of portions of my target audience. Thanks very much for suggesting them. – Pete L. Clark Feb 1 '10 at 14:38

I guess this one is a bit too late for this summer, but the theory of o-minimal structures greatly simplified proofs in real algebraic and subanalytic geometry, by emphasizing concepts over nitty-gritty details (at the cost of a loss of constructivity, of course, but what can you expect?).

It is worth noting that these two structures are the ones for which the o-minimal property was known before the notion itself was formalized. Many more have been discovered since then, the most noteworthy being probably the real exponential field (Wilkie).

-

Alan Dow and others have explored the use of elementary submodels in Topology. See e.g.his introductory paper here. One application: the theorem by Arhangel'lskij that a Hausdorff Lindelöf first countable space is at most size continuum. There is a technical proof using transfinite recursion (the standard one), but also a slick one using elementary submodels (of sufficiently large countable models of ZFC).

-

This one http://arxiv.org/abs/0909.2190 is brand new. ".... For a simple linear group G, we show that a finite subset X with |X X-1 X |/ |X| bounded is close to a finite subgroup, or else to a subset of a proper algebraic subgroup of G....". I understand that people in additive combinatorics consider it useful.

-
1. For a particular result in analysis with a snappy non-standard proof, there's this proof of the Bieri-Groves Theorem on tropical amoebas. (Does this count as "analysis"? I'm not sure.)

2. There are some nice applications of model theory to [differential Galois theory],2 partly due to the fact that the complete theory of differentially closed fields of characteristic zero happens to have extremely nice model theoretic properties (it's omega-stable, hence there nice rank functions on definable sets and unique-up-to-isomorphism prime models over any set of parameters).

-
Here's a link to a paper on differential Galois theory (for some reason it wasn't letting me add the link to my answer): math.uic.edu/~marker/sev.pdf – John Goodrick Dec 24 '09 at 19:35

I like what I've heard about this 2005 GAFA paper on topological dynamics by Kechris-Pestov-Todorcevic: http://www.springerlink.com/content/hp2h78112hg31733/

It uses the Fraïssé limit construction to produce a family of topological groups with interesting universal minimal flows.

-

Hilbert's Seventeenth Problem: Let $f \in \mathbb{R}(x_1, x_2, \ldots, x_n)$ be a rational function which is positive everywhere on $\mathbb{R}^n$. Then there exist rational functions $g_1$, $g_2$, ..., $g_N$ such that $f=\sum g_i^2$.

Proof sketch: Let $K$ be the field $\mathbb{R}(x_1, x_2, \ldots, x_n)$. If $f$ is not a sum of squares, then there is a total ordering of $K$ where $f$ is negative. Let $L$ be the real closure of $K$ with respect to that ordering. Then the rational function $f$, evaluated at the point $(x_1, x_2, \ldots, x_n) \in L^n$, is negative. But the theory of real closed fields is complete, so $f$ must be negative somewhere in $\mathbb{R}^n$, contrary to hypothesis.

See Jacobson Basic Algebra II for a detailed exposition.

-
David -- yes, it's a nice application. But please look again at the question... – Pete L. Clark Feb 18 '10 at 3:45
I searched the page for "seventeenth" and "sum of squares". Are you telling me I have to read it with my eyes as well? :) – David Speyer Feb 18 '10 at 22:40

There is a proof of a p-adic birational version of Grothendieck's Section Conjecture by Jochen Koenigsmann using Model theory: http://arxiv.org/abs/math.AG/0305226 I'm not entirely sure, but I think there is no known (published?) proof of this result not using model theory.

-

Two more examples of applications:

The paper by Hrushovski arXiv:math/0406514v1 gives an application of Model Theory to a conjecture by Jacobi on difference equations.

The paper by Cluckers, Hales and Loeser arXiv:0712.0708 gives an application of Model Theory to the Fundamental Lemma in Langlands Theory.

-
1. I think the Manin-Mumford Conjecture proofs first used some methods of Model theory, before it was finally proved by Raynaud. I am not able to dig up references, though.

2. Yuri Manin and people who worked in relation with him, posted many papers on arXiv relating the problem of getting Mordell-Weil type theorems in higher dimensions, i.e., on cubic surfaces etc.. One of the references is http://arxiv.org/abs/1001.0223 ...

-

Try looking at at a nice short introduction to "modern" "applied" model theory. Perhaps it could be used to prepare to teach a short course on "applied model theory" at UGA this summer.

-

Recently Pillay and his student Nagloo tackled transcendence questions about the famous Painlevé equations. They entirely use model theory:

http://arxiv.org/pdf/1112.2916.pdf

http://arxiv.org/pdf/1209.1562.pdf

-