People sometimes ask me for applications of proof theory to regular mathematics. I find this question very difficult – although the associativity of function composition certainly qualifies! When people ask me for applications of Model Theory, I have a much easier time: I allude to the following theorem.

Theorem. (Ax-Grothendieck)An injective polynomial map is surjective.

Stated.

The Ax-Grothendieck theorem feels sensible to everyone who took Complex Analysis. However, they tend to find the proof, and the role of model theory, a bit mysterious. Here, I attempt to explain Ax’s proof to those who speak the language of Abstract Algebra, but not the language of Model Theory. I’ll try to cordon off the logical ingredient into a single, well-defined step. We’ll see that anyone could prove the analogue of this theorem over algebraically closed fields of characteristic . Transferring the result to characteristic zero may feel hopeless: one does not have homomorphisms between fields of different characteristic. Fortunately, Model Theory steps in to bridge this gap.

First, let’s recall the following facts:

Theorem. (Fundamental, of Algebra)Every non-constant polynomial over has a root in .

Stated.

We call fields that satisfy (their analogue of) the Fundamental Theorem of Algebra *algebraically closed fields*. Interestingly, the Fundamental Theorem of Algebra implies the case of the Ax-Grothendieck theorem.

Exercise.If a polynomial function is injective then it is surjective.

Solution.

Since is injective, it is not constant. Take an arbitrary . Proving that has a preimage w.r.t. suffices to prove that is surjective. Let’s use the Fundamental Theorem of Algebra to construct this preimage: the polynomial has a root , giving , or equivalently .

Solved.

Another important fact about the field of complex numbers:

Theorem. (Categoricity)If the algebraically closed field has characteristic zero and is bijective with , then it is isomorphic to .

Proof.

Exercise. Hint: how would you prove that two vector spaces with the same dimension are isomorphic? Similary, choose transcendence bases for and over .

Qed.

Using a clever trick, we can obtain the analogue of the Ax-Grothendieck theorem for algebraically closed fields of positive characteristic.

Theorem.Let denote the algebraic closure of . An injective polynomial map is surjective.

Proof.

Take any such polynomial map and any element . We need to show that has a preimage w.r.t. . But that’s easy!

Recall that the algebraic closure can be constructed by iteratively adjoining roots of polynomials to : thus, it can be written as the union of a chain of finite fields . One of these finite fields in the chain, say , must contain both and the coefficients of .

So our polynomial maps this finite field into itself. But injective functions that map finite sets to themselves are surjective on that set (consider this an exercise or see here)! In particular, has a preimage with respect to $f$. However, was arbitrary so the function must be surjective.

Qed.

Unfortunately, this says nothing about the case of the complex numbers. Or does it? One one hand, we feel that transfer of facts between different characteristics should be possible. On the other hand, we know that the theories of finite and infinite characteristic do not interact via homomorphisms. Logic sidesteps this problem by making the two theories interact at the level of proofs.

Here, we allude to the logical ingredients: first, compactness (related, but not identical to the topological notion). In our case, compactness asserts that if you have a countable set of laws describing the behavior of some hypothetical operations, and you can exhibit examples of operations that satisfy any finite subset of the laws, then you can also exhibit an example of operations that satisfy every law in the countable set. If you find this unintuitive, you should think of it as a logic analogue of the Erdõs-de Bruijn theorem on graph coloring. Second, the Löwenheim-Skolem theorem, which shows that you can exhibit such operations on a set bijective with .

Theorem. (Ax-Grothendieck)An injective polynomial map is surjective.

Proof.

We will construct an “ideal” algebraically closed field of characteristic zero that satisfies the Ax-Grothendieck theorem and is bijective with . By the Categoricity Theorem above, will turn out to be isomorphic to , i.e. too satisfies the Ax-Grothendieck theorem.

Consider a structure with two operations, additions and multiplication, that satisfy the laws of a field (finitely many), the laws asserting that the characteristic is zero (, countably many), the laws asserting algebraic closure (, one for each degree, countably many), and the laws saying that every polynomial map over the field that is injective is surjective (one for each degree, countably many).Any finite set of these laws contains only finitely many laws of the form : consequently, we can choose some $p > 0$ such that the addition and multiplication operations of satisfy all laws in the finite subset, along with the Ax-Grothendieck theorem. By the compactness and Löwenheim-Skolem theorems, there is a set bijective with that has addition and multiplication operations satisfying all of the laws! This means that is an algebraically closed field of characteristic zero that satisfies the Ax-Grothendieck theorem. By the Categoricity Theorem, it is isomorphic to .

Qed.