Wednesday, November 11, 2015

When Baire meets Krasner

Here is a well-but-ought-to-be-better known theorem.

Theorem. — Let $\ell$ be a prime number and let $G$ be a compact subgroup of $\mathop{\rm GL}_d(\overline{\mathbf Q_\ell})$. Then there exists a finite extension $E$ of $\mathbf Q_\ell$ such that $G$ is contained in $\mathop{\rm GL}_d(E)$.

Before explaining its proof, let us recall why such a theorem can be of any interest at all. The keyword here is Galois representations.

It is now a well-established fact that linear representations are an extremly useful tool to study groups. This is standard for finite groups, for which complex linear representations appear at one point or another of graduate studies, and its topological version is even more classical for the abelian groups $\mathbf R/\mathbf Z$ (Fourier series) and $\mathbf R$ (Fourier integrals). On the other hand, some groups are extremly difficult to grasp while their representations are ubiquitous, namely the absolute Galois groups $G_K=\operatorname{Gal}(\overline K/K)$ of fields $K$.

With the notable exception of real closed fields, these groups are  infinite and have a natural (profinite) topology with open subgroups the groups $\operatorname{Gal}(\overline K/L)$, where $L$ is a finite extension of $K$ lying in $\overline K$. It is therefore important to study their continuous linear representations. Complex representations are important but since $G_K$ is totally discontinuous, their image is always finite. Therefore, $\ell$-adic representations, namely continuous morphisms from $G_K$ to $\mathop{\rm GL}_d(\mathbf Q_\ell)$, are more important. Here $\mathbf Q_\ell$ is the field of $\ell$-adic numbers.

Their use goes back to Weil's proof of the Riemann hypothesis for curves over finite fields, via the action on $\ell^\infty$-division points of its Jacobian variety. Here $\ell$ is a prime different from the characteristic of the ground field. More generally, every Abelian variety $A$ over a field $K$ of characteristic $\neq\ell$ gives rise to a Tate module $T_\ell(A)$ which is a free $\mathbf Z_\ell$-module of rank $d=2\dim(A)$, endowed with a continuous action $\rho_{A,\ell}$ of  $G_K$. Taking a basis of $T_\ell(A)$, one thus has a continuous morphism $G_K\to \mathop{\rm GL}_d(\mathbf Z_\ell)$, and, embedding $\mathbf Z_\ell$ in the field of $\ell$-adic numbers,  a continuous morphism $G_K\to\mathop{\rm GL}_d(\mathbf Q_\ell)$. Even more generally, one can consider the $\ell$-adic étale cohomology of algebraic varieties over $K$.

