Reading seminar 5: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

20 November, 2009 in Logic reading seminar, math.LO

After a one-week hiatus, we are resuming our reading seminar of the Hrushovski paper. This week, we are taking a break from the paper proper, and are instead focusing on the subject of stable theories (or more precisely, ${\omega}$ -stable theories), which form an important component of the general model-theoretic machinery that the Hrushovski paper uses. (Actually, Hrushovski’s paper needs to work with more general theories than the stable ones, but apparently many of the tools used to study stable theories will generalise to the theories studied in this paper.)

Roughly speaking, stable theories are those in which there are “few” definable sets; a classic example is the theory of algebraically closed fields (of characteristic zero, say), in which the only definable sets are boolean combinations of algebraic varieties. Because of this paucity of definable sets, it becomes possible to define the notion of the Morley rank of a definable set (analogous to the dimension of an algebraic set), together with the more refined notion of Morley degree of such sets (analogous to the number of top-dimensional irreducible components of an algebraic set). Stable theories can also be characterised by their inability to order infinite collections of elements in a definable fashion.

The material here was presented by Anush Tserunyan; her notes on the subject can be found here. Let me also repeat the previous list of resources on this paper (updated slightly):

Henry Towsner’s notes (which most of Notes 2-4 have been based on; updated to remove references to homogeneity, using only countable saturation);
Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
Anand Pillay’s sketch of a simplified proof of Theorem 1.1.

— 1. Stable theories —

Let ${L}$ be a countable language. Recall that if we have a structure ${M}$ for ${L}$ , and a set ${A}$ of constants in ${M}$ , we can define an ( ${n}$ -ary) type of ${M}$ over ${A}$ to be a maximal consistent family ${p}$ of formulae ${\phi(x_1,\ldots,x_n)}$ for an ${n}$ -tuple ${\vec x = (x_1,\ldots,x_n)}$ , where the formulae are allowed to use ${A}$ as constants. For instance, in the language of algebraically closed fields over some base field ${k}$ (all elements of which are constants in ${L}$ ), if ${M}$ is an algebraic closed field and ${A}$ is empty, the type associated to a “generic” element of an algebraic variety ${V \subset M^n}$ defined over ${k}$ (i.e. elements that obey the defining equations for ${k}$ , but do not obey any other algebraic relations over ${k}$ ) is a type. If one makes ${A}$ non-empty, then one now also needs to consider algebraic relations over ${k(A)}$ , the field formed by adjoining ${A}$ to ${k}$ . Note that in general, a type will not be realised in the structure ${M}$ (unless that structure is so huge as to be saturated over the cardinality of ${A}$ ), but can always be realised in some extension of ${M}$ , by the completeness theorem.

The set of all ${n}$ -ary types of ${M}$ over ${A}$ is denoted ${S_n^M(A)}$ . It has a natural topology, the Stone topology, whose basic open (in fact, clopen) sets are given by ${U_\phi := \{ p \in S_n^M(A): \phi \in p \}}$ for any formula ${\phi(x_1,\ldots,x_n)}$ defined over ${A}$ . This makes the space of types a Stone space (totally disconnected, Hausdorff, compact).

In general, the number of types in the world can be quite large: if ${A}$ has cardinality ${\kappa}$ for some infinite ${\kappa}$ , then the total number of formulae in ${L(A)}$ is also ${\kappa}$ , so the number of types could conceivably be as large as ${2^\kappa}$ . But for a special class of theories – the ${\kappa}$ -stable theories – the number is much smaller:

Definition 1 Let ${\kappa}$ be an infinite cardinal. A complete theory ${T}$ is ${\kappa}$ -stable if, for any structure ${M}$ satisfying ${T}$ , and any set ${A}$ of constants in ${M}$ of cardinality at most ${\kappa}$ , the set of ${n}$ -ary types of ${M}$ over ${A}$ is at most ${\kappa}$ for every ${n}$ .

