November 12, 2018

\(\newcommand{\CC}{\Bbb C} \newcommand{\FF}{\Bbb F} \newcommand{\QQ}{\Bbb Q} \newcommand{\FFx}[1]{\overline{\FF_{#1}}} \newcommand{\ACF}{\mathbf{ACF}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cT}{\mathcal{T}}\)

The Ax-Grothendieck theorem is the statement:

Ax-Grothendieck Theorem

Let \(f: \CC^n \to \CC^n\) be a polynomial map; that is, each coordinate \(f_i: \CC^n \to \CC\) is a polynomial in the \(n\) input variables. Then, if \(f\) is injective, it is surjective.

This… doesn’t seem like a particularly exciting theorem. But it has a really exciting proof.

The idea behind the proof isn’t algebraic, it isn’t topological, it’s not even geometric, it’s ~~DiGiorno~~ model-theoretic!

The spirit of the proof is as follows:

- if the theorem is false, then there is a disproof (a proof of the negation)
- this proof can be written in “first-order logic”, a particularly limited set of axioms
- because this proof is finitely long, and uses only first-order logic, it “can’t tell the difference” between \(\CC\) and \(\FFx{p}\) for large enough \(p\)
- note: \(\FFx{p}\) is the algebraic closure of the finite field \(\FF_p\)

- pick a large enough \(p\), and transfer our proof to \(\FFx{p}\); this won’t affect its structure or validity
- show that there is, in fact, no counterexample in \(\FFx{p}\)
- by contradiction, there is no disproof, and the theorem must be true

This is an… unusual proof strategy. I don’t usually think about my proofs as mathematical objects unto themselves. But that’s probably because I’m not a model theorist.

First, we’ll get the last step out of the way.

*Proof*: Let \(f: \FFx{p}^n \to \FFx{p}^n\) be injective. Pick an arbitrary target \(y_i \in \FFx{p}^n\) to hit. Let \(K \supseteq \FF_p\) be the field extension generated by the \(y_i\) and the coefficients that show up in \(f\). Since all of these generators are algebraic over \(\FF_p\), and there’s finitely many of them, \(K\) is finite. Also, since fields are closed under polynomial operations, \(f(K^n) \subseteq K^n\). But because \(f\) is injective, and \(K^n\) is finite, \(f(K^n)\) must be all of \(K^n\), i.e., there’s some input \(x_i\) such that \(f(x_i) = y_i\). Thus \(f\) is surjective.

Now for the exciting stuff.

We have to figure out a way of taking proofs over \(\CC\), and translating them into proofs over \(\FFx{p}\). This is daunting, but it’s made easier by the fact that they are both algebraically closed fields, and so they have a shared pool of axioms. Of course, they are very different in other ways: \(\CC\) is uncountable while \(\FFx{p}\) is countable, they have different characteristic, etc. We have to show that our proof manipulations aren’t affected by these differences.

Since this isn’t an intro to model theory post, I won’t be defining the basic terms. If these look unfamiliar, check out this post.

Let \(\ACF\) be the theory of algebraically closed fields. We claim that it’s first-order, and it’s *almost* complete.

This is a theory in the language of rings, which is \(\cL_{ring} = \{ +, \times, 0, 1 \}\). Our axioms are:

- the usual field axioms (these are all first-order)
- for each \(d \ge 1\), add the sentence \(\forall a_0 \forall a_1 \cdots \forall a_d \exists x \ a_0 + a_1 x + \cdots a_d x^d = 0 \land a_d \ne 0\)
- this are first-order sentences, and together, they tell us that every non-constant polynomial has a root

So \(\ACF\) is a first-order theory. It isn’t complete, of course. For example, the sentence \(1 + 1 = 0\) is true in \(\FFx{2}\), but not in \(\FFx{3}\) or \(\CC\). Turns out fields of different characteristic are… different. No surprise there.

So we define extensions of \(\ACF\), where we *do* specify the characteristic. For a prime \(p\), define \(S_p\) to be the sentence \(1 + \cdots + 1 = 0\), where there are \(p\) copies of \(1\). Then the theory of algebraically closed fields of characteristic \(p\) is \(\ACF_p = \ACF \cup \{ S_p \}\).

What about characteristic \(0\)? To force our field to have characteristic zero, we can throw in \(\lnot S_p\) for all primes \(p\): \(\ACF_0 = \ACF \cup \{ \lnot S_2, \lnot S_3, \lnot S_5, \ldots \}\). This nails down exactly the algebraically closed fields of characteristic \(0\).

We claim that \(\ACF_0\) and \(\ACF_p\) are complete theories.

If that is indeed the case, then we can prove a stronger form of the Ax-Grothendieck theorem.

Ax-Grothendieck Theorem (Stronger)

Let \(k\) be an algebraically closed field. If \(f: k^n \to k^n\) is a polynomial map, then if \(f\) is injective, it is surjective.

*Proof*: We start by breaking our claim into a number of first-order sentences. We can’t first-order define an arbitrary polynomial, so we’ll work with all polynomials of bounded degree. For a fixed \(d\), the sentence “for all polynomial maps \(f\) of degree at most \(d\), injectivity of \(f\) implies surjectivity of \(f\)” can be expressed as a first-order sentence.

First, introduce \(n \cdot (d+1)\) variables for the coefficients of \(f\). The sentence “\(f\) is injective” can be made first-order by taking \(f(x) = f(y) \implies x = y\) and expanding out the coefficients of \(f\). Likewise, “\(f\) is surjective” can be written as \(\forall z \exists x \ f(x) = z\), and expanding \(f\).

As an example, if \(n = 1, d = 2\), our sentence is:

$$ \forall a_0 \forall a_1 \forall a_2 \ (\forall x \forall y \ a_2 x^2 + a_1 x + a_0 = a_2 y^2 + a_1 y + a_0 \implies x = y) $$

$$ \implies \forall z \exists x \ a_2 x^2 + a_1 x + a_0 = z $$

Since I literally never want to write out that sentence in the general case, let’s just call it \(\phi_d\).

We’ll separately tackle the case of characteristic \(p\) and characteristic \(0\).

Let \(p\) be any prime. Because \(\ACF_p\) is complete, either there is a proof of \(\phi_d\) or a proof of \(\lnot \phi_d\). The latter is impossible; if there were such a proof, then it would show that \(\phi_d\) is false in \(\FFx{p}\), and we’ve proven before that it is true in this field. Therefore, \(\ACF_p\) entails a proof of \(\phi_d\).

Similarly, because \(\ACF_0\) is complete, either it can prove \(\phi_d\), or it can prove \(\lnot \phi_d\). Again, for the sake of contradiction, we assume the latter. Let \(P\) be a proof of \(\phi_d\) from \(\ACF_0\). Since \(P\) is finite, it can only use finitely many axioms. In particular, it can only use finitely many of the \(\lnot S_p\). So there’s some prime \(q\) such that \(\lnot S_q\) was not used in \(P\). Therefore, \(P\) is also a valid proof in \(\ACF_q\). But we already know there are no proofs of \(\lnot \phi_d\) from \(\ACF_q\), and so we’ve reached a contradiction. Therefore, there must be a proof of \(\phi_d\) from \(\ACF_0\).

Since \(\ACF_p\) can prove \(\phi_d\), and \(\ACF_0\) can prove \(\phi_d\), we know that \(\phi_d\) is true in all algebraically closed fields \(k\), no matter what the characteristic of \(k\) is. And since \(\phi_d\) is true for all \(d\), we have proved the claim for polynomials of arbitrary degree.

This proof is magical in two ways.

One is that, despite there being no homomorphisms between \(\FFx{p}\) and \(\CC\), we were able to somehow transport a claim between the two. This was possible not by looking at the structure of \(\CC\) and \(\FFx{p}\) themselves, but by using the structure of their axiomatizations. The reduction to only finitely many axioms is an example of the compactness theorem, a very useful logical principle.

The other is that we never actually made use of \(\phi_d\)! All we knew is that it was a first-order sentence, and that it was true in some model of \(\ACF_p\) for each \(p\). Generalizing this argument, we get the following principle:

Robinson's Principle

If \(\phi\) is a first-order sentence, then the following are equivalent:

- \(\ACF_p\) proves \(\phi\) for all but finitely many \(p\)
- \(\ACF_p\) proves \(\phi\) for infinitely many \(p\)
- \(\ACF_0\) proves \(\phi\)

Furthermore, the following are equivalent for \(r\) a prime or \(0\):

- \(\ACF_r\) proves \(\phi\)
- \(\phi\) is true in some algebraically closed field of characteristic \(r\)
- \(\phi\) is true in all algebraically closed fields of characteristic \(r\)

For the first claim, obviously (1) implies (2). The proof that (2) implies (3) is essentially the proof we gave above: if \(\phi\) can’t be proved from \(\ACF_0\), then \(\lnot \phi\) can. This proof can only use finitely many of the \(\lnot S_p\), and there’s infinitely many \(\ACF_p\) that prove \(\phi\), so there’s some \(p\) we can transfer the proof to and get our contradiction. The proof that (3) implies (1) is similar: if there’s a proof of \(\phi\) from \(\ACF_0\), it can be transferred to all but finitely many \(\ACF_p\).

The second claim is a direct consequence of completeness of \(\ACF_r\).

Combining these two claims gives some very powerful techniques. The way we used it is: to show something is true for all algebraically closed fields, it suffices to show it only for a single example at each prime \(p\).

At this point, there is no more spooky magic, and the rest of the article is about justifying the completeness of \(\ACF_p\) and \(\ACF_0\). Still cool though, IMO.

First, we’ll state a popular theorem in model theory:

Löwenheim–Skolem Theorem

Let \(\cT\) be a countable theory. If it has an infinite model, then for any infinite cardinal \(\kappa\), it has a model of size \(\kappa\).

Essentially, first-order logic is too limited to distinguish between different sizes of infinity; if there’s a model of one infinite size, there’s a model of all infinite sizes. The proof of this theorem is somewhat involved, and we won’t cover it here, but see here for a proof.

Using this, we can prove the Łoś–Vaught test:

Łoś–Vaught Test

Let \(\cT\) be a theory and \(\kappa\) be some infinite cardinal. We say that \(\cT\) is \(\kappa\)-categorical if there is exactly one model of \(\cT\) of size \(\kappa\), up to isomorphism.

If \(\cT\) is \(\kappa\)-categorical for some \(\kappa\), and has no finite models, then it is a complete theory.

This is unexpected, at least in my opinion. But then again, model theory isn’t my forte. Maybe there’s some intution one can use here that I don’t have.

*Proof*: If \(\cT\) isn’t complete, then there’s some \(\phi\) such that \(\cT\) proves neither \(\phi\) nor \(\lnot \phi\). By the completeness theorem, this means there’s a model \(M\) of \(\cT\) in which \(\phi\) is true, and a model \(M'\) of \(\cT\) in which \(\lnot \phi\) is true.

Since all models of \(\cT\) are infinite, both \(M\) and \(M'\) are infinite. This means that \(M\) is an infinite model of \(\cT \cup \{ \phi \}\), thus we can apply Löwenheim–Skolem to get a model \(N\) of \(\cT \cup \{ \phi \}\) which has size \(\kappa\). Likewise, we use \(M'\) to get a model \(N'\) of \(\cT \cup \{ \lnot \phi \}\) which has size \(\kappa\). But because \(\cT\) is \(\kappa\)-categorical and both \(N\) and \(N'\) are models of \(\cT\), they must be isomorphic. But because \(\phi\) is true in \(N\) and false in \(N'\), this is a contradiction.

We’d like to apply the Łoś–Vaught test to \(\ACF_p\) and \(\ACF_0\). Since all algebraically closed fields are infinite, it suffices to show that these theories are \(\kappa\)-categoral for some \(\kappa\).

*Proof*: Let \(\kappa\) be an uncountable cardinal and \(K\) be an algebraically closed field of size \(\kappa\). Let \(B\) be a transcendence basis of \(K\) over its prime subfield \(k\) (\(\FF_p\) or \(\QQ\)). A cardinality argument shows that \(\|B\| = \kappa\) (this is where the uncountability of \(\kappa\) is used; for example, \(\overline{\QQ}(t_1, \ldots, t_n)\) has transcendence degree \(n\), but cardinality \(\aleph_0\)). So, if \(K'\) is another algebraically closed field, with the same cardinality and characteristic, and we pick a transcendence basis \(B'\), it will also have cardinality \(\kappa\). The bijection between \(B\) and \(B'\) induces an isomorphism between \(k(B)\) and \(k(B')\). But since \(K\) and \(K'\) are algebraically closed, and algebraic over \(k(B) \cong k(B')\), they are algebraic closures of the same field, and are thus isomorphic!

This proves that \(\ACF_p\) and \(\ACF_0\) are \(\kappa\)-categorical for uncountable cardinals \(\kappa\). In particular, they’re \(\kappa\)-categorical for at least one infinite cardinal, and so via the Łoś–Vaught test, we conclude they are complete.