For various reasons, such as the need to diagonalize additional group actions, one can be led to consider similar representations where $\mathbf Q_\ell$ is replaced by a finite extension of $\mathbf Q_\ell$, or even by the algebraic closure $\overline{\mathbf Q_\ell}$. Since $G_K$ is a compact topological groups, its image by a continuous representation $\rho\colon G_K\to\mathop{\rm GL}_d(\overline{\mathbf Q_\ell}$ is a compact subgroup of $\mathop{\rm GL}_d(\overline{\mathbf Q_\ell}$ to which the above theorem applies.

This being said for the motivation, one proof (attributed to Warren Sinnott)  is given by Keith Conrad in his short note, Compact subgroups of ${\rm GL}_n(\overline{\mathbf Q}_p)$. In fact, while browsing at his large set of excellent expository notes,  I fell on that one and felt urged to write this blog post.

The following proof had been explained to me by Jean-Benoît Bost almost exactly 20 years ago. I believe that it ought to be much more widely known.

It relies on the Baire category theorem and on Krasner's lemma.

Lemma 1 (essentially Baire). — Let $G$ be a compact topological group and let $(G_n)$ be an increasing sequence of closed subgroups of $G$ such that $\bigcup G_n=G$. There exists an integer $n$ such that $G_n=G$.

Proof. Since $G$ is compact Hausdorff, it satisfies the Baire category theorem and there exists an integer $m$ such that $G_m$ contains a non-empty open subset $V$. For every $g\in V$, then $V\cdot g^{-1}$ is an open neighborhood of identity contained in $G_m$. This shows that $G_n$ is open in $G$. Since $G$ is compact, it has finitely many cosets $g_iG_m$ modulo $G_m$; there exists an integer $n\geq m$ such that $g_i\in G_n$ for every $i$, hence $G=G_n$. QED.

Lemma 2 (essentially Krasner). — For every integer $d$, the set of all extensions of $\mathbf Q_\ell$ of degree $d$, contained in $\overline{\mathbf Q_\ell}$, is finite.

Proof. Every finite extension of $\mathbf Q_\ell$ has a primitive element whose minimal polynomial can be taken monic and with coefficients in $\mathbf Z_\ell$; its degree is the degree of the polynomial. On the other hand, Krasner's lemma asserts that for every such irreducible polynomial $P$, there exist a real number $c_P$ for every monic polynomial $Q$ such that the coefficients of $Q-P$ have absolute values $<c_P$, then $Q$ has a root in the field $E_P=\mathbf Q_\ell[T]/(P)$. By compactness of $\mathbf Z_\ell$, the set of all finite subextensions of given degree of $\overline{\mathbf Q_\ell}$ is finite. QED.

Let us now give the proof of the theorem. Let $(E_n)$ be a increasing sequence of finite subextensions of $\overline{\mathbf Q_\ell}$ such that $\overline{\mathbf Q_\ell}=\bigcup_n E_n$ (lemma 2; take for $E_n$ the subfield generated by $E_{n-1}$ and all the subextensions of degree $n$ of $\overline{\mathbf Q_\ell}$). Then $G_n=G\cap \mathop{\rm GL}_d(E_n)$ is a closed subgroup of $G$, and $G$ is the increasing union of all $G_n$. By lemma 1, there exists an integer $n$ such that $G_n=G$. QED.

Sunday, October 25, 2015

On Lp-spaces, when 0<p<1, convex sets and linear forms

While the theory of normed vector spaces is now extensively taught at the undergraduate level, the more general theory of topological vector spaces usually does not reach the curriculum. There may be good reasons for that, and here is an example, taken from a paper of Mahlon M. Day, The spaces $L^p$ with $0<p<1$ (Bull. Amer. Math. Soc. 46 (1940), 816–823), of which I learned from a nice analysis blurb by Keith Conrad which has almost the same title.

For simplicity, I consider here the simple case when the measured space is $[0;1]$, with the Lebesgue measure, and $p=1/2$. Let $E$ be the set of measurable real valued functions $f$ on the interval $[0;1]$ such that $\int_0^1|f(t)|^{1/2}dt<+\infty$, where we identify two functions which coincide almost everywhere. For $f,g\in E$, let us define $d(f,g)=\int_0^1 \mathopen|f(t)-g(t) \mathclose|^{1/2}dt$.

Lemma. —
  1. The set $E$ is a vector subspace of the space of all measurable functions (modulo coincidence almost everywhere).
  2. The mapping $d$ is a distance on $E$.
  3. With respect to the topology defined by $d$, the addition of $E$ and the scalar multiplication are continuous, so that $E$ is a topological vector space.

Proof. — We will use the following basic inequality: For $u,v\in\mathbf R$, one has $\mathopen|u+v\mathclose|^{1/2}\leq |u|^{1/2}+|v|^{1/2}$; it can be shown by squaring both sides of the inequality and using the usual triangular inequality. Let $f,g\in E$; taking $u=f(t)$ and $v=g(t)$, and integrating the inequality, we obtain that $f+g\in E$. It is clear that $af\in E$ for $a\in\mathbf R$ and $f\in E$. This proves that $E$ is a vector subspace of the space of measurable functions. For $f,g\in E$, one has $f-g\in E$, so that $d(f,g)$ is finite. Let then $f,g,h\in E$; taking $u=f(t)-g(t)$ and $v=g(t)-h(t)$, and integrating this inequality for $t\in[0;1]$, we then obtain the triangular inequality $d(f,h)\leq d(f,g)+d(g,h)$ for $d$. Moreover, if $d(f,g)=0$, then $f=g$ almost everywhere, hence $f=g$ by definition of $E$. This proves that $d$ is a distance on $E$. Let us now show that $E$ is a topological vector space with respect to the topology defined by $d$. Let $f,g\in E$. For $f',g'\in E$, one then has $d(f'+g',f+g)=\int_0^1\mathopen|(f-f')+(g-g')\mathclose|^{1/2}\leq d(f,f')+d(g,g')$. This proves that addition is continuous on $E$. Similarly, let $a\in \mathbf R$ and $f\in E$. For $b\in\mathbf R$ and $g\in E$, one has $d(af,bg)\leq d(af,bf)+d(bf,bg)\leq \mathopen|b-a\mathclose|^{1/2} d(f,0)+|b|^{1/2}d(f,g)$. This implies that scalar multiplication is continuous. QED.

The following theorem shows one unusual feature of this topological vector space.

Theorem. — One has $E^*=0$: every continuous linear form on $E$ vanishes identically.

Proof. — Let $\phi$ be a non-zero continuous linear form on $E$. Let $f\in E$ be such that $\phi(f)\neq 0$; we may assume that $\phi(f)\geq 1$. For $s\in[0,1]$, let $g_s\colon[0;1]\to\mathbf R$ be the function defined by $g_s(t)=0$ for $0\leq t\leq s$ and $g_s(t)=1$ for $s< t\leq 1$. When $s$ goes from $0$ to $1$, $d(g_s f,0)$ goes from $d(f,0)$ to $0$. Consequently, there exists $s$ such that $d(g_s f,0)=d(f,0)/2$. Then $d((1-g_s)f,0)=\int_0^s |f(t)|^{1/2}dt=\int_0^1|f(t)|^{1/2}dt-\int_s^1|f(t)|^{1/2}dt=d(f,0)-d(g_sf,0)=d(f,0)/2$ as well. Moreover the equality $1=\phi(f)=\phi(g_sf)+\phi((1-g_s)f)=0$ shows that either $\phi(g_sf)\geq1/2$ or $\phi((1-g_s)f)\geq 1/2$. Set $f'=2g_s f$ in the first case, and $f'=2(1-g_s)f$ in the latter; one has $\phi(f')\geq 1$ and $d(f',0)=d(f,0)/\sqrt 2$. Iterating, we obtain a sequence $(f^{(n)})$ of elements of $E$ which converges to $0$ but such that $\phi(f^{(n)})\geq 1$ for every $n$, contradicting the continuity of $\phi$. QED.

On the other hand, we may believe to remember the Hahn-Banach theorem according to which, for every non-zero function $f\in E$, there exists a continuous linear form $\phi\in E^*$ such that $\phi(f)=1$. Obviously, the previous theorem seems to violate the Hahn-Banach theorem.
So why is this not so? Precisely because the Hahn-Banach theorem makes the fundamental hypothesis that the topological vector space be a normed vector space or, more generally, a locally convex vector space, which means that $0$ admits a basis of convex neighborhoods. According to the following proposition, this is far from being so.

Proposition. — $E$ is the only non-empty convex open subset of $E$.

Proof. — Let $V$ be a non-empty convex open subset of $E$. Up to an affine transformation, in order prove that $V=E$, we may assume that $0\in V$ and that $V$ contains the unit ball of center $0$. We first show that $V$ is unbounded. For every $n\geq 1$, we split the interval $[0,1]$ in $n$ intervals $[(k-1)/n,k/n]$, for $1\leq k\leq n$, with characteristic functions $g_k$. One has $d(n^2g_k,0)=1$ for every $k$, hence $n^2 g_k\in V$; moreover, $1=\sum_{k=1}^n g_k$, so that $n=\frac 1n \sum_{k=1}^n n^2 g_k$ belongs to $V$. More generally, given $f\in E$ and $n\geq 1$, we split the interval $[0;1]$ into $n$ successive intervals, with characteristic functions $g_k$, such that $d(fg_k,0)=d(f,0)/n$ for every $k$; one also has $f=\sum fg_k$. Then $d(nfg_k,0)=\sqrt n d(fg_k,0)=1/\sqrt n\leq 1$, hence $n fg_k\in V$ and the relation $f=\frac1n \sum nf g_k$ shows that $f\in V$. QED.

When $(X,\mu)$ is a measured space and $p$ is a real number such that $0<p<1$, the space $L^p(X,\mu)$ has similar properties. For this, I refer the interested reader to the above cited paper of Day and to Conrad's note.

Saturday, June 6, 2015

Model theory and algebraic geometry, 4 — Elimination of imaginaries

The fourth post of this series is devoted to an important concept of model theory, that of elimination of imaginaries. The statement of Scanlon's theorem will appear in a subsequent one.

Definition. — Let $T$ be a theory in a language $L$. One says that $T$ eliminates imaginaries (resp. weakly eliminates imaginaries) if for every model $M$ and every formula $f(x;a)$ with parameters $a\in M^p$, there exists a formula $g(x;y)$ such that $\{ b\in M^q\;;\; \forall x, f(x;a)\Leftrightarrow g(x;b)\}$ is a singleton (resp. is a non-empty finite set).

What does this mean? View the formula $f(x;y)$ as defining a family of definable subsets, where $f(x;a)$ is the slice given by the choice of parameters $a$. It may happen that many fibers are equal. The property of elimination of imaginaries asserts that one can define the same family of definable subsets via another formula $g(x;y)$, with different parameters, so that every definable set in the original family appears once and only once. For the case of weak elimination, every definable set of the initial family appears only finitely times.

There is an alternative, Galois theoretic style, description: a theory $T$ (weakly) eliminates imaginaries if and only if, for every formula $f(x;a)$ with parameters in a model $M$, there exists a finite subset $B\subset M$ such that for every elementary extension $N$ of $M$ and every automorphism $\sigma$ of $N$, then $\sigma$ preserves the formula (meaning $f(x;a)\leftrightarrow f(\sigma(x);a)$, or, equivalently, $\sigma$ leaves globally invariant the definable subset of $N^n$ defined by the formula $f(x;a)$) if and only if  $\sigma$ leaves $B$ pointwise (resp. globally) invariant. One direction is obvious: take for $B$ the coordinates of the elements of the singleton (resp. the finite set) given by applying the definition. For the converse, elementary extensions must enter the picture because some models are too small to possess the necessary automorphisms that should exist; under “saturation hypotheses”, the model $M$ will witness them already.

This property is related to the possibility of representing equivalence classes modulo a definable equivalence relation. Namely, let $M$ be a model and let $E$ be an equivalence relation on $M^n$ whose graph is a definable subset of $M^n\times M^n$. Assume that the theory $T$ eliminates imaginaries and allows to define two distinct elements. Then there exists a definable map $f_E\colon M^n\to M^m$ such that for every $y,z\in M^n$, $y \mathrel{E} z$ if and only if $f_E(y)=f_E(z)$. In particular, the quotient set $M^n/E$ is represented by the image of the definable map $f_E$.

Conversely, let $f(x;a)$ be a formula with parameters $a\in M^p$ and consider the equivalence relation $E$ on $M^p$ given by $yEz$ if and only if $\forall x,\ f(x;y)\Leftrightarrow f(x;z)$. Its graph is obviously definable. Assume that there exists a definable map $f_E\colon M^p\to M^q$ such that $yEz$ if and only if $f_E(y)=f_E(z)$. Then an automorphism of (an elementary extension of) $M$ will fix the definable set defined by $f(x;a)$ if and only if it fixes $f_E(a)$, so that one has elimination of imaginaries.

Theorem (Poizat). — The theory of algebraically closed fields eliminates imaginaries.

This is more or less equivalent to Weil's theorem on the field of definition of a variety. It is my feeling, however, that this property is under-estimated in algebraic geometry. Indeed, it is closely related to a theorem of Rosenlicht that asserts that given a variety $X$ and an algebraic group $G$ acting on $X$, there exists a dense $G$-invariant open subset $U$ of $X$ such that a geometric quotient $U/G$ exists in the sense of Mumford's Geometric Invariant Theory.

Examples. — Let $K$ be an algebraically closed field.

a) Let $X$ be a Zariski closed subset of $K^n$ and let $G$ be a finite group of (regular) automorphisms of $X$. Let us consider the formula $f(x;y)=\bigwedge_{g\in G} (x=g\cdot y)$ which asserts that $x$ belongs to the orbit of $G$ under the given action, so that $f(x;y)$ parameterizes $G$-orbits. Since $G$ is finite, weak elimination of imaginaries is a trivial matter, but elimination of imaginaries is possible. Let indeed $A$ be the affine algebra of $X$; this is a $K$-algebra of finite type with an action of $G$ and the algebra $A^G$ is finitely generated. Consequently, there exists a Zariski closed subset $Y$ of some $K^m$ and a polynomial morphism $\phi\colon K^n\to K^m$ such that, for every $y,z\in X$, $\phi(y)=\phi(z)$ if and only if there exists $g\in G$ such that $z=g\cdot y$. Consequently, for $a\in X$, $b=\phi(a)$ is the only element such that the formula $f(x;a)$ be equivalent to the formula $g(x;b)=(b\in Y) \wedge (\exists y\in X)(\phi(y)=b) \wedge f(x;y))$.

