# Ax-Grothendieck Theorem


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:

1. $$\ACF_p$$ proves $$\phi$$ for all but finitely many $$p$$
2. $$\ACF_p$$ proves $$\phi$$ for infinitely many $$p$$
3. $$\ACF_0$$ proves $$\phi$$

Furthermore, the following are equivalent for $$r$$ a prime or $$0$$:

1. $$\ACF_r$$ proves $$\phi$$
2. $$\phi$$ is true in some algebraically closed field of characteristic $$r$$
3. $$\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.