The classic example of a ${\kappa}$ -stable theory (for any infinite ${\kappa}$ ) is the theory of algebraically closed fields with fixed characteristic (it is a classical theorem that this theory is complete, basically thanks to quantifier elimination). By quantifier elimination (or by many applications of the nullstellensatz), one can show that the ${n}$ -ary types in this theory over ${A}$ are in one-to-one correspondence with minimal ideals in ${F(x_1,\ldots,x_n)}$ , where ${F = k(A)}$ , where ${k}$ is the base field of given characteristic, with a type ${p}$ consisting of the “generic” points cut out by the ideal ${I := \{ f \in F(x_1,\ldots,x_n): (f(x_1,\ldots,x_n)=0) \in p \}}$ . More succinctly, ${S_n^M(A) \equiv Spec(F(x_1,\ldots,x_n))}$ . By Hilbert’s basis theorem, all ideals in ${F(x_1,\ldots,x_n)}$ are finitely generated, and so the cardinality of types is easily seen to be at most ${\kappa}$ .

When ${\kappa}$ is uncountable, a more general example of a ${\kappa}$ -stable theory is that of a ${\kappa}$ -categorical theory – a theory such that any two models of cardinality ${\kappa}$ are isomorphic. (Details can be found in Anush’s notes.)

The classic example of a theory which is not ${\kappa}$ -stable is the theory of dense linear orderings, i.e. the theory of the rationals ${{\mathbb Q}}$ with the order relation ${<}$ . Using Dedekind cuts, one can associate a type in ${S_1^{\mathbb Q}({\mathbb Q})}$ to every real number, and so there are uncountably many types here even though the number of constants is countable. Thus this theory is not ${\omega}$ -stable (though it is ${\omega}$ -categorical).

Now we look at alternate characterisations of stability, particularly ${\omega}$ -stability. If ${M}$ is a model of a theory ${T}$ in a language ${L}$ , define a binary tree in ${M}$ to be a collection ${\phi_s(x_1,\ldots,x_n)}$ of ${n}$ -ary formulas in ${L(M)}$ , where ${s}$ are indexed by finite strings of ${0}$ s and ${1}$ s, each of which are consistent with ${T}$ , and such that for any string ${s}$ and its two children ${s0}$ and ${s1}$ , the formulae ${\phi_{s0}}$ and ${\phi_{s1}}$ cut out disjoint subsets of the set cut out by ${\phi_s}$ relative to ${T}$ , or more precisely that ${\phi_{s0},\phi_{s1}}$ are mutually inconsistent in ${T}$ , but both imply ${\phi_s}$ .

Theorem 2 For a countable language ${L}$ and a complete theory ${T}$ , the following are equivalent:

(i) No binary tree of formulae exists for any model ${M}$ of ${T}$ .

(ii) ${T}$ is ${\kappa}$ -stable for every infinite ${\kappa}$ ;

(iii) ${T}$ is ${\omega}$ -stable.

Proof: (ii) trivially implies (iii). Now we show that (i) implies (ii), i.e. we take a theory which is not ${\kappa}$ -stable for some infinite ${\kappa}$ and use it to create a binary tree.

By hypothesis, we can find a model ${M}$ and a set ${A}$ of constants of cardinality at most ${\kappa}$ , and an ${n}$ such that the number of ${n}$ -ary types exceeds ${\kappa}$ . We can use this to create a binary tree as follows. Call a formula ${\phi(x_1,\ldots,x_n)}$ defined over ${A}$ large if it is contained in more than ${\kappa}$ types (i.e. if ${U_\phi}$ has cardinality more than ${\kappa}$ ), and small types; thus in particular any tautology is large. We set the root ${\phi_\emptyset}$ of the binary tree to be such a large formula. We then remove all the types associated to small formulae from ${U_{\phi_\emptyset}}$ , and still retain more than ${\kappa}$ types. Picking two such distinct types ${p,q}$ , one can find a formula ${\psi}$ separating ${p}$ from ${q}$ (since ${p \neq q}$ ), which allows one to find two formulae ${\phi_1, \phi_2}$ which are inconsistent with each other and imply ${\phi_\emptyset}$ (namely ${\phi \wedge \neg \psi}$ and ${\phi_\emptyset \wedge \neg \psi}$ ); by construction, these formulae are also large. Iterating this procedure gives the binary tree.

