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$.

Link to Part 2 — Definable sets, types; quantifier elimination