PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 82(96) (2007), 79–83 DOI 102298/PIM0796079T

SOME QUESTIONS CONCERNING MINIMAL STRUCTURES

Predrag Tanović

Abstract. An infinite first-order structure is minimal if its each definable subset is either finite or co-finite. We formulate three questions concerning order properties of minimal structures which are motivated by Pillay’s Conjecture (stating that a countable first-order structure must have infinitely many countable, pairwise non-isomorphic elementary extensions).

In this article a connection between articles [7] and [8] is explained in order to motivate some questions concerning minimal, first-order structures which I could not answer. On the way, a minor gap which appeared in [8] will be fixed; thanks to Enrique Casanovas for pointing it out to me.

The original motivation for this work comes from Pillay’s work on countable elementary extensions of first-order structures. If 𝕄_{0} = (M_{0}, …) is a countable first-order structure and 𝕄_{0} ≺ 𝕄_{1}, 𝕄_{0} ≺ 𝕄_{2} then we say that 𝕄_{1} and 𝕄_{2} are isomorphic over 𝕄_{0} if there is an isomorphism between them fixing M_{0} pointwise.

Pillay’s Conjecture. Any countable first-order structure 𝕄_{0} has infinitely many countable elementary extensions which are pairwise non-isomorphic over 𝕄_{0}.

There are a few results partially confirming Pillay’s Conjecture. The initial result of Pillay’s is in [3] where he proved that there are at least four nonisomorphic countable elementary extensions of 𝕄_{0}. There he also reduces the general case to the case when 𝕄_{0} is minimal and has small theory (|S(M_{0})| = ℵ_{0}); recall that an infinite first-order structure is minimal if its each definable (possibly with parameters) subset is either finite or co-finite. By a well known result of Baldwin and Lachlan, see [1], any countable strongly minimal structure has infinitely many countable pairwise non-isomorphic elementary extensions, so the conjecture is true for strongly minimal structures (a minimal structure is strongly minimal if the minimality is preserved in all elementarily equivalent structures). Belegradek in [2] found a pattern for constructing minimal, but not strongly minimal structures; other examples of such structures are (ω, <) and (ω + ω^{∗}, <) (where ω^{∗} is reversely ordered ω).

2000 Mathematics Subject Classification: Primary 03C15.

Supported by Ministry of Science of Serbia.

Recall that 𝕄_{0} has the order property if for some n ⩾ 1 there is an infinite (but not necessarily definable) {ā_{i} | i ∈ ω} ⊂ M_{0}^{n} which can be ordered by a formula, i.e., for some ϕ(x̄, ȳ) and all i, j ∈ ω we have 𝕄_{0} ⊨ ϕ(ā_{i}, ā_{j}) iff i < j (here we allow ϕ to have parameters from M_{0}). We will say that 𝕄_{0} = (M_{0}, …) is ordered if there is a binary relation < on M_{0}, which is definable (possibly with parameters from M_{0}), irreflexive, transitive and has an infinite chain. 𝕄_{0} has the strict order property if 𝕄_{0}^{n} is ordered for some n ∈ ω; Th(𝕄_{0}) has the strict order property if there is an elementary extension of 𝕄_{0} having the strict order property.

In [4] Pillay proved that the conjecture is true when 𝕄_{0} = (M_{0}, …) does not have the order property, and in [7] the conjecture is verified for the case when Th(𝕄_{0}) does not have the strict order property. It is clear that the later result partially overlaps Pillay’s result, we don’t know if it completely does. More precisely, it is well known that there are first-order structures (like simple, unstable ones) having the order property but whose elementary diagram does not have the strict order property. Still we don’t know if there is such a minimal structure:

Question 1. Is there a minimal structure with small theory which has the order property but whose elementary diagram does not have the strict order property?

In [5] Pillay and Kim found an example of a minimal structure with small theory whose theory is simple and unstable (and thus does not have the strict order property), but which does not have the order property.

Altogether, the conjecture is up to now reduced to the case when 𝕄_{0} is minimal with small theory, has the order property and Th(𝕄_{0}) has the strict order property. Two questions come up naturally. The first: whether in such situation M_{0} must be ordered? This seems unlikely to be true, i.e., my guess is that the answer to the following question will be affirmative (although I don’t know of a particular example):

Question 2. Is there a minimal structure with small theory 𝕄_{0} such that 𝕄_{0} has the order property, Th(𝕄_{0}) has the strict order property but 𝕄_{0} is not ordered?

The second question is whether the conjecture is true for minimal, ordered structures. This is what we started answering in [8] and here we only state the complete answer; we omit the proof since in the meantime a more general result is found [9].

Theorem 1. A countable, minimal, ordered structure has 2^{ℵ_{0}} non-isomorphic countable elementary extensions.