Finally, to show (iii) implies (i), we see from taking Dedekind cuts again that an infinite binary tree can be used to define an uncountable number of types (by including all the formulae to the left of a cut, excluding all the ones to the right, and then completing to a complete type), which violates ${\omega}$ -stability. $\Box$

The property of not having binary trees is also known as being totally transcendental, though it was unclear where this terminology came from (especially given that the theory of algebraically closed fields is the classic example of a totally transcendental theory).

We have seen that order theories tend to be unstable. Indeed, ${\omega}$ -stable theories is that they are unable to definably order infinite sets:

Theorem 3 Let ${T}$ be an ${\omega}$ -stable theory, let ${M}$ be a model of ${T}$ , and let ${X}$ be an infinite subset of ${M}$ . Then there is no definable relation ${<}$ in ${L}$ that is a total ordering on ${X}$ .

Proof: Suppose this is not the case. Using the compactness theorem, we can thus find a model of ${M}$ with a countably infinite subset ${X}$ for which ${<}$ endows ${X}$ with the order structure of the rationals. But then by Dedekind cuts one can then create an uncountable number of types over ${X}$ , contradicting ${\omega}$ -stability. $\Box$

It is easy to generalise ${\omega}$ -stability in the above theorem to ${\kappa}$ -stability for any infinite ${\kappa}$ , by developing analogues of the rational order structure for other cardinalities; see Anush’s notes.

There was some debate as to whether the theory of the Rado graph admitted any obvious definable total ordering on a countable set, but the discussion was inconclusive.

— 2. Stability and indiscernability —

Recall from previous notes that a sequence ${x_1,x_2,\ldots}$ of elements of a structure ${M}$ were order-indiscernible if all of the ${k}$ -tuples ${(x_{i_1},\ldots,x_{i_k})}$ with ${i_1<\ldots<i_k}$ were elementarily indistinguishable from each other (i.e. every formula obeyed by one tuple, is obeyed by all the other tuples). One can use Ramsey-theoretic methods to generate a plentiful supply of order-indiscernibles.

One would however like a stronger notion of indiscernability, which we will just call indiscernability, in which all ${k}$ -tuples ${(x_{i_1},\ldots,x_{i_k})}$ with ${i_1,\ldots,i_k}$ distinct (but not necessarily ordered) are indistinguishable. In general, order indiscernability does not imply indiscernability. But because stable theories cannot “see” order, one has equivalence in this case:

Theorem 4 In an ${\omega}$ -stable theory, every order-indiscernible sequence is indiscernible.

Proof: Let ${x_1,x_2,\ldots}$ be order-indiscernible in some model ${M}$ . To show indiscernibility, it suffices to show that permutations of ${(x_{i_1},\ldots,x_{i_k})}$ are indistinguishable from each other. As permutations are generated by adjacent transpositions, it suffices to do this for adjacent transpositions. For notational simplicity we will just show that ${(x_1,x_2)}$ and ${(x_2,x_1)}$ are indistinguishable; the general case is similar.

Suppose this is not the case, thus there is a formula ${\phi}$ such that ${\phi(x_1,x_2)}$ holds in ${M}$ but ${\phi(x_2,x_1)}$ fails. Then ${\phi(x_i,x_j)}$ holds precisely when ${i < j}$ , thus ${\phi}$ orders ${x_1,x_2,\ldots}$ , contradicting the previous theorem.

(In the general case, one cannot quite use Theorem 3 directly, but one can modify the proof to achieve a similar result; see Anush’s notes.) $\Box$

By the previous remarks, the argument can also be extended to ${\kappa}$ -stable theories for any infinite ${\kappa}$ .

— 3. Morley rank and degree —

