Constructing ω-stable Structures: Model Completeness

John T. Baldwin Department of Mathematics, Statistics and Computer Science University of Illinois at Chicago^{∗}

Kitty Holland Department of Mathematics Northern Illinois University^{†}

October 10, 2003

Abstract

The projective plane of [2] is model complete in a language with additional constant symbols. The infinite rank bicolored field of [14] is not model complete. The finite rank bicolored fields of [4, 6] are model complete. More generally, the finite rank expansions of a strongly minimal set obtained by adding a ‘random’ unary predicate are almost strongly minimal and model complete provided the strongly minimal set is ‘well-behaved’ and admits ‘exactly rank k formulas’. The last notion is a geometric condition on strongly minimal sets formalized in this paper.

There are a number of variants of the ‘Hrushovski construction’ [10] which produce ωstable or even ℵ_{1}-categorical theories. All of them result in theories which are nearly model complete (all formulas are equivalent to a Boolean combination of existential formulas); some result in model complete theories (all formulas are equivalent to existential formulas). These ‘quantifier elimination’ results are closely connected to complexity of the axiomatization of the theory. Every model complete theory is ∀∃-axiomatizable; a theorem of Lindstrom [11] asserts every ∀∃-theory that is categorical in some infinite power is model complete. One of the intriguing features of the Hrushovski construction and the associated Shelah-Spencer random graph was that theories constructed for some other purposes naturally arose with ∀∃∀-axiomatizations. Almost no natural theories are that complex. It was a surprise when Holland [9] proved that the strongly minimal Hrushovski constructions were in fact model complete (and so admit ∀∃-axiomatizations). In this paper we investigate several variants on the construction and show that Holland’s model completeness extends from the strongly minimal case to ℵ_{1}-categorical expansions by a unary predicates of strongly minimal sets which satisfy a certain geometric condition: the existence of exactly k-independent sequences. In fact we show that these theories are all almost strongly minimal. Ahlbrandt and Baldwin [1] had shown that every ℵ_{0}-categorical almost strongly minimal theory is axiomatizable using at most n alternations of quantifiers for some n. But Marker [12] has shown that the minimal such n could be arbitrary. The essence of Marker’s counterexamples is to make the definition of the strongly minimal set complicated. Our strongly minimal sets are Σ_{1}- definable.

∗e-mail: jbaldwin@uic.edu. Partially supported by NSF grant DMS-0100594.

†email: kholland@math.niu.edu. Partially supported by NSF grant DMS 0203747.

The infinite rank bicolored field of [14] is not model complete. Using an argument in the style of [9], we establish the model completeness of an expansion by constants of the projective plane in [2].

This paper builds on the notation and results in [4, 5, 2]. The general framework consists of a class \overline{K}_{0} of countable models which have hereditarily nonnegative rank with respect to a given predimension δ. A strong substructure relation is defined on \overline{K}_{0} by A ≤ B if for every finite B′ contained in B, δ(B′/A) ≥ 0. In each case, the class \overline{K}_{0} has amalgamation with respect to ≤ and we are able to produce a countable generic structure 𝔾 which is ω-saturated.

In the first section, we provide a sufficient condition for an almost strongly minimal theory to have a finite extension by constants that is model complete. The main goal of the paper is to prove certain constructions yield ℵ_{1}-categorical model complete theories. We exhibit two quite different proof methods. In the second section we deal with expansions of a ‘wellbehaved’ strongly minimal set. Using the known ℵ_{1}-categoricity of the theories, we show they are model complete. In fact, no expansion by constants is needed. The result depends on the existence of exactly k-independent sequences. In the third section, we obtain directly a ∀∃-axiomatization of the projective plane [2] and prove these axioms are ℵ_{1}-categorical. By Lindstrom, we conclude model completeness. And in the final section we review the significance of these results and suggest some further problems.

1 Some ‘Ancient’ model theory

We prove a sufficient condition for almost strong minimality that could have been proved long ago but the proper formulation was missed. For this, we must be careful about the adjunction of additional constants; we delineate this below. We will have to relativize certain notions to the domain in which they are computed; we indicate this by subscripting the ambient model.

We say the complete theory T′ is a principal extension of T if the language of T′ is obtained by adding a finite number of constants to that of T and if T′ is axiomatized by adding one additional sentence to the axioms of T.

Notation 1.1 ϕ(M, c) denotes the set of solutions of ϕ(v, c) in M.

Definition 1.2 1. For X ⊂ M, the algebraic closure of X in M, acl_{M}(X) is the set of elements a of M such that M ⊧ ϕ(a, c) ∧ (∃^{<m}v)ϕ(v, c) for some c ∈ X and some formula ϕ.

2. The theory T is almost strongly minimal (witnessed by T′) if T′ is a principal extension of T and there is a strongly minimal formula ϕ(x) (over the empty set in T′) such that for every M ⊧ T′, M = acl_{M}(ϕ(M)).

We describe a technical condition on M ⊂ N models of a theory T which guarantees that M ≺ N. Recall that a definable subset X of N is minimal in N if every subset of X, that is definable with parameters in N is finite or cofinite. And X is strongly minimal if this condition remains true when parameters from an elementary extension of N are allowed.