The theorem generalizes Shelah’s result, see [6], who proved it for structures of the form (ω, <, …) and (ω + ω^{∗}, <, …) (the minimality of these structures is not assumed, but it is easy to reduce the general case to the case of minimal structures by passing to a definable subset of Cantor–Bendixson rank 1). The reason for having many countable models in our case is the same as in Shelah’s: an arbitrary countable linear order can be ’coded’ by an elementary extension of the ground structure. However, the major technical obstacle in our case turns out to be the absence of Skolem functions.

The proof of Theorem 1 heavily relies on the classification of minimal, ordered structures from [8] which we recall below in more detail; it is also needed to motivate Question 3 at the end. The two basic examples of minimal, ordered structures are (ω, <) and (ω + ω^{∗}, <) (where ω^{∗} is reversely ordered ω). Theorem 2 below states that any other minimal ordered structure is, in a way, similar to one of them.

We recall some notation. Let 𝕄_{0} = (M_{0}, …) be a minimal ordered structure and let p(x) be the set of all formulas in a free variable x (possibly with parameters from M_{0}), defining a co-finite subset of M_{0}. By minimality, p(x) is a complete 1-type with parameters from M_{0}; moreover, it is the only type in S_{1}(M_{0}) which is not already realized in 𝕄_{0} by an element of M_{0}. We write simply p instead of p(x). If 𝕄_{0} ≺ 𝕄 = (M, …) then by p(M) we denote the set of realizations of p in M (so that M = M_{0} ∪ p(M)).

Definition. For < a definable strict-ordering relation on 𝕄_{0} define:

L_{<}(M_{0}) = {m ∈ M_{0} | (m < x) ∈ p}
U_{<}(M_{0}) = {m ∈ M_{0} | (x < m) ∈ p}
I_{<}(M_{0}) = {m ∈ M_{0} | (x⊥m) ∈ p}.

(Here x⊥y denotes x ≠ y ∧ ¬(x < y) ∧ ¬(y < x).)

Note that any element of M_{0} belongs to exactly one of L_{<}(M_{0}), U_{<}(M_{0}) or I_{<}(M_{0}):

M_{0} = L_{<}(M_{0}) ∪ U_{<}(M_{0}) ∪ I_{<}(M_{0}),

Also:

M = p(M) ∪ L_{<}(M_{0}) ∪ U_{<}(M_{0}) ∪ I_{<}(M_{0}).

The unions above are disjoint, L_{<}(M_{0}) < p(M) < U_{<}(M_{0}) and I_{<}(M_{0})⊥p(M), (here by A < B we mean a < b for all a ∈ A and b ∈ B), in which sense we consider p(M) (in 𝕄 = (M, < …) ≻ 𝕄_{0}) as the ‘middle’ part of M; similarly, ‘L’ in L_{<}(M_{0}) = {x ∈ M|x < p(M)} indicates that the ‘lower’ part of M_{0} (and also of M) is in question, U the ‘upper’ and I the ‘incompatible’ part of M_{0}. The main technical result in [8] is that I_{<}(M_{0}) is finite whenever < has an infinite chain (or just arbitrarily large finite chains). It induces a closer description of minimal, ordered structures:

Theorem 2. If 𝕄_{0} = (M_{0}, …) is a minimal ordered structure, and < is a definable strict ordering on M_{0} with an infinite (increasing) chain then (M_{0}, <) falls into one of the following two types:

Type(ω)  M_{0} = L_{<}(M_{0}) ∪ a finite set;
Type(ω + ω^{∗})  M_{0} = L_{<}(M_{0}) ∪ U_{<}(M_{0}) ∪ a finite set

(here both L_{<}(M_{0}) and U_{<}(M_{0}) are infinite).

If (M_{0}, <) is of Type(ω), then (L_{<}(M_{0}), <) has no maximal elements, is directed upwards and has no increasing chains of order type ω+1; it somehow reminds us of (ω, <). Similarly, if (M_{0}, <) is of Type(ω + ω^{∗}), then (L_{<}(M_{0}), <) has no maximal elements, is directed upwards and has no increasing chains of order type ω + 1, while (U_{<}(M_{0}), <) has no minimal elements, is directed downwards and has no decreasing chains of order type 1+ω^{∗}; altogether, (M_{0}, <) reminds of (ω+ω^{∗}, <).

The next natural question to be considered is whether Type(−) of a minimal, ordered structure depends on a particular choice of the ordering relation; i.e., whether a structure can be of Type(ω) with respect to one ordering relation and of Type(ω +ω^{∗}) with respect some other. It turned out that the answer is negative; it follows from the next theorem, which establishes a model-theoretic characterization of minimal, ordered structures of Type(ω).