The simplest instance would be the symmetric group $G=\mathfrak S_n$ acting on $K^n$ by permutation of coordinates. Then $G$-orbits are unordered $n$-tuples of elements of $K$, and it is a both trivial and fundamental fact that the orbit of $(x_1,\dots,x_n)$ is faithfully represented by the first $n$ elementary symmetric functions of $(x_1,\dots,x_n)$, equivalently, by the coefficients of the polynomial $\prod_{j=1}^n (T-x_j)$.

b) Let $X=K^{n^2}$ be the set of all $n\times n$ matrices under which the group $G=\mathop{\rm GL}(n,K)$ acts by conjugation. The Jordan decomposition gives a partition of $X$ into constructible sets, stable under the action of $G$, and on each of them, there exists a regular representation of the equivalence classes. For example, the set $U$ of all matrices with pairwise distinct eigenvalues is Zariski open — it is defined by the non-vanishing of the discriminant of the characteristic polynomial — and on this set $U$, the conjugacy class of a matrix is represented by its characteristic polynomial.

Theorem. — An o-minimal theory eliminates imaginaries. More precisely any surjective definable map $f\colon X\to Y$ between definable sets admits a definable section.

This follows from the fact that one can define a canonical point in every non-empty definable set. By induction on dimension, it suffices to prove this for a subset $A$ of the line. Then, let $J_A$ be the leftmost interval of $A$ (if the formula $f$ defines $f$, then $J_A$ is defined by the formula $y\leq \rightarrow f(y)$); let $u$ and $v$ be the “endpoints” of $J_A$; if $u=-\infty$ and $v=+\infty$, set $x_A=0$; if $u=-\infty$ and $v<\infty$, set $x_A=v-1$; if $-\infty<u\leq v<+\infty$, set $x_A=(u+v)/2$. It is easy to write down a formula that expresses $x_A$ in terms of a formula for $A$. Consequently, in a family $A_t\subset M$ of non-empty definable sets, the function $t\mapsto x_{A_t}$ is definable.

Theorem (Poizat). — The theory of differentially closed fields eliminates imaginaries in the language $\{+,-,\cdot,0,1,\partial\}$.

Examples. — Let $K$ be an algebraically closed differential field. Let $X$ be an algebraic variety with the action of an algebraic group $G$, all defined over the field of constants $C=K^\partial$. We can then endow $X(K)$ with the equivalence relation given by $x\sim y$ if and only if there exists $g\in G(C)$ such that $y=g\cdot x$. The following three special instances of elimination of imaginaries in DCF are classical results of function theory:

a) If $X=\mathbf A^1$ is the affine line and $G=\mathbf G_a$ is the additive group acting by translation, then the map $\partial\colon x\mapsto \partial (x)$ gives a bijection from $X(K)/G(C)$ to $K$. Indeed, two elements $x,y$ of $K$ differ by the addition of a constant element if and if $\partial(x)=\partial(y)$. (Moreover, every element of $K$ has a primitive.)

b) Let $X=\mathbf A^1\setminus\{0\}$ be the affine line minus the origin and let $G=\mathbf G_m$ be the multiplicative group acting by multiplication. Then the logarithmic derivative $\partial\log\colon x\mapsto \partial(x)/x$ gives a bijection from $X(K)/G(C)=K^\times/C^\times$ to $K$ — two elements $x,y$ of $K^\times$ differ by multiplication by a constant if and only if $\partial(x)/x=\partial(y)/y$, and every element of $K$ is a logarithmic derivative.