Theorem 1.3 Let T = Th(N) and suppose there is an e ∈ N and an existential formula ϕ(x, e) such that ϕ(x, e) is minimal in N and acl_{N}(ϕ(N, e)) = N. If M ⊆ N is a model of T that satisfies: a) acl_{N}(M) = M, b) e ∈ M and c) ϕ(N, e) ∩ M is infinite then M ≺ N.

Proof. Applying the Tarski-Vaught test we fix a formula ψ(x, c) with c ∈ M that has a solution in N and show it has a solution in M. Let r ≥ 0 be least so that there is an r-tuple d from ϕ(N, e) such that ψ(N, c) ∩ acl_{N}(Md) ≠ ∅. If r = 0, we are done. If not, choose θ(v, y_{1}, … y_{r}) such that for some n < ω,

T ⊧ (∀y)(∃^{<m}v)θ(v, y)

and

N ⊧ (∃v)(∃y)(θ(v, y) ∧ ψ(v, c) ∧ ⋀_{1≤i≤r} ϕ(y_{i}, e)).

Consider the formula

θ′(y_{1}) := (∃v)(∃y_{2}, …, y_{r})[θ(v, y_{1}, …, y_{r}) ∧ ψ(v, c) ∧ ϕ(y_{1}, e)],

which has parameters in M. Then θ′(y_{1}) has a solution in M. (If θ′ is algebraic, this follows by the definition of algebraic closure; if not θ′(N) is cofinite in ϕ(x, e) (by minimality). Since ϕ(N, e) ∩ M is infinite, θ′ has a solution in M.) But if e_{1} is a solution of θ′ in M, for some e_{2}, …, e_{r} ∈ N,

ψ(N, c) ∩ acl_{N}(Me_{2}, …, e_{r}) = ψ(N, c) ∩ acl_{N}(Me_{1}, e_{2}, …, e_{r}) ≠ ∅,

contradicting the minimality of r. □_{1.3} Lemma 1.4 Suppose a countable saturated model N and formula ϕ(x, e) satisfies the hypothesis in the first sentence of Theorem 1.3 and for every M ⊧ T with M ⊆ N, acl_{N}(M) = M. Suppose further that e realises a principal type. Then the theory T′ = Th(M, e) is model complete and witnesses that T is almost strong minimal.

Proof. Consider a pair M_{1}, M_{2} of countable models, M_{1} ⊆ M_{2} ⊧ T′. We want to show M_{1} ≺ M_{2}. Since N is saturated, M_{2} can be elementarily embedded in N. So it suffices to show that any substructure M of (N, e) that satisfies T′ is an elementary submodel. Condition a) of Theorem 1.3 is part of our hypothesis; condition b) holds since e realises a principal type. For condition c) note that since T is complete and e realises a principal type, ϕ(M, e) is infinite in the sense of M; since ϕ(x, e) is existential, this implies ϕ(N, e) ∩ M is infinite. The almost strong minimality is automatic since N is saturated. □_{1.4}

The most trivial example shows that in general it is necessary to pass to T′. Consider the theory of (ω, S). Of course, if the universe is the algebraic closure with no new parameters of the strongly minimal set, which itself is defined without parameters, the original theory T is model complete.

2 Expansions of strongly minimal sets

In this section we contrast the non-model completeness of the infinite rank bicolored fields with the model completeness of the finite rank case. In fact, our arguments show arbitrary unary expansions (by the Hrushovski construction with μ) of sufficiently well-behaved strongly minimal sets are almost strongly minimal without parameters. Thus, we extend the model completeness from bicolored fields to a more general setting.

We will consider expansions of a strongly minimal set (in a language denoted L_{f}) by a unary predicate P (to form the language L); we say the points satisfying P are black. The following notations summarize the notions used below; details and justifications for these definitions are in [4, 5, 6]. Recall that 𝔾 denotes the generic model for the relevant case and is ω-saturated.

Notation 2.1 1. The base theory T_{f} in the language L_{f} admits elimination of quantifiers, elimination of imaginaries and has the definable multiplicity property.

2. δ(x) = δ_{k}(x) = k · R_{M}(x) − |P (x)|; for X ⊂ N, d_{N}(X) = inf{δ(X′) : X ⊆ X′ ⊂_{ω} N}, where R_{M} is Morley rank.

3. \overline{K}_{0} is the class of models of T_{0} that have nonnegative dimension relative to δ_{k}(x). We write T_{k}^{ω} for the theory of the generic of \overline{K}_{0}.

4. \overline{K}_{0}^{μ} is the members of \overline{K}_{0} in which the number of realizations of each primitive are bounded by a finite-to-one function μ as in Definition 2.9 of [4]. We write T_{k}^{μ} for the theory of the generic in rank k.

We assume familiarity with the basic properties of these constructions and proceed directly to the new results. In particular, we frequently use

Fact 2.2 Every member of \overline{K}_{0} (of \overline{K}_{0}^{μ}) can be strongly embedded in the generic model 𝔾 for \overline{K}_{0} (for \overline{K}_{0}^{μ}).

If M is in \overline{K}_{0} and c realizes a complete L_{f}-type over M, we denote by M[c] the structure whose universe is the L_{f}-algebraic closure of Mc and whose only black points are in Mc.

