Read an Excerpt
Finite Structures with Few Types. (AM-152)
By Gregory Cherlin Ehud Hrushovski
Princeton University PressCopyright © 2003 Princeton University Press
All right reserved.
1.1 THE SUBJECT
In the present monograph we develop a structure theory for a class of finite structures whose description lies on the border between model theory and group theory. Model theoretically, we study large finite structures for a fixed finite language, with a bounded number of 4-types. In group theoretic terms, we study all sufficiently large finite permutation groups which have a bounded number of orbits on 4-tuples and which are k-closed for a fixed value of k. The primitive case is analyzed in [KLM; cf. Mp2]. The treatment of the general case involves the application of model theoretic ideas along lines pioneered by Lachlan.
We show that such structures fall into finitely many classes naturally parametrized by "dimensions" in the sense of Lachlan, which approximate finitely many infinite limit structures (a version of Lachlan's theory of shrinking and stretching), and we prove uniform finite axiomatizability modulo appropriate axioms of infinity (quasifinite axiomatizability). We also deal with issues of effectivity. At our level of generality, the proofs involve the extension of the methods of stability theory-geometries, orthogonality, modularity, definable groups-to this somewhat unstable context. Our treatment is relatively self-contained, although knowledge of the model theoretic background provides considerable motivation for the results and their proofs. The reader who is more interested in the statement of precise results than in the model theoretic background will find them in the next section.
On the model theoretic side, this work has two sources. Lachlan worked out the theory originally in the context of stable structures which are homogeneous for a finite relational language [La], emphasizing the parametrization by numerical invariants. Zilber, on the other hand, investigated totally categorical structures and developed a theory of finite approximations called "envelopes," in his work on the problems of finite axiomatizability. The class of [N.sub.0]-categorical, [N.sub.0]-stable structures provides a broad model theoretic context to which both aspects of the theory are relevant. The theory was worked out at this level in [CHL], including the appropriate theory of envelopes. These were used in particular to show that the corresponding theories are not finitely axiomatizable, by Zilber's method. The basic tool used in [CHL], in accordance with Shelah's general approach to stability theory and geometrical refinements due to Zilber, was a "coordinatization" of an arbitrary structure in the class by a tree of standard coordinate geometries (affine or projective over finite fields, or degenerate. Other classical geometries involving quadratic forms were conspicuous only by their absence at this point.
The more delicate issue of finite axiomatizability modulo appropriate "axioms of infinity," which is closely connected with other finiteness problems as well as problems of effectivity, took some time to resolve. In [AZ1] Ahlbrandt and Ziegler isolated the relevant combinatorial property of the coordinatizing geometries, which we refer to here as "geometrical finiteness," and used it to prove quasifinite axiomatizability in the case of a single coordinatizing geometry. The case of [N.sub.0]-stable, [N.sub.0]-categorical structures in general was treated in [HrTC].
The class of smoothly approximable structures was introduced by Lachlan as a natural generalization of the class of [N.sub.0]-categorical [N.sub.0]-stable structures, in essence taking the theory of envelopes as a definition. Smoothly approximable structures are [N.sub.0]-categorical structures which can be well approximated by finite structures in a sense to be given precisely in §2.1. One of the achievements of the structure theory for [N.sub.0]-categorical [N.sub.0]-stable theories was the proof that they are smoothly approximable in Lachlan's sense. While this was useful model theoretically, Lachlan's point was that in dealing with the model theory of large finite structures, one should also look at the reverse direction, from smooth approximability to the structure theory. We show here, confirming this not very explicitly formulated conjecture of Lachlan, that the bulk of the structure theory applies to smoothly approximable structures, or even, as stated at the outset, to sufficiently large finite structures with a fixed finite language, having a bounded number of 4-types.
Lachlan's project was launched by Kantor, Liebeck, and Macpherson in [KLM] with the classification of the primitive smoothly approximable structures in terms of various more or less classical geometries (the least classical being the "quadratic" geometry in characteristic 2, described in §2.1.2). These turn up in projective, linear, and affine flavors, and in the affine case there are some additional nonprimitive structures that play no role in [KLM] but will be needed here ("affine duality," §2.3). Bearing in mind that any [[??].sub.0]-categorical structure can be analyzed to some degree in terms of its primitive sections, the results of [KLM] furnish a rough coordinatization theorem for smoothly approximable structures. This must be massaged a bit to give the sort of coordinatization that has been exploited previously in an [omega]-stable context. We will refer to a structure as "Lie coordinatizable" if it is bi-interpretable with a structure which has a nice coordinatization of the type introduced below. Lie coordinatizability will prove to be equivalent to smooth approximability, in one direction largely because of [KLM], and in the other by the analog of Zilber's theory of envelopes in this context. One tends to work with Lie coordinatizability as the basic technical notion in the subject. The analysis in [KLM] was in fact carried out for primitive structures with a bound on the number of orbits on 5-tuples, and in [Mp2] it was indicated how the proof may be modified so as to work with a bound on 4-tuples. (Using only [KLM], we would also be forced to state everything done here with 5 in place of 4.)
In model theory, techniques for going from a good description of primitive pieces to meaningful statements about imprimitive structures generally fall under the heading of "geometrical stability theory," whose roots lie in early work of Zilber on [[??].sub.1]-categorical theories, much developed subsequently. Though the present theory lies slightly outside stability theory (it can find a home in the more recent developments relating to simple theories), geometrical stability theory provided a very useful template [Bu, PiGS].
Before entering into greater detail regarding the present work, we make some comments on the Galois correspondence between structures and permutation groups implicit in the above, and on its limitations.
Let X be a finite set. There is then a Galois correspondence between subgroups of the symmetric group Sym(X) on X, and model theoretic structures with universe X, associating to a permutation group the invariant relations, and to a structure its automorphism group. This correspondence extends to [[??].sub.0]-categorical structures ([AZ1, Introduction], [CaO]).
When we consider infinite families of finite structures in general, or a passage to an infinite limit, this correspondence is not well behaved. For instance, the automorphism group of a large finite random graph of order n (with constant and nontrivial edge probability) is trivial with probability approaching 1 as n goes to infinity, while the natural model theoretic limit is the random countable graph, which has many automorphisms.
It was shown in [CHL], building on work of Zilber for totally categorical structures, that structures which are both [[??].sub.0]-categorical and [[??].sub.0]-stable can be approximated by finite structures simultaneously in both categories. Lachlan emphasized the importance of this property, which will be defined precisely in §2.1, and proposed that the class of structures with this property, the smoothly approximable structures, should be amenable to a strong structure theory, appropriately generalizing [CHL]. Moreover, Lachlan suggested that the direction of the analysis can be reversed, from the finite to the infinite: one could classify the large finite structures that appear to be "smooth approximations" to an infinite limit, or in other words, classify the families of finite structures which appear to be Cauchy sequences both as structures and as permutation groups. This line of thought was suggested by Lachlan's work on stable finitely homogeneous structures [La], much of which predates the work in [CHL], and provided an additional ideological framework for that paper.
In the context of stable finitely homogeneous structures this analysis in terms of families parametrized by dimensions was carried out in [KL] (cf. [CL, La]), but was not known to go through even in the totally categorical case. Harrington pointed out that this reversal would follow immediately from compactness if one were able to work systematically within an elementary framework [Ha]. This idea is implemented here: we will replace the original class of "smoothly approximable structures" by an elementary class, a priori larger. Part of our effort then goes into developing the structure theory for the ostensibly broader class.
From the point of view of permutation group theory, it is natural to begin the analysis with the case of finite primitive structures. This was carried out using group theoretic methods in [KLM], and we rely on that analysis. However, there are model theoretic issues which are not immediately resolved by such a classification, even for primitive structures. For instance, if some finite graphs [G.sub.n] are assumed to be primitive, and to have a uniformly bounded number of 4-types, our theory shows that an ultraproduct [G.sup.*] of the [G.sub.n] is bi-interpretable with a Grassmannian structure, which does not appear to follow from [KLM] by direct considerations. The point here is that if [G.sub.n] is "the same as" a Grassmannian structure in the category of permutation groups, then it is bi-interpretable with such a structure on the model theoretic side. To deal with families, one must deal (at least implicitly) with the uniformity of such interpretations; see §8.3, and the sections on reducts. It is noteworthy that our proof in this case actually passes through the theory for imprimitive structures: any nonuniform interpretation of a Grassmannian structure on [G.sub.n] gives rise to a certain structure on [G.sup.*] a reduct of the structure which would be obtained from a uniform interpretation, and one argues that finite approximations (on the model theoretic side) to [G.sup.*] would have too many automorphisms. In other words, we can obtain results on uniformity (and hence effectivity) by ensuring that the class for which we have a structure theory is closed under reducts. This turns out to be a very delicate point, and perhaps the connection with effectivity explains why it should be delicate.
A rapid but thorough summary of this theory was sketched in [HrBa], with occasional inaccuracies. For ease of reference we now repeat the main results of the theory as presented there, making use of a considerable amount of specialized terminology which will be reintroduced in the present work. The various finiteness conditions referred to are all given in Definition 2.1.1.
Theorem 1 (Structure Theory)
Let M be a Lie coordinatizable structure. Then M can be presented in a finite language. Assuming M is so presented, there are finitely many definable dimension invariants for M which are infinite, up to equivalence of such invariants. If C is a set of representatives for such definable dimension invariants, then there is a sentence [??] = [??]M with the following properties:
1. Every model of [??] in which the definable dimension invariants of C are well-defined is determined up to isomorphism by these invariants.
2. Any sufficiently large reasonable sequence of dimension invariants is realized by some model of [??].
3. The models of [??] for which the definable dimension invariants of C are well-defined embed homogeneously into M and these embeddings are unique up to an automorphism of M.
There are a considerable number of terms occurring here which will be defined later. Readers familiar with "shrinking" and "stretching" in the sense of Lachlan should recognize the situation. Definable dimension invariants are simply the dimensions of coordinatizing geometries which occur in families of geometries of constant dimension; when the appropriate dimensions are not constant within each family, the corresponding invariants are no longer well-defined. A dimension invariant is reasonable if its parity is compatible with the type of the geometry under consideration; in particular, infinite values are always reasonable.
The statements of the next two theorems are slight deformations of the versions given in [HrBa]. We include more clauses here, and we use definitions which vary slightly from those used in [HrBa].
Theorem 2 (Characterizations)
The following conditions on a model M are equivalent:
1. M is smoothly approximable.
2. M is weakly approximable.
3. M is strongly quasifinite.
4. M is strongly 4-quasifinite.
5. M is Lie coordinatizable.
6. The theory of M has a model [M.sup.*] in a nonstandard universe whose size is an infinite nonstandard integer, and for which the number of internal n-types [s.sup.*.sub.n]([M.sup.*]) satisfies
[s.sup.*.sub.n]([M.sup.*]) [less than or equal to] [c.sup.n.sup.2]
for some finite c, and in which internal n-types and n-types coincide. (Here n varies over standard natural numbers.)
The class characterized above is not closed under reducts. For the closure under reducts we have:
Theorem 3 (Reducts)
The following conditions on a model M are equivalent:
1. M has a smoothly approximable expansion.
2. M has a weakly approximable expansion.
3. M is quasifinite.
4. M is 4-quasifinite.
5. M is weakly Lie coordinatizable
6. The theory of M has a model [M.sup.*] in a nonstandard universe whose size is an infinite nonstandard integer, and for which the number of internal n-types [s.sup.*.sub.n]([M.sup.*]) satisfies:
[s.sup.*.sub.n]([M.sup.*]) [less than equal to] [c.sup.n.sup.2]
for some finite c. (Here n varies over standard natural numbers.)
Excerpted from Finite Structures with Few Types. (AM-152) by Gregory Cherlin Ehud Hrushovski Copyright © 2003 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.