Math Mondays

A work in progress.

Ax-Grothendieck Theorem

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:

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:

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.