Suppose one was working in the theory of algebraically closed fields of characteristic zero, and wanted to define the notion of the dimension of an algebraic set ${V}$ . Clearly, one would want finite sets to have dimension ${0}$ , and to be the only sets with this property. As for infinite sets, one could recursively define dimension by enforcing the following statement: an algebraic set has dimension at least ${\alpha+1}$ if and only if it contains infinitely many disjoint algebraic sets of dimension at least ${\alpha}$ .

One can do the same for any theory, assigning to each definable set in a structure ${M}$ a Morley rank, which is either ${-1}$ , an ordinal, or ${\infty}$ (which we consider to be larger than all the ordinals (!)) by the following rules:

The empty set has Morley rank ${-1}$ ; all other definable sets have Morley rank at least ${0}$ .
If ${\alpha}$ is an ordinal, then a definable set has Morley rank at least ${\alpha+1}$ if and only if it contains infinitely many disjoint definable sets of Morley rank at least ${\alpha}$ .

Note that for a limit ordinal ${\alpha}$ , a set will have Morley rank at least ${\alpha}$ iff it has Morley rank at least ${\beta}$ for all ${\beta < \alpha}$ , and a set will have Morley rank ${\infty}$ if it has Morley rank at least ${\alpha}$ for every ordinal ${\alpha}$ . Using this, one can show by transfinite induction that every definable set has a Morley rank.

The Morley rank of a formula ${\phi}$ cutting out a definable set in a structure ${M}$ may depend on the choice of structure ${M}$ . However, if we assume that the structure ${M}$ is countably saturated, i.e. that any finitely satisfiable collection of formulae involving at most countably many constants is fully satisfiable, then the dependence on ${M}$ largely disappears. To see this, we first need a preliminary lemma:

Lemma 5 Let ${M}$ be countably saturated, and let ${A_a}$ be a definable set depending on a parameter ${a}$ . Then the Morley rank of ${A_a}$ in ${M}$ depends only on the type of ${a}$ .

Proof: Let ${a, b}$ have the same type (i.e. they are elementarily indistinguishable). We need to show that ${A_a}$ , ${A_b}$ have the same Morley rank. Suppose not. If ${A_a}$ was empty, then ${A_b}$ would be also by indistinguishability, and the claim is obvious; so suppose that both sets are non-empty. Then, without loss of generality, we may assume that ${A_a}$ has Morley rank ${\alpha}$ but ${A_b}$ has Morley rank at least ${\alpha+1}$ , thus ${A_b}$ contains a countable family of disjoint definable sets ${B_{b,c_1}, B_{b,c_2}, \ldots}$ of Morley rank at least ${\alpha}$ defined using some constants ${c_1, c_2, \ldots}$ . Using countable saturation, one can find inductively constants ${d_1,d_2,\ldots}$ such that ${(a,d_1,\ldots,d_m)}$ has the same type as ${(b,c_1,\ldots,c_m)}$ for every ${m}$ . This creates a countable family of djsoint definable sets ${B_{a,d_1},B_{a,d_2},\ldots}$ of ${A_a}$ , which by an induction hypothesis on ${\alpha}$ can be assumed to have Morley rank at least ${\alpha}$ , which forces ${A_a}$ to have Morley rank at least ${\alpha+1}$ , a contradiction. $\Box$

Corollary 6 If ${M}$ is countably saturated, and ${\phi_a}$ is a formula defined using some constants ${a}$ in ${M}$ , then the Morley rank of ${\phi_a}$ in ${M}$ is equal to the Morley rank of ${\phi_a}$ in ${N}$ , for any elementary extension ${N}$ of ${M}$ .