We now show that the infinite rank bicolored field fails to be model complete. Thus, it provides a somewhat less contrived example than Lindstrom’s original one [11] of a theory which is ∀∃-axiomatizable but not model complete. In fact, the argument extends to unary expansions of any strongly minimal set in which singletons have infinite algebraic closure.

Theorem 2.3 Let \overline{K}_{0} be the class of countable bicolored fields with nonnegative dimension relative to δ(x) = k × R_{M}(x) − |P (x)|. T_{k}^{ω} is not model complete.

Proof. By algebraic we mean ‘L_{f}-algebraic’. Let k_{0} be the algebraic closure of a point a_{1} that is not algebraic and satisfies {a_{1}} ≤ k_{0}. Let M_{0} be a countable model of T_{k}^{ω} with k_{0} ≤ M_{0}. Let ϕ(x, y) be a formula which asserts that k + 1 elements are pairwise algebraic over y and distinct without implying that any of the elements are algebraic over y. Let ⟨b_{0}, b_{1}, …, b_{k}⟩ be a sequence of black points that satisfy ϕ(b, a_{1}). So δ(b/k_{0}) < 0. Embed M_{0}[b_{0}, b_{1}, …, b_{k}] in 𝔾 ⊧ T_{k}^{ω} by Fact 2.2. Then M_{0} is a submodel of 𝔾 but not an elementary submodel because there is no k + 1-tuple of distinct black points in M_{0} satisfying ϕ(x_{0}, x_{1}, …, x_{k}; a_{1}) as k_{0} ≤ M_{0}. □_{2.3}

In contrast, we show that for each k the theory T_{k}^{μ} of a rank k unary expansion of a strongly minimal set [6] that satisfies Assumption 2.11 is model complete. For this, we use freely the ‘code notation’ described in [4]; this includes formulas such as θc, ϕc.

Notation 2.4 For N ⊧ T_{k}^{μ} and b ∈ N,

1. tp_{N}(b) denotes the set of parameter-free L-formulas ψ(x) such that N ⊧ ψ(b).

2. Diag(b) denotes the set of parameter free L_{f}-formulas ψ(x) such that N ⊧ ψ(b). We need no subscript N because we have assumed that T_{f} admits elimination of quantifiers.

3. Following [4], we denote by I(y) a collection of universal L-formulas such that for any N ∈ \overline{K}_{0} and b ∈ N, if N ⊧ I(b) then b ≤ N.

4. Let c be a primitive code and suppose N ⊧ θc(b′) and b′ ⊂ b ⊂ N. We write χc(b) = k to denote a first order formula that holds in N if the cardinality of a maximal set in N of pairwise disjoint solutions (each disjoint from b) of ϕc(x, b′) is k.

The next few lemmas show that if M ⊂ N are models of T_{k}^{μ} then M is strong in N; indeed, M is d-closed in N (i.e. if a ∈ N, X ⊂ M and d_{N}(a/X) = 0 then a ∈ M).

Lemma 2.5 Let b ≤ N ⊧ T_{k}^{μ}. Then

T_{k}^{μ} ∪ I(y) ∪ Diag(b) ⊧ tp_{N}(b).

Proof. By saturation of 𝔾, tp_{N}(b) is realized in 𝔾 by some b′. For some M ⊧ T_{k}^{μ} let c ∈ M ⊧ T_{k}^{μ} satisfy I(y)∪Diag(b) (in the sense of M). Then tp_{M}(c) is realized in 𝔾 by some c′. But c′ and b′ are automorphic in 𝔾 by genericity. So tp_{N}(b) = tp𝔾(b′) = tp𝔾(c′) = tp_{M}(c), as required. □_{2.5}

Lemma 2.6 If M ≤ N are models of T_{k}^{μ} there is no a ∈ N − M which is primitive over M. Thus, M is d-closed in N.

Proof. Fix a primitive code c and b′ ⊂ M such that θc(b′). Let b be the intrinsic closure of b′ in M (hence in N, since M ≤ N). There is a maximal r such that M ⊧ χc(b) = r, witnessed, say, by a_{1}, …, a_{r}. By Lemma 2.5, N ⊧ χc(b) = r. Therefore ϕ(x, b′) is not realized in N − M since any realization a_{r+1} would be disjoint from a_{1}, …, a_{r}, b and so contradict the definition of χc .

□_{2.6}

Remark 2.7 Let 𝔾 be generic for T_{k}^{μ}. The definition of genericity yields immediately that for aX ⊂ 𝔾, d𝔾(a/X) = 0 if and only if a ∈ acl𝔾(X). For this, recall that if d𝔾(a/X) > 0, then a has infinitely many conjugates over X in 𝔾.

Lemma 2.8 Let M ⊂ N be countable models of T_{k}^{μ}. Then M ≤ N. Moreover, if M ⊂ 𝔾 then acl𝔾(M) = M.

Proof. Suppose for the sake of contradiction that M ≰ N. Let A ⊂ N − M be minimal with respect to inclusion so that δ(A/M) < 0. Necessarily, all elements of A are black. Let ℓ be the transcendence degree of A over M. Since M is L_{f}-algebraically closed, ℓ > 0. Then,

k · ℓ − |A| = δ(A/M) < 0.