c) Let $X=\mathbf P^1$ be the projective line endowed with the action of the group $G=\operatorname{\rm PGL}(2)$. Then two points $x,y\in X(K)$ differ by an action of $G(C)$ if and only if their Schwarzian derivatives are equal, where the Schwarzian derivative of $x\in K$ is defined by
\[ S(x) = \partial\big(\partial^2 (x)/\partial (x)\big) -\frac12 \big(\partial^2(x)/\partial(x)\big). \]

Monday, May 11, 2015

Model theory and algebraic geometry, 3 — Real closed fields and o-minimality

In this third post devoted to some interactions between model theory and algebraic geometry, we describe the concept of o-minimality and the o-minimal complex analysis of Peterzil and Starchenko.

1. Real closed fields and the theorem of Tarski-Seidenberg

To begin with, we work in the language $L_{\mathrm{or}}$ of ordered rings which is the language of rings $L_{\mathrm r}=\{+,-,\cdot,0,1\}$ enlarged with an order relation $\leq$.

Let us recall the definition of a real closed field: this is an field $K$ endowed with an ordering which is compatible with the field laws (the sum of positive elements is positive and the product of positive elements is positive) which satisfies the intermediate value theorem for polynomials: for every polynomial $P\in K[T]$, any pair $(a,b)$ of elements of $K$ such that $a<b$, $P(a)<0$ and $P(b)>0$, there exists $c\in K$ such that $P(c)=0$ and $a<c<b$. Observe that this property can be expressed by a sequence of first-order formulas, one for each degree.

The field $\mathbf R$ of real numbers is real closed, but there are many other. For example, the field of formal Puiseux series with real coefficients is also real closed.

A theorem of Artin-Schreier asserts that a field $K$ is real closed if and only if $\sqrt{-1}\not\in K$ and $K(\sqrt{-1})$ is an algebraic closure of $K$. This is also equialent to the fact that “the” algebraic closure of $K$ is a finite non-trivial extension of $K$. While the algebraic notion adapted to the language of rings is that of an algebraically closed field, the notion of a real closed field is the one which is adapted to the language of ordered rings. In model theoretic terms, the theory of real closed fields is the model companion of the theory of ordered fields.

The analogue of the theorem of Chevalley is the classical theorem of Tarski-Seidenberg:

Theorem (Tarski-Seidenberg). — The theory of real closed fields eliminates quantifiers in the language of ordered rings.

There is a very classical example of this theorem, namely, the resolution of polynomial equation of degree 2. Indeed, in a real closed field, every positive element has a square root (if $a>0$, then the polynomial $T^2-a$ is negative at $0$ and positive at $\max(a,1)$, so that it admits a positive root). The usual algebraic computation thus shows that the formula $\exists x, x^2+ax+b=0$ is equivalent to the formula $a^2-4b\geq 0$.

Corollary 1. — If $M$ is a real closed field and $A$ is a subset of $A$, then $\mathop{\rm Def}(M^n,A)$ is the set of all semi-algebraic subsets of $M$ defined by polynomials with coefficients in $A$.

Corollary 2. — If $M$ is a real closed field, the definable subsets of $M$ are the finite unions of intervals (open, closed or half-open, $\mathopen]a;b\mathclose[$, $\mathopen]a;b]$, $[\mathopen a;b\mathclose[$, $[a;b]$, possibly unbounded, possibly reduced to singletons).

2. O-minimality

The seemingly innocuous property stated in corollary 2 leads to a definition which is surprisingly important and powerful.

Definition. — Let $T$ be the theory of a real closed field $M$ in an expansion $L$ of the language of ordered rings. One says that $T$ is o-minimal if the definable subsets of $M$ are the finite unions of intervals.

It is a non-trivial result that the o-minimality is indeed a property of the theory $T$, and not a property of the model $M$: if it holds, then for every elementary extension $N$ of $M$, the definable subsets of $N$ still are finite unions of intervals.

By the theorem of Tarski-Seidenberg, the theory of real closed fields is o-minimal. The discovery of more complicated o-minimal theories is a remarkable fact from the 80s.

Example. — Let $L_{\mathrm{an},\mathrm{exp}}$ be the language obtained by adjoining to the language $L_{\mathrm{or}}$ of ordered rings symbols of functions $\exp$ and $f$, for every real analytic function $f\colon [0;1]^n\to\mathbf R$. The field of real numbers is viewed as a structure for this language by interpreting $\exp$ as the exponential function from $\mathbf R$ to $\mathbf R$, and every function symbol $f$ as the function from $\mathbf R^n$ to $\mathbf R$ that maps $x$ to $f(x)$ if $x\in [0;1]^n$, and to $0$ otherwise. The theory (denoted $\mathbf R_{\mathrm{an},\mathrm{exp}})$) of $\mathbf R$ in this language is o-minimal.

This is a thorem of van den Dries and Miller; the case of $L_{\mathrm{an}}$ (without the exponential function) had been established Denef and van den Dries, while the case of $L_{\mathrm{exp}}$ is due to Wilkie.

To give a non-example, let us consider the language obtained by adjoining a symbol $\sin$ and view $\mathbf R$ as a structure for this language, the symbol $\sin$ being interpreted as the sine function from $\mathbf R$ to $\mathbf R$. Then the theory of $\mathbf R$ in this language is not o-minimal. Indeed, the set $2\pi\mathbf Z$ is definable by the formula $\sin(x)=0$, but $2\pi\mathbf Z$ has infinitely many connected components, so is not a finite union of intervals.

One motivation for o-minimality is that it realizes (part of) Grothendieck quest towards tame topology as described in his Esquisse d'un programme. Indeed, sets which are definable in an o-minimal structure have many tameness properties:
  • The interior, the closure, the boundary of a definable set is definable.
  • Every definable set is homeomorphic to (the topological realization) of a simplicial complex
  • Every definable set has a celllular decomposition. Precisely, let us call a cell of $\mathbf R^{n+1}$ any subset $C$ of the following form: one is given a definable subset $A$ of $\mathbf R^n$ and definable functions $f,g\colon A\to\mathbf R$ such that $f(x)<g(x)$ for every $x\in A$, and the set $C$ is defined by the condition $x\in A$, and by one of the conditions $t<f(x)$, or $t=f(x)$, or $f(x)<t<g(x)$, or $t>f(x)$.  Then for every finite family $(B_i)$ of definable subsets of $\mathbf R^{n+1}$, there is a finite partition of $\mathbf R^{n+1}$ into cells such that every $B_i$ is a union of cells.
  • Every definable function is piecewise smooth.
  • Definable continuous functions are definably piecewise trivial (theorem of Hardt): for every function $f\colon X\to Y$ between definable sets which is definable and continuous, there is a finite partition $(Y_i)$ of $Y$ into definable subsets such that the map $f_i\colon f^{-1}(Y_i)\to Y_i$ deduced from $f$ by restriction is isomorphic to a projection $Y_i\times S_i\to Y_i$.