Proof: It is easy to see by transfinite induction that the Morley rank in ${N}$ is at least as large as that of ${M}$ (there are more non-empty definable sets). Suppose for contradiction that the Morley rank in ${M}$ is ${\alpha}$ , but the Morley rank in ${N}$ is at least ${\alpha+1}$ . (The case when ${\phi_a}$ cuts out an empty set in ${M}$ or ${N}$ is trivial from elementary equivalence.) Then the set ${\phi_a(N)}$ cut out by ${\phi_a}$ in ${N}$ contains a countable family of disjoint definable sets ${\psi_{a,b_1}(N), \psi_{a,b_2}(N), \ldots}$ of Morley rank at least ${\alpha}$ , for some ${b_1, b_2, \ldots}$ in ${N}$ . By elementary equivalence and countable saturation, one can inductively find ${c_1,c_2,\ldots}$ in ${M}$ such that the type of ${(a,c_1,\ldots,c_m)}$ in ${M}$ equals the type of ${(a,b_1,\ldots,b_m)}$ in ${N}$ . Then ${\psi_{a,c_1}(M), \psi_{a,c_2}(M), \ldots}$ form a countable family of disjoint definable sets in ${\phi_a(M)}$ , which have Morley rank at least ${\alpha}$ by the previous lemma, giving the desired contradiction. $\Box$

Corollary 7 If ${N_0, N_1}$ are countably saturated elementary extensions of ${M}$ , and ${\phi_a}$ is a formula defined using some constants ${a}$ in ${M}$ , then the Morley rank of ${\phi_a}$ in ${N_0}$ is the same as that in ${N_1}$ .

Proof: Take a common countably saturated elementary extension ${N}$ of both ${N_0}$ and ${N_1}$ ; by the previous corollary, the rank in ${N_0}$ or in ${N_1}$ is equal to that in ${N}$ . $\Box$

We can thus define the (structure-independent) Morley rank of any formula ${\phi}$ in ${M}$ to be the rank of ${\phi}$ in any countably saturated elementary extension.

It is not hard to show that Morley rank obeys the basic properties of a dimension, e.g. the dimension of a union is the larger of the dimensions of the two summands (in particular, Morley rank is monotone with respect to set inclusion), and that the only sets of dimension zero are the finite sets.

To avoid technical issues, let us now assume that all models ${M}$ we work in are small elementary submodels of a universal model ${{\Bbb M}}$ (i.e. a model which is saturated with respect to all small models).

We know that any set of a given Morley rank ${\alpha}$ cannot be partitioned into infinitely many disjoint subsets of the same rank. Using this and König’s lemma, we in fact conclude

Proposition 8 If a definable set ${A}$ has an ordinal Morley rank ${\alpha}$ , then there exists a finite ${d}$ such that ${A}$ cannot be partitioned into more than ${d}$ definable subsets of Morley rank ${\alpha}$ .

Proof: We form a partial binary tree by taking ${A}$ and splitting it (if possible) into disjoint non-empty subsets of Morley rank ${\alpha}$ , then taking these subsets and splitting them further, continuing until no further splitting is possible. If this tree is infinite, then König’s lemma ensures an infinite path, which easily gives a decomposition of ${A}$ into infinitely many disjoint definable sets of Morley rank ${\alpha}$ , a contradiction. Thus this tree is finite, and decomposes ${A}$ into some finite number ${B_1,\ldots,B_d}$ of rank ${\alpha}$ definable sets which are “irreducible” in the sense that they cannot be partitioned into two subsets of rank ${\alpha}$ .

We now claim that any other partition ${A = C_1 \cup \ldots \cup C_m}$ of ${A}$ into rank ${\alpha}$ definable sets must have ${m \leq d}$ . Note that for each ${B_i}$ there is at most one ${C_j}$ for which ${B_i \cap C_j}$ has rank ${\alpha}$ , otherwise ${B_i}$ would not be irreducible. On the other hand, each ${C_j}$ has to have at least one ${B_i}$ for which ${B_i \cap C_j}$ had rank ${\alpha}$ , for if all the ${B_i \cap C_j}$ had rank less than ${\alpha}$ then ${C_j}$ would also. Thus we can assign disjoint non-empty subsets of ${\{1,\ldots,d\}}$ to each ${j}$ in ${\{1,\ldots,m\}}$ , which forces ${m \leq d}$ . $\Box$

We thus define the Morley degree of ${A}$ to be the largest ${d}$ for which one can partition ${A}$ into disjoint definable sets of the same rank. Note that all such components necessarily have degree ${1}$ .

About these ads

10 comments