Choose a from A of length k · ℓ that extends a transcendence basis for A over M. Then δ(a/M) = 0 and M ≤ Ma so a contains a primitive b over M. But M[b] imbeds strongly into 𝔾, contradicting Lemma 2.6 (with 𝔾 as N and M as M).

Now suppose M ⊂ 𝔾. We have just seen M ≤ 𝔾; whence by Lemma 2.6, M is d-closed in 𝔾. By Remark 2.7, acl𝔾(M) = M. □_{2.8}

Since it follows easily from Zilber’s Irreducibility Lemma (Proposition 2.12 of [13]) that finite rank fields are almost strongly minimal, we could conclude that the relevant T′ is model complete. However, we have a stronger result.

We generalize to strongly minimal sets a property that the formula x_{1} + … + x_{k} = 0 has in either vector spaces or algebraically closed fields.

Definition 2.9 A formula ϕ(x_{1}, …, x_{k}) has exactly rank k −1 if for every generic (over the parameters of ϕ) solution a = ⟨a_{1}, …, a_{k}⟩ of ϕ(x_{1}, …, x_{k}), R_{M}(a) = k − 1 and any proper subsequence of a is independent.

Note that ϕ is exactly rank k, just if for any generic solution a of ϕ, a subset of a is independent if and only if it has at most k-elements: i.e. the sequence is exactly kindependent.

Remark 2.10 Note that the k-ary ϕ(x) has exactly rank k − 1 if and only if for any subsequence x′ of x with length r < k, and any ψ(x′) with Morley rank less than r,

R_{M}(ψ(x′) ∧ ϕ(x)) < k − 1.

That is, ψ is not satisfied by a generic solution of ϕ.

We augment our requirement on the underlying theory T_{f} of a strongly minimal set by requiring that exactly rank k formulas are dense in the following sense.

Assumption 2.11 The underlying theory T_{f} satisfies the following condition: If ψ_{i}(x, y) for i < m are a finite set of k +1-ary formulas such that for some g, for each i < m, ψ_{i}(x, g) has rank at most k − 1, there is a formula ϕ(x, y) such that ϕ(x, g) has exactly rank k − 1 and for each i < m,

R_{M}(ϕ(x, g) ∧ ψ_{i}(x, g)) < k − 1.

Remark 2.12 In either vector spaces or algebraically closed fields the formula x_{1} + … + x_{k} +y +z = 0 gives us (as we fix g for y and substitute various elements e of the prime model for z) a family of disjoint exactly rank k formulas. Any theory of a strongly minimal set with such a disjoint family ϕ(x, y) (or more weakly with R_{M}(ϕ(x, a_{i}) ∧ ϕ(x, a_{j})) < k − 1 if i ≠ j) satisfies Assumption 2.11. For example, in vector spaces, for any g and ψ_{i}(x, y) for i < m there is an e in the prime model such that R_{M}(ψ_{i}(x, g) ∧ x_{1} + … + x_{k} + g + e = 0) < k − 1.

Note that trivial strongly minimal sets do not have exactly rank k formulas for k > 2. It is not hard to check that some structures constructed by the Hrushovski method (e.g. the original strongly minimal set) do have exactly rank k formulas in k + 1 variables for every k. The construction of a bicolored field that is not ω-stable (although built by the Hrushovski construction) in [4] used essentially the fact that in algebraically closed fields for m ≤ n there are exactly rank m formulas in n variables.

Theorem 2.13 Let \overline{K}_{0}^{μ} be the class of those models of a well-behaved L_{f}-strongly minimal theory as specified in paragraph 2.1 and satisfying Assumption 2.11. There is an existential L-strongly minimal formula λ(x) over the empty set such that the generic model satisfies 𝔾 = acl𝔾(λ(𝔾)).

Thus, since 𝔾 is satuated, the theory, T_{k}^{μ}, of the generic model is almost strongly minimal without naming parameters, i.e. with itself as the required T′.

Proof. Choose any L_{f}-formula ρ(x) which asserts that k − 1 elements are pairwise algebraic and distinct without implying that any of the elements are algebraic; thus ρ(x) has infinitely many solutions. Then any a that is L_{f}-generic for ρ(x) ∧ ⋀_{i<k} P (x_{i}) is minimal strong over the empty set with δ(a/∅) = 1. Now, λ(x) := (∃x′)ρ(x, x′) is L-strongly minimal (where x = xx′). To see this just note that in 𝔾 for any a ∈ 𝔾, each b ∈ λ(𝔾) is either algebraic over a (if d𝔾(b/a) = 0) or is in the infinite orbit of those elements in λ(𝔾) with d𝔾(b/a) = 1. This gives minimality; strong minimality follows since 𝔾 is saturated.