Recently, o-minimality has had spectacular and fantastic applications via the approach of Pila-Zannier to the conjecture of Pink, leading to new proofs of the Manin-Mumford conjecture (Pila-Zannier), and to proofs of the André-Oort conjecture (Pila, Pila-Tsimerman, Klingler-Ullmo-Yafaev), and, more recently, to partial results towards the conjecture of Pink (Gao, Habegger-Pila,...). However, this is not the goal of that post, so let me refer the interested reader to Tom Scanlon's Bourbaki talk on that topic.

3. O-minimal complex analysis

The standard identification of the field $\mathbf C$ of complex numbers with $\mathbf R^2$ (associating with a complex number its real and imaginary parts) allows to talk of complex valued functions (on a subset of $\mathbf C^n$) which are definable in a given language. In a remarkable series of papers, Peterzil and Starchenko have shown that holomorphic functions which are definable in an o-minimal structure possess very rigid properties. Let us quote some of their theorems.

So we fix an expansion of the language $L_{\mathrm{or}}$ of which the field $\mathbf R$ is a structure whose theory is o-minimal. By “definable”, we mean definable in that language. The typical language considered in the applications here is the language $L_{\mathrm{an},\mathrm{exp}}$.

Theorem. — Let $A$ be a finite subset of $\mathbf C$ and let $f\colon \mathbf C\setminus A\to \mathbf C$ be a holomorphic function. If $f$ is definable, then it is a rational function.

Theorem. — Let $V\subset\mathbf C^n$ be a closed analytic subset. If $V$ is definable, then $V$ is algebraic.

Corollary (Theorem of Chow). — Let $V\subset\mathbf P^n(\mathbf C)$ be a closed analytic subset. Then $V$ is algebraic.

Indeed, working on the standard charts of $\mathbf P^n(\mathbf C)$, we see that $V$ is locally definable by analytic functions. By compactness of $\mathbf P^n(\mathbf C)$, it is thus definable in the language $L_{\mathrm{an}}$. Since the theory of $\mathbf R$ in this language is o-minimal, the corollary is a consequence of the previous theorem.

Let us finally give an important example. Let $X$ be an bounded symmetric domain. This means that $X$ is a bounded open subset of $\mathbf C^n$ such that for every point $p\in X$, there exists a biholomorphic involution $f\colon X\to X$ such that $p$ is an isolated fixed point of $f$. This implies that $X$ is a homogeneous space $G/K$ under a semisimple Lie group $G$ which acts by holomorphisms, and $K$ is a maximal compact subgroup of $G$. Moreover, $X$ has a canonical Kähler metric which is invariant under $G$.

The most classical example is given by the Poincaré upper half-plane on which $\mathrm{PGL}(2,\mathbf R)$ acts by homographies; of course, the upper half-plane is not bounded, but is biholomorphic to the open unit disk.

A more sophisticated example is given by the Siegel upper half-plane or, rather, its bounded version. That is, $X$ is the set of $n\times n$ symmetric complex matrices $Z$ such that $\mathrm I_n-Z^* Z$ is positive definite. It is a homogeneous space for the symplectic group $\mathrm{Sp}(2n,\mathbf R)$; the fixator of $Z=0$ is the unitary group $U(n)$.

Let now $\Gamma$ be an arithmetic subgroup of $\mathrm{Sp}(2n,\mathbf R)$; for example, let us take $\Gamma$ be a subgroup of finite index of $\mathrm{Sp}(2n,\mathbf Z)$. Then the quotient $S=X/\Gamma$ admits a structure of an analytic set and the projection $p\colon X\to S$ is an analytic map. If $\Gamma$ is “small enough” (torsion free, say), then $S$ is even complex manifold manifold, and $p$ is a covering. An important and difficult theorem of Baily-Borel asserts that $S$ is an algebraic variety.

In fact, it is classical in this context that there exist Siegel sets, which are explicit subsets $F$ of $X$ such that $\Gamma\cdot F=X$ and such that the set of $\gamma\in\Gamma$ such that $\gamma\cdot F\cap F\neq\emptyset$ is finite. So Siegel sets are almost fundamental domains. An important remark is that they are semi-algebraic, that is, definable in the language of ordered rings. For example in the upper half-plane, one may take $F$ to be the set of all $z\in\mathbf C$ such that $-\frac12\leq \Re(z)\leq \frac12$ and $\Im(z)\geq \sqrt 3/2$. One may even take “fundamental sets” (which are fundamental domains up to something of empty interior) such as the one defined by the inequalities $-\frac12\leq \Re(z)\leq\frac12$ and $\lvert z\rvert \geq1$.

Peterzil and Starchenko have proved that there restriction to $F$ of the projection $p$ is definable in the language $L_{\mathrm{an},\mathrm{exp}}$. An immediate consequence is that $S$ is definable in this language, hence is algebraic.

These results have been generalized by Klinger, Ullmo and Yafaev to any bounded symmetric domain. This is an important technical part of their proof of the hyperbolic Ax-Lindemann conjecture.

Saturday, May 2, 2015

Model theory and algebraic geometry, 2 — Definable sets, types; quantifier elimination

This is the second post in a series of 4 devoted to the exposition of interactions between model theory and algebraic geometry. In the first one, I explained the notions of language, structures and theories, with examples taken from algebra. Here, I shall discuss the notion of definable set, of types, as well as basic results from dimension theory ($\omega$-stability).

So we fix a theory $T$ in a language $L$. A definable set is defined, in a given model $M$ of $T$, by a formula. More precisely, we consider definable sets in cartesian powers $M^n$ of the model $M$, which can be defined by a formula in $n$ free variables with parameters in some subset $A$ of $M$. By definition, such a formula is a formula of the form $\phi(x;a)$, where $\phi(x;y)$ is a formula in $n+m$ free variables, split into two groups $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_m)$ and $a=(a_1,\dots,a_m)\in A^m$ is an $m$-tuple of parameters; the formula $\phi(x;y)$ can have quantifiers and bounded variables too. Given such a formula, we define a subset $[\phi(x;a)]$ of $M^n$ by $\{ x\in M^n\mid \phi(x;a)\}$. We write $\mathrm{Def}(M^n;A)$ for the set of all subsets of $M^n$ which are definable with parameters in $A$.

Let us give examples, where $L$ is the language of rings and $T$ is the theory $\mathrm{ACF}$ of algebraically closed fields:
  • $V_1=\{x\mid x\neq 0 \}\subset M $, given by the formula “$x\neq 0$” with 1 variable and $0$ parameter;
  • $V_2=\{x\mid \exists y, 2xy=1\} \subset M $, given by the formula “$\exists y, 2xy=1$” with 1 free variable $x$, and one bounded variable $y$;
  • $V_3=\{(x,y)\mid x^2+\sqrt 2 y^2=\pi \}\subset \mathbf C^2$, where the model $\mathbf C$ is the field of complex numbers, $\phi((x,y),(a,b))$ is the formula $x^2+ay^2=b$ in 4 free variables, and the parameters are given by $(a,b)=(\sqrt 2,\pi)$.