Comments feed for this article

21 November, 2009 at 12:23 pm

Anush Tserunyan

Hi Prof. Tao,

In the end of the proof of Proposition 8, you say that we have an injection from ${1,2,...,m}$ to ${1,2,...,d}$ , but the correspondence may not be a function since for one $C_j$ there may be two different $B_i$ -s having rank $\alpha$ intersections with $C_j$ . That’s why in the notes I wrote it as a partial function going the other way.

Thanks,
Anush

[Corrected, thanks. -T.]

24 November, 2009 at 4:39 pm

Alex Usvyatsov

Dear Terry,

What did you mean by a definable ordering on a countable set (for the random graph)? There is no definable ordering on a definable subset of $M^n$ for any $n$ . The order property is exemplified by singletons: there are indiscernible sequences a_i, b_j such that R(a_i,b_j) iff i<j. So there is a definable order on an indiscernible sequence of pairs: $a_ib_i < a_jb_j$ iff $R(a_i,b_j)$ . If, on the other hand, you take a set of singletons $X$ , then by quantifier elimination the type of a pair $ab \in X^2$ is determined by whether or not they are R-related (note that any two singletons have the same type), so there is no ordering… One might ask what happens when one works with parameters, but I don't think that this is any different: given an ordering with parameters on an infinite set of singletons $X$ , one may assume that all the elements have the same type over the parameters, so the type of a pair from $X$ is still symmetric.

Possibly a small suggestion: stability theory can also be done locally (that is, looking at a single formula). Since one basic idea in Udi's paper is that a lot can be done once you have just one stable relation, it might be interesting to develop some of the local theory as well as the global one (global stability theory can be also deduced from the local one, but not e.g. $\omega$ -stability, Morley rank, etc).

26 November, 2009 at 12:54 pm

Terence Tao

Ah, I see now. The relation you define gives rise to orderings on arbitrarily large sets in the random graph itself, and thus to orderings on infinite sets in other models of the random graph (e.g. a nonstandard random graph), but does not order any definable sets. Thanks!

I personally don’t understand stability well enough yet to comment intelligently on your suggestion, but hopefully it will become clearer what the minimal amount of stability theory tools are needed to get Hrushovski’s results.

27 November, 2009 at 3:41 am

Alex Usvyatsov

Oh, I understand you question now (I think). You are asking whether the random graph is an unstable structure, that is, whether there is an infinite subset of the random graph itself which is definably ordered. The short answer is yes, but let me elaborate a bit.

First, although in model theory we normally don’t distinguish between a model and its elementary extensions when it comes to properties like stability (just like we often don’t distinguish between a definable order on a subset of the model and a subset of the model to some finite power), these distinctions are sometimes important. There are stable structures with unstable theories (structures in which one can order arbitrarily large finite sets, but no infinite set), and they have certain interesting properties (related to things I have been working on recently, actually). One example is Krivine-Maurey theorem saying that a quantifier-free stable separable Banach space (here stability is of the structure, not the theory; one has to define stability in the right way for this context, but let’s ignore this for a moment) embeds an $\ell_p$ space almost isometrically.

As for the random graph $G$ , you can actually find the ordering on pairs I was talking about in the structure itself. There are several related ways of seeing that this has to be the case. First, since $G$ is $\omega$ -saturated, so if you have an instance of the order property in an elementary extension, you can construct an ordering on an infinite subset of $G$ itself by saturation. Second, $G$ is $\omega$ -categorical; so if you have the order property in an elementary extension, there is such a countable elementary extension, but it is isomorphic to $G$ . Since $\omega$ -categoricity implies $\omega$ -saturation, this is in some sense a stronger argument.

But in this case, the straightforward construction that I mentioned simply works: choose $a_i, b_i \in G$ in by induction such that