Now we show each element of 𝔾 is in acl(λ(𝔾)). Let g be an arbitrary element of 𝔾 and let G = icl𝔾(g). (Recall [4] that icl𝔾(g) is the least subset of 𝔾 containing g which is strong in 𝔾.) Let b_{i} for i < k be k independent (over G) black realizations of ρ. Write a_{i} for the first element of b_{i}. Now each b_{i} is contained in a member of \overline{K}_{0}^{μ} since δ(b_{i}) = 1 and b_{i} contains no primitive pairs. The only primitive pairs in the free amalgam of two finitely generated structures X_{1}, X_{2} are those in one of the X_{i}. Let B denote the free union of the b_{i}, B ∈ \overline{K}_{0}^{μ}; write BG for the free amalgam of B and G. Since no primitive pair is embeddable in any of the b_{i} and G is embeddable in a member of \overline{K}_{0}^{μ}, BG is embeddable in a member of \overline{K}_{0}^{μ}. Let w_{1}, …, w_{k−1}v = wv be an enumeration of variables for the elements of BG and also let u_{i} (as the first element of the sequence w_{i}) stand for a_{i}. Let a = ⟨a_{1}, … a_{k−1}⟩ and u = ⟨u_{1}, … u_{k−1}⟩. Since each b_{i} is in acl(a_{i}) and since we will be concerned only with realizations of the diagram of ag that are independent from 𝔾 over g, we need only to control the L_{f}-dimensions of subsets of ag. Note that B has transcendence degree k (over both G and ∅) and has (k − 1) · k elements which are all black; so δ(B/G) = k · k − k · (k − 1) = k. We want to choose an additional formula ϕ(u, y) so that if B′ is a solution of ϕ(u, g) ∧ ⋀_{i<k} ρ_{i}(w_{i}) containing a, and B′ is independent from 𝔾 over g, then 𝔾[B′] is a primitive extension of 𝔾 that is in \overline{K}_{0}^{μ}. If we choose ϕ(u, y) to be exactly rank k then a′_{0}, …, a′_{k−1} is exactly k − 1 independent over g and this guarantees the primitivity. In particular, δ(B′/G) = k · (k − 1) − k · (k − 1) = 0.

Now, possibly refining our choice of ϕ, we ensure 𝔾[B′] is in \overline{K}_{0}^{μ}. Since μ is finite-to-one and BG is finite, there are only finitely many primitive codes d so that more than μ(d) realizations of d can occur in some set with the same cardinality as BG. Each possible arrangement σ of μ(d)+1 realizations of d in BG is described by a formula ψ_{d,σ} on a subset of the variables wv. Since we are concerned only with solutions B′ which are independent from 𝔾 over g we may restrict to formulas of the form: ψ_{d,σ}(u′, v) with u′ a subsequence of u. For each d, σ, R𝔾(ψ_{d,σ}(u′, g)) < lg(u′), since if a realization of ψ_{d,σ}(u′, g)) were independent from g and violated μ, BG would violate μ, contrary to hypothesis. If for some d, σ, lg(u′) < k − 1, ψ_{d,σ}(u′, g) is not satisfied by a generic solution of ϕ(u, b), lest the fact that ϕ(u, g) has exactly rank k − 1 be violated. (See Remark 2.10.) So without loss of generality, each ψ_{d,σ}(u, y) is k + 1-ary. It suffices to choose ϕ(u, y) so that ϕ(u, y) is exactly rank k and for each d, σ,

R𝔾(ϕ(u, g) ∧ ψ_{d,σ}(u, g)) < k − 1.

Assumption 2.11 guarantees we can choose such a ϕ. So if B′ is a generic solution of ϕ(u, g), 𝔾[B′] is a primitive extension of 𝔾, which is in \overline{K}_{0}^{μ}. Since 𝔾 ∈ \overline{K}_{0}^{μ}, 𝔾 ≤ 𝔾[B′] and 𝔾 is d-closed in all strong extensions, ϕ(u, g) ∧ ∧_{i<k}ρ_{i}(w_{i}) can be realized in 𝔾 by some a′_{i}. The a′_{i} are k independent solutions of λ and g ∈ acl_{L_{f}} (a′_{0}, …, a′_{k−1}) as required. □_{2.13}

Theorem 2.14 If T_{f} satisfies 2.1 and satisfies Assumption 2.11 then T_{k}^{μ} is model complete. In particular, the rank k bicolored fields are model complete.

Proof. In the general case apply Theorem 1.3, Lemma 2.8, and Lemma 2.13. Remark 2.12 guarantees the application to bicolored fields. Note that we don’t need T′ since we showed almost strong minimality without adding parameters. □_{2.14}

3 The almost strongly minimal projective plane

In this section we show that the almost strongly minimal projective plane of [2] has a principal extension which is model complete. The argument is an elaboration of Holland’s argument in [9] that the ab initio strongly minimal Hrushovski examples are model complete. The two innovations are the extension from rank 1 to rank 2 and the use of an extension by constants.

The first part of the argument, through Lemma 3.8, will work for any ab initio example. For concreteness, we work with the rank 2 case.

Fix a finite relational language L. If X and Y are L-structures, we write X ⊆ Y to indicate X is a substructure of Y. In agreement with current terminology we replace the y of [2] by δ. We depend heavily on the development in [2] and [9]. In particular, for the projective plane, L contains a single binary relation which is constrained to be symmetric and irreflexive.

Definition 3.1 Let M be an L-structure. For X ⊆_{ω} M, r(X) is the number of (unordered) tuples \overline{a} from X such that M ⊧ R(\overline{a}) for some R in L. Let

δ(X) = 2|X| − r(X).

Primitive pairs are easy to define in this ab initio context.

Definition 3.2 1. X is primitive over Y if δ(X/Y) = 0 and for every proper subset X′ of X, δ(X′/Y) > 0.

2. The pair (X, Y) is a minimal primitive pair if X is primitive over Y and X is not primitive over any proper subset of Y.