Theorem (Chevalley). — Let $L$ be the language of rings, $T=\mathrm{ACF}$ and $M$ be an algebraically closed field; let $A$ be a subset of $M$. The set $\mathrm{Def}(M^n;A)$ is the smallest boolean algebra of subsets of $M^n$ which contains all subsets of $M^n$ of the form $[P(x;a)]$ where $P$ is a polynomial in $n+m$ variables with coefficients in $\mathbf Z$ and $a=(a_1,\dots,a_m)$ is an $m$-tuple of elements of $A$. In other words, a subsets of $M^n$ is definable with parameters in $A$ if and only if it is constructible with parameters in $A$.

The reason behind this theorem is the following set-theoretic interpretation of quantifiers and logical connectors. Precisely, if $\phi$ is a formula in $n+m+p$ variables, and $a\in A^p$, the definable subset $[\exists y \phi(x,y,a)]$ of $M^n$ coincides with the image of the definable subset $[\phi(x,y;a)]$ of $M^{n+m}$ under the projection $p_x \colon M^{n+m}\to M^n$. Similarly, if $\phi(x)$ and $\psi(x)$ are two formulas in $n$ free variables, then the definable subset $[\phi(x)\wedge\psi(x)]$ is the union of the definable subsets $[\phi(x)]$ and $[\psi(x)]$. And if $\phi(x)$ is a formula in $n$ variables, then the definable subset $[\neg\phi(x)]$ is the complement in $M^n$ of the definable subset $[\phi(x)]$.

For example, the subset $V_2=[\exists y, 2xy=1]$ defined above can also be defined by $M\setminus [2x=0]$.

One says that the theory ACF admits elimination of quantifiers: modulo the axioms of algebraically closed fields, every formula of the language $L$ is equivalent to a formula without quantifiers.

An important consequence of this property is that for every extension $M\hookrightarrow M'$ of models of ACF, the theory of $M'$ is equal to the theory of $M$—one says that every extension of models is elementary.

Let $p$ be either $0$ or a prime number. Observe that every algebraically closed field of characteristic $p$ is an extension of $\overline{\mathbf Q}$ if $p=0$, or of $\overline{\mathbf F_p}$ if $p$ is a prime number. As a consequence, for every characteristic $p\geq0$, the theory $\mathrm{ACF}_p$ of algebraically closed fields of characteristic $p$ (defined by the axioms of $\mathrm{ACF}$, and  the axiom $1+1+\dots+1=0$ that the characteristic is $p$ if $p$ is a prime number, or the infinite list of axioms that assert that the characteristic is $\neq \ell$, if $p=0$) is complete: this list of axioms determines everything that can be said about algebraically closed fields of characteristic $p$.

Definition. — Let $a\in M^n$ and let $A$ be a subset of $M$. The type of $a$ (with parameters in $A$) is the set $\mathrm{tp}(a/A)$ of all formulas $\phi(x;b)$ in $n$ free variables with parameters in $A$ such that $\phi(a;b)$ holds in the model $M$.

Definition. — Let $A$ be a subset of $M$. For every integer $n\geq 0$, the set $S_n(A)$ of types (with parameters in $A$) is the set of all types $\mathrm{tp}(a/A)$, where $N$ is an extension of $M$ which is a model of $T$ and $a\in N^n$. One then says that this type is realized in $N$.

Gödel's completeness theorem allows us to give an alternative description of $S_n(A)$. Namely, let $p$ be a set of formulas in $n$ free variables and parameters in $A$ which contains the diagram of $A$ (that is, all formulas which involve only elements of $A$ and are true in $M$). Assume that $p$ is consistent (there exists a model $N$ which is an extension of $M$ and and element $a\in M^n$ such that $\phi(a)$ holds in $N$ for every $\phi\in p$) and maximal (for every formula $\phi\not\in p$, then for every model $N$ and every $a\in N^n$ such that $p\subset \mathrm{tp}(a/A)$, then $\phi(a)$ does not hold). Then $p\in S_n(A)$.

For every formula $\phi\in L(A)$ in $n$ free variables and parameters in $A$, let $V_\phi$ be the set of types $p\in S_n(A)$ such that $\phi\in p$. Then the subsets $V_\phi$ of $S_n(A)$ consistute a basis of open sets for a natural topology on $S_n(A)$.

Theorem. — The topological space $S_n(A)$ is compact and totally discontinuous.

Let us detail the case of the theory ACF in the langage of rings. I claim that if $K$ is a field, then $S_n(K)$ is homeomorphic to the spectrum $\mathop{\rm Spec}(K[T_1,\dots,T_n])$ endowed with its constructible topology. Concretely, for every algebraically closed extension $M$ of $K$ and every $a\in M^n$, the homeomorphism $j$ maps $\mathrm{tp}(a/K)$ to the prime ideal $\mathfrak p_a$ consisting of all polynomials $P\in K[T_1,\dots,T_n]$ such that $P(a)=0$.

A type $p=\mathrm{tp}(a/K)$ is isolated if and only if the prime ideal $\mathfrak p_a$ is maximal. Consequently, if $n=1$, there is exactly one non-isolated type in $S_1(K)$, corresponding to the generic point of the spectrum $\mathop{\rm Spec}(K[T])$.

As for any compact topological space, a space of types can be studied via its Cantor-Bendixson analysis, which is a decreasing sequence of subspaces, indexed by ordinals, defined by transfinite induction. First of all, for every topological space $X$, one denotes by $D(X)$ the set of all non-isolated points of $X$. One then defines $X_0=X$, $X_{\alpha}=D(X_\beta)$ if $\alpha=\beta+1$ is a successor-ordinal, and $X_\alpha=\bigcap_{\beta<\alpha} X_\beta$ if $\alpha$ is a limit-ordinal. For $x\in X$, the Cantor-Bendixson rank of $x$ is defined by $r_{CB}(x)=\alpha$ if $x\in X_\alpha$ and $x\not\in X_\beta$ for $\beta>\alpha$, and $r_{CB}(x)=\infty$ if $x\in X_\alpha$ for every ordinal $\alpha$. The set of points of infinite rank is the largest perfect subset of $X$.

Let us return to the example of the theory ACF. If a type $p\in S_n(K)$ corresponds to a prime ideal $\mathfrak p=j(p)$ of $\mathop{\rm Spec}(K[T_1,\dots,T_n])$, its Cantor-Bendixson rank is the Zariski dimension of $V(I)$. More generally, if $F$ is a constructible subset of $\mathop{\rm Spec}(K[T_1,\dots,T_n])$, then $r_{CB}(F)$ is the Zariski-dimension of the Zariski-closure of $F$. Moreover, the points of maximal Cantor-Bendixson rank correspond to the generic points of the irreducible components of maximal dimension; in particular, there are only finitely many of them.

Definition. — One says that a theory $T$ is $\omega$-stable if for every finite or countable set of parameters $A$, the space of 1-types $S_1(A)$ is finite or countable.