$a_i$ are R-related to $b_{<i}$ (that is, to all $b_j$ for j<i
$b_i$ is not R-related to $a_{<i}$
$a_i$ is not R-related to $a_{<i}$ , same for the b_i's.

The last clause is somewhat arbitrary, but it ensures that both sequences are indiscernible, so not only do you get a definable ordering on the sequence of pairs, but we have constructed an instance of the order property in $G$ itself, no compactness arguments needed.

Still. it is true that there is no order on definable sets or on infinite sets of singletons.

The answer to your question about how much stability is actually needed for Hrushovski’s paper is “virtually none”. But local stability can be an illuminating background discussion, just like $\omega$ -stability that you have been looking at. If you are currently mostly interested in stable group theory (e.g. existence of stabilizers), then $\omega$ -stability is a simpler framework (due to the existence of Morley rank), and possibly a better choice. But if you would also like to see some general model theoretic properties of stable theories (such as definability of types), I personally would recommend the local approach. The very beginning of Pillay’s book “Geometric stability theory” is a good source.

26 November, 2009 at 12:11 am

Leonard

Hi Prof. Tao,

It’s interesting to note that all the tools which your reading group has discussed so far are sufficient to develop a proof of Morley’s Categoricity Theorem, which states that a complete theory in a countable language is k-categorical for all uncountable cardinals k if and only if it is l-categorical for just one uncountable cardinal l. However, I suppose that this result, though an important one, won’t be of any relevance to your discussion?

26 November, 2009 at 12:55 pm

Terence Tao

Morley’s theorem is mentioned in passing in Anush’s notes (to explain why categorical theories are stable), but yes, it does seem to not play a direct role in Hrushovski’s paper, though it is of course in the same general subject area.

2 December, 2009 at 11:18 am

imiro

I am a former model-theorist: my advisor was Jerry Keisler, my “grandfather” was Alfred Tarski, whom I knew well while in Berkeley teaching set theory and model theory. I find your investigations between model theory and other parts of mathematics fascinating and to help I would like to bring to your attention my paper on Modeloids (Transactions of AMS, vol. 250, June 1979, pp. 47 – 90); the concepts discussed there are naturally tied to the fields (group theory, combinatorics, topological dynamics, etc.) where you apply model theory.

What follows is a brief synopsis of modeloids balancing brevity and accuracy (brief rather than pedantic):

The group of automorphisms of a structure M = (A R, … ) in a language L provides useful information about M but the set of partial automorphisms (finite functions on A preserving the relations of L) captures the essence of the structure M, the salient model-theoretic properties like homogeneity, being saturated, etc. discussed in your postings. The set F of partial automorphisms of a model M satisfies the following properties:

0. elements of F are one-to-one finite functions on A (from subsets of A to A)
1. all finite identities (including the empty one) are in F
2. F is closed under inverses
3. F is closed under compositions (compositions may be empty)

A modeloid on A is a set F of functions on A satisfying the above properties.

Note that the somewhat arbitrary language L is gone. However, given a modeloid F on A there is a language L and a structure M = (A, R, …) in that language such that F is the set of partial automorphisms of M.

The key operation on modeloids is the derivative defined as the set F’ of functions in F which can be “extended”: $f \in F$ ’ iff
$( \forall x \in A ) ( \exists g \in F ) [ x \in domain(g) \wedge f \subseteq g ]$ and
$( \forall y \in A ) ( \exists g \in F ) [ y \in range(g) \wedge f \subseteq g ]$
Clearly, F’ is a modeloid included in F and we can iterate the operation by $F^{\alpha + 1} = ( F^{\alpha}$ )’ and taking the intersection at limit ordinals. Eventually we end with $F^b$ (b for basic) such $( F^b )$ ’ = $F^b$ , the basic modeloid for b.

The paper characterizes basic modeloids in terms of topological dynamics (section 5 of the paper). For countable A, Fb consists exactly of the “partial automorphisms” which can be extended to an automorphism – a back-and-forth argument).

When I wrote the paper it looked like the process of taking successive derivatives was akin to obtaining a Poisson stable point in the qualitative theory of differential equations (see p. 71 of the paper).