If X is primitive over M then there is a unique smallest Y ⊆_{ω} M such that the pair (X, Y) is minimal primitive (take Y = {x ∈ M : R ∩ ((XM)^{n} − M^{n}) ⊈ R ∩ (XM − {x})^{n} for some n-ary R ∈ L}).

Notation 3.3 On page 701 of [2] we constructed arbitrarily large primitives over the empty set such that each primitive A contains three discrete points and four points so that no three are connected to a common point in A. Fix such a primitive A and let n be its cardinality.

For any finite set G, At_{G}(x) is the formula expressing the atomic diagram of G. We write AT_{(P,G)}(v, x) for the atomic diagram of P G where (P, G) is a primitive pair.

Definition 3.4 Let T^{μ} be a collection of (universal) sentences, in the vocabulary of one binary relation symbol R and constant symbols {a_{0}, …, a_{n−1}}, ensuring the following.

1. δ(X) ≥ 0 for all finite X.

2. Fix a set A = {a_{0}, …, a_{n−1}} (whose existence is guaranteed by the previous paragraph) that is primitive over the empty set and such that a_{0}, a_{1}, a_{2} have no edges between them and no three of a_{3}, …, a_{n−1} are connected to a common point in A. Add an axiom saying the constants {a_{0}, …, a_{n−1}} form a structure isomorphic to this primitive structure A.

3. There is no 4-cycle in any model of T^{μ}.

4. Fix a function μ from (isomorphism types of) minimal primitive pairs (X, Y) into ℕ with μ((X, Y)) ≥ δ(Y). For each pair (X, Y), the sentence

∀Y′∀X_{1}, …, X_{μ(X,Y)+1} ⋀_{i} At_{(X,Y)}(X_{i}, Y′) → ⋁_{i≠j} X_{i} ∩ X_{j} ≠ ∅.

We write K = Mod(T^{μ}); \overline{K}_{0}^{μ} would closer to our usage in Section 2 but since we are dealing only with the finite rank case here, we suppress the parameters.

We use the formulation of the ‘strong amalgamation lemma’ from [9].

Lemma 3.5 Let B_{1}B_{2} be a free amalgam of B_{1} and B_{2} over B_{0} = B_{1}∩B_{2}, where B_{1}, B_{2} ∈ K and B_{1} − B_{0} is primitive over B_{0}. Suppose that (Q, F) is a minimal primitive pair with F ⊆ B_{1}B_{2} and that ℙ is a collection of μ(Q, F) + 1 pairwise disjoint copies of Q over F in B_{1}B_{2}. Then the following hold.

1. F ⊆ B_{1} and some element P of ℙ is contained in B_{1} − B_{0}.

2. If B_{0} ≤ B_{2}, then F ⊆ B_{0} and B_{1} − B_{0} = P.

For each N ∈ K, we modify δ by defining for any finite X ⊂ N, d_{N}(X) = min{δ(X′) : X ⊆ X′ ⊂_{ω} N}. As usual [7] for any finite X ⊂ Y ⊂ N, d_{N}(X) ≤ d_{N}(Y) and d_{N} is lower semimodular: d_{N}(XY) + d_{N}(X ∩ Y) ≤ d_{N}(X) + d_{N}(Y). Denote d_{N}(XY) − d_{N}(Y) by d_{N}(X/Y) for finite X, Y and d_{N}(X/Y) = inf{d_{N}(X/Y_{0}) : Y_{0} ⊂_{ω} Y } for finite X and infinite Y. Then we can define a closure relation by a ∈ cl_{N}(X) if d_{N}(a/X) = 0. We call this relation d-closure. Note that the relation does not define a geometry as exchange fails.

Notation 3.6 Let K = Mod(T^{μ}) and let K^{∗} denote the collection of M ∈ K such that if M ≤ N ∈ K, then for all a ∈ N − M, d_{N}(a/M) > 0. If M ∈ K^{∗}, we say M is d-closed in every strong extension in K.

Now, using Lemma 3.5, we produce a ∀∃ axiomatization of T h(K^{∗}); we show this theory is consistent and ℵ_{1}-categorical. Thus, it is complete by the Loś-Vaught test and model complete by Lindstrom’s theorem. Let φ_{(P,G)}(\overline{x}) be a formula such that if M ⊧ At_{G}(g) and if M[P′] is an extension obtained by realizing AT_{(P,G)}(v, g) by a P′ free from M over g then M ⊧ φ_{(P,G)}(g) if and only if for some minimal primitive pair (Q, F) with QF ⊆ P′g, Q is realized too many times (i.e. at least μ(Q, F) + 1 times) over F in M[P′]. More formally, fix (P, G) and (Q, F), minimal primitive pairs, with QF ⊆ P G. Let \overline{g}, \overline{q}, \overline{p} and \overline{f} enumerate G, Q, P and F, respectively. Suppose that \overline{q}_{1}, …, \overline{q}_{r} are r = μ(Q, F) + 1 pairwise disjoint copies of \overline{q} over \overline{f} in some free amalgam P M of P G with an element M of K over G. Let \overline{s} enumerate ⋃ rng\{\overline{q}_{i}\} − P and let C(\overline{v}; \overline{y}) be the atomic type of \overline{s}\overline{g}. Note that there are only finitely many possibilities for C. Let φ_{(P,G),(Q,F)}(\overline{x}) be the disjunction over all such C of the formulas ∃\overline{v}C(\overline{v}; \overline{x}). For each minimally primitive pair (P, G) whose atomic type is realized in an element of K, φ_{(P,G)}(x) denotes the formula:

At_{G}(\overline{x}) → ⋁ φ_{(P,G),(Q,F)}(x),

where for fixed (P, G), the disjunction ranges over all minimally primitive pairs (Q, F) contained in P G. Note these axioms are ∀∃.

Definition 3.7 Let T^{∗} denote the union of T^{μ} with the collection of all sentences (∀x)φ_{(P,G)}(x).

Lemma 3.8 T^{∗} axiomatizes K^{∗}.

Proof. If M ⊧ T^{∗} then M ∈ K^{∗} since if M has a proper primitive extension M[P] ∈ K (for some minimal primitive pair (P, G)) then some (Q, F) violates μ in M[P] by the definition of T^{∗}, contradicting M[P] ∈ K. Conversely, if M |̸= T^{∗}, for some (P, G) and g ∈ M, M ⊧ ¬φ_{(P,G)}(g). Then if M ⊧ AT_{G}(g) and P′ is a free realization of (P, G) over M, M[P′] ∈ K. But M ≤ M[P′] so M ∉ K^{∗}. □_{3.8}

Now we have two further properties of d-closure. Recall that we have constants for the elements of A in the language.

Lemma 3.9 1. If X ≤ M ∈ K^{∗} and Y ≤ N ∈ K^{∗} and f is an isomorphism from X onto Y then f extends to an isomorphism from cl_{M}(X) onto cl_{N}(Y).

2. If X ≤ M ∈ K^{∗}, cl_{M}(X) ⊆ acl_{M}(X).

Proof. 1) First consider P contained in M which is primitive over X. So XP ∈ K. There is a copy P′Y of P X, so that P′ is primitive over Y and Y P′ ∈ K. Now by Lemma 3.5, either there is an embedding of P′ into N over Y or NP′ ∈ K. But the second case is impossible since N ∈ K^{∗}. With this base step in mind it is easy to construct the isomorphism by a back and forth.

2) The use of μ shows that if X ≤ M, XP ⊂ M and d_{M}(P/X) = 0, there are only finitely many copies of P over X in M so P ⊆ acl_{M}(X). □_{3.9}

In this context, we require a slight variant on Fact 2.2, which can be proved by amalgamation and taking unions of chains. Note that the existence of a function μ guaranteeing that there are only a finite number of solutions for each primitive is essential for this version.

Lemma 3.10 Each member of K can be strongly embedded in a member of K^{∗}.

To interpret the models of T^{∗} as planes, regard each point of M as both a point and a line. Interpret R(a, b) to mean both the point a is on the line b and the point b is on the line a. Thus there is a built in polarity mapping a point a to the line Rxa. The following lemma implies that any model M of T^{∗} is a projective plane under this interpretation. (The third projective plane axiom, that every pair of points lie on a unique line, follows from the first by the duality in the definition of the plane.)

Lemma 3.11 The theory T^{∗} implies the following.

1. Any two lines intersect in a unique point.

2. There are four points with no three lying on a line.

Proof. If two lines intersected in more than one point there would be a square. But for any two points a, b ∈ M, adding a point c related to both is a primitive extension. By Lemma 3.5, either such c exists in M or in some strong extension. But M is d-closed in any strong extension, so there is such a c ∈ M. Every N ⊧ T^{∗} is a strong extension of a copy of the primitive A, described in Definition 3.4. Condition 2) is witnessed in N by elements of this copy of A. □_{3.11}

In any projective plane, given any line ℓ and two points a, b not on ℓ, the entire plane is in dcl(ℓ, a, b). Thus, in any infinite plane, any line has the same cardinality as the plane.

In this next lemma we write Rxa_{0} for the set of points in the ambient structure N which are R-related to a_{0}. We complete the proof by showing:

Theorem 3.12 T^{∗} is ℵ_{1}-categorical; thus complete and model complete.

Proof. Let N ⊧ T^{∗}. The formula Rxa_{0} defines a line in the projective plane. Since Rba_{0} implies d_{N}(b/a_{0}) ≤ 1, taking for X ⊂ Rxa_{0} the closure of X as cl_{N}(XA) ∩ Rxa_{0} = cl_{N}(Xa_{0}) ∩ Rxa_{0} defines a geometry on the line Rxa_{0}. I.e., exchange holds on the line. More specifically, the restriction satisfies all the axioms of Fact 2 of [9]. Suppose (M, A), (M′, A′) are models of T^{∗} with cardinality ℵ_{1}. Since each line has the same cardinality as the universe, and any infinite set X has the same cardinality as its d-closure, there is a 1-1 correspondence between the bases X, Y for the lines Rxa_{0} and Rxa′_{0}. Note that the only edges between X and A (respectively Y and A′) are the edges between a_{0} (a′_{0}) and each point of X (Y). Moreover, A and A′ are isomorphic, so there is an isomorphism f between AX and A′Y. Note that in general if A ≤ M and X is independent over A, AX ≤ M. In particular, AX ≤ M, AY ≤ M′. By Lemma 3.9 1) f extends to an isomorphism of cl_{M}(XA) and cl_{M′}(YA′). But cl_{M}(XA) = M. To see this suppose b ∈ M − cl_{M}(XA). Note first that since X is a basis for the geometry on Rxa_{0}, every element of the line {x : Rxa_{0}} is in cl_{M}(XA). If b is not on the line through a_{1}a_{2}, there is a line through a_{1}b which intersects the line a_{0} in b′ and a line through a_{2}b which intersects the line a_{0} in b′′. Now these lines are {x : Rxc_{1}} and {x : Rxc_{2}} for some c_{1}, c_{2}, so d_{M}(b/c_{1}c_{2}) = 0. But c_{1}, c_{2} must be in cl_{M}(XA) since the line through a_{0}b′ (respectively a_{0}b′′) is fixed setwise by every automorphism which fixes AX. Then b ∈ cl_{M}(XA) as required. (A slight elaboration of this argument handles the case where b is on the line a_{1}a_{2}.)