The theory ACF is $\omega$-stable. Indeed, if $K$ is the field generated by $A$, then $K[T]$ being
a countable noetherian ring, it has only countably many prime ideals.

Since any non-empty perfect set is uncountable, one has the following lemma.

Lemma. — Let $T$ be an $\omega$-stable theory and let $M$ be a model of $T$. Then the Cantor-Bendixson rank of every type $x\in S_n(M)$ is finite.

Let us assume that $T$ is $\omega$-stable and let $F$ be a closed subset of $S_n(M)$. Then $r_{CB}(F)=\sup \{ r_{CB}(x)\,;\, x\in F\}$ is finite, and the set of points $x\in F$ such that $r_{CB}(x)=r_{CB}(F)$ is finite and non-empty.

This example gives a strong indication that the model theory approach may be extremly fruitful for the study of algebraic theories whose geometry is not as well developed than algebraic geometry.

Thursday, April 23, 2015

Model theory and algebraic geometry, 1 — Structures, languages, theories, models

Last november, I had been invited to lecture at the GAGC conference on the use of model theoretic methods in algebraic geometry. In the last two decades, important results of “general mathematics” have been proved using sophisticated techniques, see for example Hrushovski's proofs of the Manin-Mumford and of the Mordell-Lang conjecture over function fields, or Chatzidakis-Hrushovski's proof of a descent result in algebraic dynamics (generalizing a theorem of Néron for abelian varieties), or Hrushovski-Loeser's approach to the topology of Berkovich spaces, or Medvedev-Scanlon's results on invariant varieties in polynomial dynamics, or Hrushovski's generalization of the Lang-Weil estimates, or the applications to the André-Oort conjecture (by Pila and others) of a theorem of Pila-Wilkie in o-minimal geometry... All these wonderful results were however too complicated to be discussed from scratch in this series of lectures and I decided to discuss a beautiful paper of Scanlon that “explains” why coverings from analytic geometry lead to algebraic differential equations.
There will be 4 posts:
  1. Structures, languages, theories, models (this one)
  2. Definable sets, types, quantifier elimination
  3. Real closed fields and o-minimality
  4. Elimination of imaginaries
Model theory — a branch of mathematical logic — has two aspects:
  • The first one, that one could name “pure”, studies mathematical theories as mathematical objects. It introduced important concepts, such as quantifier elimination, elimination of imaginaries, types and their dimensions, stability theory, Zariski geometries, and provides a rough classification of mathematical theories.
  • The second one is “applied”: it studies classical mathematical theories using these tools. It may be for algebraic theories, such as fields, differential fields, valued fields, ordered groups or fields, difference fields, etc., that it works the best, and for theories which are primitive enough so that they escape indecidability à la Gödel.
 Let us begin with an empirical observation; classical mathematical theories feature:
  • sets (which may be receptacles for groups, rings, fields, modules, etc.);
  • functions and relations between those sets (composition laws, order relations, equality);
  • certain axioms which are well-formed formulas using these functions, these relations, basic logical symbols ($\forall$, $\exists$, $\vee$, $\wedge$, $\neg$) or their variants ($\Rightarrow$, $\Leftrightarrow$, $\exists!$, etc.).
Model theory (to be precise, first-order model theory) introduces the concepts of a language (the letters and symbols that allow to express a mathematical theory), of a theory (sets of formulas in a given language, using a fixed infinite supply of variables), of a structure (sets, functions and relations that allow to interpret all formulas in the language) and finally of a model of a theory (a structure where the formulas of the given theory are interpreted as true). The theory of a structure is the set of all formulas which are interpreted as true. A morphism of structures is a map which is compatible with all the given relations.

Let us give three examples from algebra: groups, fields, differential fields

a) Groups

The language of groups has one symbol $\cdot$ which represents a binary law. Consequently, a structure for this language is just a set $S$ together with a binary law $S\times S\to S$. In this language, one can axiomatize groups using two axioms:
  • Associativity: $\forall x \forall y \forall z \quad x\cdot (y\cdot z)= (x\cdot y)\cdot z$
  • Existence of a neutral element and of inverses: $\exists e\forall x \exists y \quad (x\cdot e=e\cdot x \wedge  x\cdot y=y\cdot x=e)$.
Observe that in writing these formulas, we allow ourselves the usual shortcuts to which we are used as mathematicians. In fact, the foundations of model theory require to spend a few pages to discuss how formulas should be written, with or without parentheses, that they can be unambiguously read, etc.

However, it may be more useful to study groups in a language with 3 symbols $\cdot,e,i$, where $\cdot$ represents the binary law, $e$ the neutral element and $i$ the inversion. Then a structure is a set together with a binary law, a distinguished element and a self-map; in particular, what is a structure depends on the language. In this new language, groups are axiomatized with three axioms:
  • Associativity as above;
  • Neutral element: $\forall x \quad x\cdot e=e\cdot x=x$;
  • Inverse: $\forall x\quad x\cdot i(x)=i(x)\cdot x=e$.
The two theories of groups are essentially equivalent: one can translates any formula of the first language into the second, and conversely. Indeed, if a formula of the second language involves the symbols $e$, it suffices to copy $\exists e x\cdot e=e\cdot x$ in front of it; and if a formula involves $i(x)$, it suffices to add $\exists y$ in front of it, as well as the requirement $x\cdot y=y\cdot x=e$, and to replace $i(x)$ by $y$. Since the neutral element and the inverse law of a group are unambiguously defined by the composition law, this shows that the new formula is equivalent, albeit longer and less practical, to the initial one.

The possibility of interpreting a theory in a language in a second language is a very important tool in mathematical logic.

b) Rings

The language used to study rings has 5 symbols: $+,-,0,1,\cdot$. In this language, structures are just sets with three binary laws and two distinguished elements. One can of course axiomatize rings, using the well-known formulas that express that the law $+$ is associative and commutative, that $0$ is a neutral element and that $-$ gives subtraction, that the law $\cdot$ is associative and commutative with $1$ as a neutral element, and that the multiplication $\cdot$ distributes over addition.

Adding the axioms $\forall x (x\neq 0 \Rightarrow \exists y \quad xy=1)$ and $1\neq 0$ gives rise to fields.

That a field has characteristic 2, say, is axiomatized by the formula $1+1=0$, that it has characteristic 3 is axiomatized by the formula $1+1+1=0$, etc. That a field has characteristic 0 is axiomatized by an infinite list of axiom, one for each prime number $p$, saying that $1+1+\cdots+1\neq 0$ (with $p$ symbols $1$ on the left). We will see below why fields of characteristic 0 must be axiomatized by infinitely  axioms.

That a field is algebraically closed means that every monic polynomial has a root. To express this property, one needs to write down all possible polynomials. However, the language of rings does not give us access to integers, nor to sets of polynomials. Consequently, we must write down an infinite list of axioms, one for each positive integer $n$: $\forall x_1\forall x_2\cdots \forall x_n \exists y \quad y^n+x_1 y^{n-1}+\cdots+x_{n-1}y+x_n=0$. Here $y^m$ is an abbreviation for the product $y\cdot y \cdots y$ of $m$ factors equal to $y$.