The paper is actually written in terms of a “dual” notion, in terms of equivalence relations. Notation seems easier and it is more general since it allows languages without equality.
Modeloid F is represented as an equivalence relation $E_F$ on A* (the set of finite sequences from A) as follows: (a, b in A* are sequences of the same length):
$a E_F b$ iff for some f in F f(a) = b (the natural extension of f to words in A*)
In this terminology (and a model M = (A, R, …) of L in the back of our mind), the equivalence classes correspond to the minimal subsets definable in the structure using no quantifiers.
The derivative of a modeloid E is then a more precise equivalence relation E’ (also on A*) defined by: aE’b iff
$( \forall x \in A ) ( \exists y \in A ) [ axEby ]$ and
$( \forall y \in A ) ( \exists x \in A ) [ axEby ]$
(ax is the concatenation of a from A* with the element x of A) This is essentially an Ehrenfeucht game: I choose x (or y) and, to win, you have to find y (or x) to make axEby true. The equivalence classes of E’ are the minimal subsets of M definable in the structure using one quantifier.

As before, the operation can be iterated to obtain the basic modeloid $E^b$ whose derivative is itself. The key model-theoretical properties are contained in the manner of how the basic modeloid for E “fits” into E (see Proposition 4.9 and Proposition 7.1).

To give an example, the type of a k-tuple a from A* is {a/ $E^n$ | n > 0 } (the $E^n$ equivalence classes containing a). A type in general is a descending sequence of equivalence classes $a_n / E^n$ where a’s are from $A^k$ (fixed k). Note that $a_n E^n a_{n + 1}$ because $E^n \subseteq E^{n + 1}$ .
Countable saturation means that all types are realized, that is
For each sequence $a_n \in A^k$ such that $a_n E^n a_{n + 1}$ we can find $a \in A^k$ satisfying $a E^n a_n$ for large enough n’s.
(If you think of $a E^n b$ as |a – b| < 1/n (i.e. a and b are 1/n close) then this is very much like the completeness of reals).
Other model-theory concepts like homogeneity, stability, ultraproducts, etc. are discussed in section 7 of the paper. Take a look.

2 December, 2009 at 6:34 pm

Miro Benda

One more thing that I would like to add to my (iMiro) comment about modeloids (Trans of AMS, vol. 250, June 1979, pp. 47 – 90): As a specific example of modeloid techniques I used modeloids associated with subgroups of symmetric groups to show that for n > 4 the alternating group is the only non-trivial normal subgroup (see Application 6.13 on p. 75). The proof relies just on equivalences; I label it there as “an exercise in pretending”. Though it is not a “proof without words” it does not invoke Sylow’s Theorem, Galois Theory, or other high power machinery.

4 December, 2009 at 9:56 pm

Reading seminar 6: “Stable group theory and approximate subgroups”, by Ehud Hrushovski « What’s new

[...] that any countable set of constants can only generate at most a countable number of types. Last time, we showed that -stability also implied that for any other infinite cardinal , a set of constants [...]

12 September, 2012 at 7:09 pm

Definable subsets over (nonstandard) finite fields, and almost quantifier elimination « What’s new

[...] geometry; for instance, the concept of Morley rank and Morley degree in model theory (discussed in this previous blog post) directly generalises the concepts of dimension and degree in algebraic geometry.) Over , the [...]

	Anonymous on Estimation of the Type III…
	Anonymous on A combinatorial subset sum pro…
	Gergely Harcos on Further analysis of the trunca…
	Gergely Harcos on Further analysis of the trunca…
	Gergely Harcos on Further analysis of the trunca…
	Terence Tao on A combinatorial subset sum pro…
	Ph.M on Estimation of the Type III…
	Eytan Paldi on Further analysis of the trunca…
	Terence Tao on Estimation of the Type III…
	Eytan Paldi on Further analysis of the trunca…
	v08ltu on Estimation of the Type III…
	George DeMarse on Does one have to be a genius t…
	Terence Tao on Estimation of the Type III…
	Emmanuel Kowalski on Estimation of the Type III…
	v08ltu on Estimation of the Type III…

Reading seminar 5: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

10 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”

Reading seminar 5: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

10 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”