Completeness is immediate by the Ĺos-Vaught test and model completeness follows since the axioms for T^{∗} are ∀∃. □_{3.12}

4 Context and Further Problems

In the wake of Lindstrom’s proof that a categorical ∀∃ theory is model complete, there was speculation that categoricity would imply some approximation to model completeness. The results of Ahrbrandt-Baldwin [1] and [12], mentioned in the introduction, describe the totally categorical case. We have taken two different approaches here to show that a large family of examples are model complete. For the bicolored field case, we have used the known complete theory and proved it is model complete. In the projective plane case, we extended the language by constants, introduced a new ∀∃ axiomatization, and proved it was categorical.

Recent work shows the importance of geometrical considerations when considering the relation between model completeness and ℵ_{1}-categoricity. Goncharov, Harizanov, Laskowski, Lempp, and McCoy [8] show that if a strongly minimal set has a trivial geometry then an extension by naming (possibly) infinitely many constants is model complete.

Our work is different in several respects. First, we are dealing with the family of examples generated by the Hrushovski construction. In particular, we are looking at expansions of strongly minimal sets. Second, the geometric condition we require is one of sufficient complexity, not of triviality. Further investigation is needed on the following questions.

Question 4.1 What strongly minimal sets have (uniform families of) formulas with exactly rank k?

We have some preliminary results on this issue. We used formulas with exactly rank k earlier [4] to show that the ”finite-to-one” requirement is necessary to construct ℵ_{1}-categorical bicolored fields. In particular one might ask.

Question 4.2 Must every nontrivial strongly minimal set have formulas of exact rank k for each k?

In Section 3 we added constants to find a model complete theory.

Question 4.3 Is some (any) projective plane constructed in this way model complete in the language of projective planes without constants?

The theory of the projective place described above is almost strongly minimal via the constants a_{0}, a_{1}, a_{2}. Note however that a_{1}, a_{2} are algebraic over the empty set (since A was chosen primitive). Thus the plane is actually algebraic over the line Rxa_{0}. In [3], we constructed a plane which is the definable closure of any line. But in that case there were no algebraic points.

Question 4.4 Is every projective plane with a built-in polarity as described after Lemma 3.10 or in [3] necessarily the definable closure of a line?

References

[1] G. Ahlbrandt and Baldwin J.T. Categoricity and generalized model completeness. Z. Math. Logik Grundlag. Math., pages 1–4, 1988.

[2] J.T. Baldwin. An almost strongly minimal non-desarguesian projective plane. Transactions of the American Mathematical Society, 342:695–711, 1994.

[3] J.T. Baldwin. Some projective planes of Lenz Barlotti class I. Proceedings of the A.M.S., 123:251–256, 1995.

[4] J.T. Baldwin and K. Holland. Constructing ω-stable structures: Rank 2 fields. Journal of Symbolic Logic, 65:371–391, 2000.

[5] J.T. Baldwin and K. Holland. Constructing ω-stable structures: Computing rank. Fundamenta Mathematica, 170, 2001.

[6] J.T. Baldwin and K. Holland. Constructing ω-stable structures: Rank k. Notre Dame Journal of Formal logic, 2001. to appear.

[7] J.T. Baldwin and Niandong Shi. Stable generic structures. Annals of Pure and Applied Logic, 79:1–35, 1996.

[8] Goncharov, Harizanov, Laskowski, Lempp, and McCoy. Trivial strongly minimal sets are model complete are naming constants. preprint, 2003.

[9] Kitty Holland. Model completeness of the new strongly minimal sets. J. Symbolic Logic, 64:946–962, 1999.

[10] E. Hrushovski. A new strongly minimal set. Annals of Pure and Applied Logic, 62:147– 166, 1993.

[11] P. Lindstrom. On model completeness. Theoria, 30:183–196, 1964.

[12] D. Marker. Non-Σ_{n}-axiomatizable almost strongly minimal theories. J. Symbolic Logic, 54:921–927, 1989.

[13] Bruno Poizat. Groupes Stables. Nur Al-mantiq Wal-ma’rifah, 82, Rue Racine 69100 Villeurbanne France, 1987.

[14] Bruno Poizat. Le carré de l’egalité. The Journal of Symbolic Logic, 64:1339–1356, 1999.