As we will see, the language of rings and the theory ACF of algebraically closed fields is well suited to study algebraic geometry.

c) Differential fields

A differential ring/field is a ring/field $A$ endowed with a derivation $\partial\colon A\to A$, that is, with an additive map satisfying the Leibniz relation $\partial(ab)=a\partial(b)+b\partial(a)$. They can be naturally axiomatized in the language of rings augmented with a symbol $\partial$.

There is a notion of a differentially closed field, analogous to the notion of an algebraically closed field, but encompassing differential equations. A differential field is differentially closed if any differential equation which has a solution in some differential extension already has a solution. This property is analogous to the consequence of Hilbert's Nullstellensatz according to which a field is algebraically closed if any system of polynomial equations which has a solution in an extension already has a solution. At least in characteristic zero, Robinson showed that their theory DCF$_0$ can be axiomatized by various families of axioms. For example, the one devised by Blum asserts the existence of an element $x$ such that $P(x)=0$ and $Q(x)\neq0$, for every pair $(P,Q)$ of non-zero differential polynomials in one indeterminate such that the order of $Q$ is strictly smaller than the order of $P$. This study requires the development of important and difficult results in differential algebra due to Ritt and Seidenberg.

At this level, there are two important basic theorems to mention: Gödel completeness theorem, and the theorems of Löwenheim-Skolem.

Completeness theorem (Gödel). — Let $T$ be a theory in a language $L$. Assume that every finite subset $S$ of $T$ admits a model. Then $T$ admits a model.

There are two classical proof of this theorem.

The first one uses ultraproducts and consists in choosing a model $M_S$ for every finite subset $S$ of $T$. Let then $\mathcal U$ be a non-principal ultrafilter on the set of finite subsets of $T$ and let $M$ be the ultraproduct of the family of models $(M_S)$. It inherits functions and relations from those of the models $M_S$, so that it is a structure in the language $L$. Moreover, one deduces from the definition of an ultrafilter that for every axiom $\alpha$ of $T$, the structure $M$ satisfies the axiom $\alpha$. Consequently, $M$ is a model of $T$.

A second proof, due to Henkin, is more syntactical. It considers the set of all terms in the language $L$ (formulas without logical connectors), together with an equivalence relation that equates two terms for which some axiom says that they are equal, and with symbols representing objets of which an axiom affirms the existence. The quotient set modulo the equivalence relation is a model. In essence, this proof is very close to the construction of a free group as words.

It is important to obseve that the proof of this theorem uses the existence of non-principal ultraproducts, which is a weak form of the axiom of choice. In fact, as in all classical mathematics, the axiom of choice — and set theory in general — is used in model theory to establish theorems. That does not prevent logicians to study the model theory of set theory without choice as a particular mathematical theory, but even to do that, one uses choice.

Theorem of Löwenheim-Skolem.Let $T$ be a theory in a language $L$. If it admits an infinite model $M$, then it admits a model in every cardinality $\geq \sup(\mathop{\rm Card}(L),\aleph_0)$.

To show the existence of a model of cardinality $\geq\kappa$, one enlarges the language $L$ and the theory $T$ by adding symbols $c_i$, indexed by a set of cardinality $\kappa$, and the axioms $c_i\neq c_j$ if $i\neq j$, giving rise to a theory $T'$ in a language $L'$. A structure for $L'$ is a structure for $L$ together with distinguished elements $c_i$; such a structure is a model of $T'$ if and only if it is a model of $T$ and if the elements $c_i$ are pairwise disintct. If the initial theory $T$ has an infinite model, then this model is a model of every finite fragment of the theory $T'$, because there are only finitely many axioms of the form $c_i\neq c_j$ to satisfy, and the model is assumed to be infinite. By Gödel's completeness theorem, the theory $T'$ has a model $M'$; forgetting the choice of distinguished elements, $M'$  is a model of the theory $T$, but the mere existence of the elements $c_i$ forces its cardinality to be at least $\kappa$.

To show that there exists a model of cardinality exactly $\kappa$ (assumed to be larger than $\sup(\mathop{\rm Card}(L),\aleph_0)$), one starts from a model $M$ of cardinality $\geq\kappa$ and defines a substructure by induction, starting from the constant symbols and adding step by step only the elements which are required by the function symbols, the axioms and the elements already constructed. This construction furnishes a model of $T$ whose cardinality is equal to $\kappa$.

Monday, March 23, 2015

When Lagrange meets Galois

Jean-Benoît Bost told me a beautiful proof of the main ingredient in the proof of Galois correspondence, which had been published by Lagrange in his 1772 “Réflexions sur la résolution des résolutions algébriques”, almost 60 years before Galois. (See Section 4 of that paper, I think; it is often difficult to recognize our modern mathematics in the language of these old masters.)

In modernized notations, Lagrange considers the following situation. He is given a polynomial equation $ T^n + a_{n-1} T^{n-1}+\cdots + a_0 = 0$, with roots $x_1,\dots,x_n$, and two “rational functions” of its roots  $f(x_1,\dots,x_n)$ and $\phi(x_1,\dots,x_n)$. (This means that $f$ and $\phi$ are the evaluation at the $n$-tuple $(x_1,\dots,x_n)$ of two rational functions in $n$ variables.) Lagrange says that $f$ and $\phi$ are similar (“semblables”) if every permutation of the roots which leaves $f(x_1,\dots,x_n)$ unchanged leaves $\phi(x_1,\dots,x_n)$ unchanged as well (and conversely). He then proves that $\phi(x_1,\dots,x_n)$ is a rational function of $a_0,\dots,a_{n-1}$ and $f(x_1,\dots,x_n)$.

Let us restate this in a more modern language. Let $K\to L$ be a finite Galois extension of fields, in the sense that $K= L^{G}$, where $G=\mathop{\rm Aut}_K(L)$. Let $a, b\in L$ and let us assume that every element $g\in G$ which fixes $a$ fixes $b$ as well; then Lagrange proves that $b\in K(a)$.

Translated in our language, his proof could be as follows. In formula, the assumption is that $g\cdot a=a$ implies $g\cdot b=b$; consequently, there exists a unique *function* $\phi\colon G\cdot a\to G\cdot b$ which is $G$-equivariant and maps $a$ to $b$. Let $d=\mathop{\rm Card}(G\cdot a)$ and let us consider Lagrange's interpolation polynomial —the unique polynomial $P\in L[T]$ of degree $d$ such that $P(x)=\phi(x)$ for every $x\in G\cdot a$. If $h\in G$, the polynomial $P^h$ obtained by applying $h$ to the coefficients of $P$ has degree $d$ and coincides with $\phi$; consequently, $P^h=P$. By the initial assumption, $P$ belongs to $K[T]$ and $b=P(a)$, hence $b\in K(a)$, as claimed.

Combined with the primitive element theorem, this allows to give another short, and fairly elementary, presentation of the Galois correspondence.