March 29, 2010

Robinson’s characteristic p principle and the Ax-Grothendieck theorem

Posted by Akhil Mathew under algebra, algebraic geometry, logic | Tags: , , , |
[3] Comments 

Model theory often provides a framework from one which one can obtain “finitary” versions of infinitary results, and vice versa.

One spectacular example is the Ax-Grothendieck theorem, which states that an injective polynomial map {P: \mathbb{C}^n \rightarrow \mathbb{C}^n} is surjective. The key idea here is that the theorem for polynomial maps of a fixed degree is a statement of first-order logic, to which the compactness theorem applies. Next, the theorem is trivial when {\mathbb{C}} is replaced by a finite field, and one then deduces it for {\overline{\mathbb{F}_p}} (and maps {P: \overline{\mathbb{F}_p} \rightarrow \overline{\mathbb{F}_p}} by an inductive limit argument. It then holds for algebraically closed fields of nonzero characteristic, because {ACF_p} is a complete theory—any first-order statement true in one algebraically closed field of characteristic {p} is true in any such field. Finally, one appeals to a famous result of Abraham Robinson that any first-order statement true in algebraically closed fields of characteristic {p>p_0} is true in algebraically closed fields of characteristic zero.

There is a discussion of this result and other proofs by Terence Tao here.

For fun, I will formally state and prove Robinson’s theorem.

Theorem 1 (A. Robinson) Let {S} be a statement in first-order logic in the language of fields (i.e., referring to the operations of addition and multiplication, and the constants {0,1}). Then {S} is true in algebraically closed fields of characteristic zero if and only if {S} is true algebraically closed fields of arbitrarily high (or sufficiently high, {p>p_0}) characteristic {p}. (more…)

 

March 9, 2010

An infinite Ramsey theorem for graphs

Posted by Akhil Mathew under combinatorics | Tags: , , , |
Leave a Comment 

I’m not yet back to full-blown quasi-daily blogging.  But I couldn’t resist this all the same. 

Edit: I am embarrassed to admit that I used the wrong terminology in the first version of this entry.  I said “discrete graph” for null graph.  Whoops.

I recently learned about a version of Ramsey’s theorem in combinatorics:

Let m \in \mathbb{N}.  There is r such that if G be a graph with more than r vertices, then G contains either a null subgraph of size m or a complete subgraph of size m.

One of the interesting applications of model theory is that this (finitary) version of Ramsey’s theorem can be proved using the simpler infinite Ramsey theorem.  There are other such applications, e.g., using the regular Nullstellensatz to prove one with bounds on the coefficients.  The idea is similar to the theorem of Robinson that a sentence of first-order logic holding in fields of characteristic zero must hold in fields of all but finitely many characteristics.   All this abstract nonsense (OK, it’s not technically category theory, but it has the same feel) deserves its own post at some point.

I don’t have time for a full post that explains all this, but I found the infinite Ramsey theorem an interesting problem in itself.

Let G be an infinite graph.  Then G contains either an infinite complete subgraph or an infinite null subgraph.

To prove this, let V_{fin} be the collection of vertices that are connected to only finitely many other vertices. 

1) If V_{fin} is infinite, we may construct a null subgraph is follows.  Choose v_1 \in V_{fin}; then choose v_2 \in V_{fin} not one of the finitely many points connected to v_1; then v_3 \in V_{fin} not connected to v_1, v_2.  The infiniteness of V_{fin} allows this process to continue indefinitely.

2) If V_{fin} is finite, we may assume wlog that for any infinite subgraph G' \subset G, the analogous set V'_{fin} is finite (or we could use the previous reasoning applied to G').   Now choose v_1 \in V - V_{fin}, which is connected to infinitely many vertices that form a subgraph G_1; then each vertex of G_1 is connected to v_1.  Also, because V^1_{fin} (the analog of V_{fin} for G_1) is finite, we can choose v_2 \in G_1 connected to infinitely many points of G_1.  Then define G_2 \subset G_1 to be the subgraph of G_1 consisting of points connected to v_2.  Repeating this process, one obtains an infinite sequence v_1, v_2, \dots such that v_n is connected to v_1, \dots, v_{n-1} (by virtue of belonging to G_n \subset G_{n-1} \subset \dots \subset G_1), which is thus a complete subgraph.