Recall the notion of semi-isolation: let ℕ = (N, …) be a first-order structure, let A ⊆ N and a, b ∈ N, then tp(b/A) is semi-isolated over a (or a semi-isolates tp(b/A)) if there is a formula ϕ(x, y) (with parameters from A possible) such that ℕ ⊨ ϕ(a, b) and whenever ℕ ⊨ ϕ(a, c) then c ⊨ tp(b/A). If A = ∅ then we simply say that b is semi-isolated over a (or that a semi-isolates b). In the context of the following theorem, we may assume that all the parameters from the are incorporated into the language, so that semi-isolation becomes a binary relation on p(N). It is reflexive and transitive: for transitivity, if a semi-isolates b is witnessed by ϕ(x, y), and b semi-isolates c is witnessed by ψ(y, z), it is straightforward to check that (∃y)(ϕ(x, y) ∧ ψ(y, z)) witnesses that a semi-isolates c. Further, recall that q ∈ S_{1}(N) is definable if for each formula ϕ(x, ȳ) there is a formula ψ(ȳ) (with parameters from N possibly) such that:

for all n̄ ∈ N^{k}: ϕ(x, n̄) ∈ q iff ℕ ⊨ ψ(n̄).

Theorem 3. Let 𝕄 = (M, …) be a minimal structure and let p ∈ S_{1}(M) be the non-algebraic type. Then the following conditions are equivalent:

(1) There exists (a definable) < such that (M, <) is of Type(ω).

(2) There exists 𝕄_{1} ≻ 𝕄 such that semi-isolation is not symmetric on p(M_{1}).

If we in addition assume that 𝕄 is ordered, then (1) and (2) are also equivalent to:

(3) p is definable.

(4) 𝕄 is ordered of Type(ω) with respect to any < having an infinite (increasing) chain.

Proof. The equivalence of (1) and (2) is proved in Theorem 2.1 in [8]. To prove the rest, we will assume that 𝕄 is a minimal, ordered structure.

(4) → (1) is trivial.

(1) → (3). Suppose (M, <) is of Type(ω) and we will prove that p is definable. Let 𝕄_{1} ≻ 𝕄 and a ∈ p(M_{1}). Since (M, <) is of Type(ω) we may assume L_{<}(M) = M and thus M < a. Then a < x ⊢ p(x) easily follows.

Let ϕ(x, ȳ) be a formula. We claim that for all m̄ ∈ M:

ϕ(x, m̄) ∈ p iff 𝕄 ⊨ (∀y)(∃x>y) ϕ(x, m̄),

which, clearly, implies the definability of p.

For one direction, ϕ(x, m̄) ∈ p implies 𝕄_{1} ⊨ ϕ(b, m̄) for all b ∈ p(M_{1}). Now, M < p(M_{1}) implies 𝕄_{1} ⊨ (∀y)(∃x > y) ϕ(x, m̄) and 𝕄 ⊨ (∀y)(∃x > y) ϕ(x, m̄) follows.

For the other direction suppose 𝕄, 𝕄_{1} ⊨ (∀y)(∃x>y) ϕ(x, m̄). Then, in particular, we have 𝕄_{1} ⊨ (∃x>a) ϕ(x, m̄). Since x > a ⊢ p(x) we conclude ϕ(x, m̄) ∈ p.

(3) → (4). Suppose p is definable and let ◁ be any definable strict ordering on M. Note that, by definability of p, both L_{◁}(M) = {m ∈ M | (m ◁ x) ∈ p} and U_{◁}(M) = {m ∈ M | (x ◁ m) ∈ p} are definable subsets of M. They are disjoint so, by minimality of 𝕄, at least one of them must be finite. This implies that (M, ◁) can not be of Type(ω + ω^{∗}) and the desired conclusion follows by Theorem 2. □

From Theorems 2 and 3 we immediately derive:

Corollary. Type of ordering of (M_{0}, <) in a minimal, ordered structure 𝕄_{0} does not depend on the particular choice of <.

In [8] I stated that the corollary follows from Theorem 2.1 there, which includes only conditions (1) and (2) from Theorem 3. This was not quite true, and is now fixed by adding (3) and (4).

As we noted before, Theorem 2 establishes a (weak) similarity of a minimal ordered structure with a basic one. The similarity of any structure that I found by now was much stronger, so it is natural to ask:

Question 3. Must every minimal, ordered structure interpret either (ω, <) or (ω + ω^{∗}, <)?

References

[1] J. T. Baldwin, A. H. Lachlan, On strongly minimal sets, J. Symb. Log. 36(1971), 79–96.

[2] O. V. Belegradek, On minimal structures, J. Symb. Log. 63(1998), 421–426.

[3] A. Pillay, Number of countable models, J. Symb. Log. 43(1978), 494–496.

[4] A. Pillay, Dimension theory and homogeneity for elementary extensions of a model, J. Symb. Log. 47(1982), 147–160.

[5] A. Pillay, Minimal types in simple theories, preprint, 2006

[6] S. Shelah, End extensions and numbers of countable models, J. Symb. Log. 43(1978), 550–562.

[7] P. Tanović, On constants and the strict order property, Arch. Math. Logic 45(2006), 423–430.

[8] P. Tanović, On minimal ordered structures, Publ. Inst. Math., Nouv. Sér. 78(92) (2005), 65–72.

[9] P. Tanović, Types directed by constants, in preparation.

Matematički institut SANU

Knez Mihailova 36

11001 Beograd, p.p. 367

Serbia

    tane@mi.sanu.ac.yu