PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 78(92) (2005), 65–72

ON MINIMAL ORDERED STRUCTURES

Predrag Tanović

Communicated by Žarko Mijajlović

Abstract. We partially describe minimal, first-order structures which have a strong form of the strict order property.

An infinite first-order structure is minimal if its each definable (possibly with parameters) subset is either finite or co-finite. It is strongly minimal if the minimality is preserved in elementarily equivalent structures. While strongly minimal structures were investigated more closely in a number of papers beginning with [4] and [1], there are a very few results on minimal but not strongly minimal structures. For some examples see [2] and [3].

In this paper we shall consider minimal, ordered structures. A first-order structure 𝕄_{0} = (M_{0}, …) is ordered if there is a binary relation < on M_{0}, which is definable possibly with parameters from M_{0}, irreflexive, antisymmetric, transitive and has arbitrarily large finite chains. We usually distinguish (one) such relation by absorbing the involved parameters into the language and assuming that < is an interpretation of a relation symbol from the language, in which case we write 𝕄_{0} = (M_{0}, <, …).

Two basic examples of minimal, ordered structures are (ω, <) and (ω + ω^{∗}, <) (where ω^{∗} is reversely ordered ω and + denotes the (ordinal) sum of partial orders). We can modify a basic example by replacing the original order by a new one, so that the structure remains minimal, ordered. For example, we can change < by taking a finite set of elements from the domain and rearranging them arbitrarily, leaving the order of the other elements unchanged; e.g. we can take 0 ∈ ω and make it bigger than all other elements, or incompatible to the others. Also, we can simply reverse the original order. Note that the ’new’ order obtained in either way is inter-definable with the original one, so that the structure remains unchanged. Further, we can enlarge basic structure as follows: starting with (ω, <) we can replace each n ∈ ω by some (large enough) finite set L(n) and define for a ∈ L(n) and b ∈ L(m): a < b iff n < m. For example (details are left to the reader):

1991 Mathematics Subject Classification: Primary 03C50; Secondary 03C15.

The author is supported by Ministry of Science and Technology of Serbia.

Example 0.1. Let L = {(i, n) ∈ ω × ω | i ≤ n}, and (i, n) < (j, m) iff n < m. Then 𝕃 = (L, <) is a minimal ordered structure.

Example 0.2. Let U = {(i, n^{∗}) ∈ ω × ω^{∗} | i ≤ n}, let L be as in the previous example, and define: (i, n) < (j, m^{∗}) for all i, j, n, m; (i, n) < (j, m) iff n < m and (i, n^{∗}) < (j, m^{∗}) iff m < n. Then (L ∪ U, <) is a minimal, ordered structure.

Note that in both examples (L, <) is directed upwards and has no ascending chains of order type ω + 1, whilst (U, <) is directed downwards and has no descending chains of order type (ω + 1)^{∗}.

Our main result is a characterization of (M_{0}, <) in a minimal, ordered structure 𝕄_{0} = (M_{0}, <, …). It is done in Section 1 below where we we show that, after possibly changing < on a finite subset of M_{0} (as described above), or reversing the original order, we can partition M_{0} into two pieces L(M_{0}) and U(M_{0}) such that L(M_{0}) is upwards directed and unbounded, and has no ascending chains of order type ω + 1 and either:

U(M_{0}) = ∅ (i.e., (M_{0}, <) is similar to Example 0.1 above); or

U(M_{0}) is downwards directed and unbounded, and has no descending chains of order type (ω + 1)^{∗} (i.e., (M_{0}, <) is similar to Example 0.2).

In Section 2 we give a model-theoretic characterization of minimal, ordered structures 𝕄_{0} = (M_{0}, <, …) which are similar to Example 0.1. in the above sense.

1. Properties of order

Throughout this section we fix a minimal ordered structure 𝕄_{0} = (M_{0}, <, …). 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 1type 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.

Lemma 1.1. (a) {x ∈ M_{0} | x has immediate successor and predecessor} is co-finite.

(b) Every realization of p in an elementary extension of 𝕄_{0} has immediate successors and predecessors which are necessarily realizations of p.

Proof. Suppose that m ∈ M_{0} does not have immediate successors. Then we have (exactly) one of the following two cases:

(I) m is a maximal element; (II) 𝕄_{0} ⊧ (∀x > m)(∃y)(m < y < x).

Firstly, we show that there are finitely many possibilities for m in case (I). Note that the set of maximal elements is a definable antichain; the existence of arbitrary large finite chains in M_{0} implies that the antichain can not be co-finite. Therefore, by minimality, it must be finite.

Suppose our m is in case (II) above. Choose an infinite descending chain above m, of order type ω^{∗}. Suppose that an element from the chain falls into case (II), and, then choose a descending chain above it of order type ω^{∗}. We now have a chain of order type ω^{∗} + ω^{∗} (above m), contradicting the minimality assumption.

We conclude that infinitely many elements of the (first) chain fall into neither of cases (I) or (II), so they have immediate successors.

Thus the set of elements of M_{0} having immediate successors (which is definable) is infinite; by minimality it has to be co-finite. Dually, the set of elements of M_{0} having immediate predecessors is co-finite, finishing the proof of (a).

To prove (b) note that it easily follows from (a) that any realization of p has immediate successors, so it remains to show that among them there are no elements of M_{0}. For, let m ∈ M_{0}. Note that the set of all immediate predecessors of m is a definable antichain which is, by minimality, finite. Hence, the ‘formula’ ′m is an immediate successor of x′ does not belong to p, completing the proof of the Lemma. □

Lemma 1.2. Suppose that 𝕄_{0} ≺ 𝕄 = (M, <, …). Then at least one of the following conditions holds:

(MIN) Every definable (with parameters) subset of M has a minimal element; (MAX) Every definable (with parameters) subset of M has a maximal element.

Proof. Suppose that neither (MAX) nor (MIN) hold in 𝕄. Let ϕ(x, m̄) define a subset of M without minimal element, and let ψ(x, n̄) define a subset of M without maximal element, where m̄ and n̄ are tuples of elements of M. Note that ϕ(x, ȳ) (considered as a formula in variable x, with ȳ fixed) defines a subset without minimal elements’ is expressible by a first-order formula in variables ȳ, call it ϕ_{1}(ȳ) and similarly define ψ_{1}(z̄). Thus

𝕄 ⊧ (∃ȳ)(∃z̄)(ϕ_{1}(ȳ) ∧ ψ_{1}(z̄)),

and hence:

𝕄_{0} ⊧ (∃ȳ)(∃z̄)(ϕ_{1}(ȳ) ∧ ψ_{1}(z̄)).

We conclude that there are m̄_{0} and n̄_{0} in M_{0} such that ϕ(x, m̄_{0}) defines a subset of M_{0} without a minimal element, and ψ(x, n̄_{0}) defines a subset of M_{0} without a maximal element. Clearly both sets are infinite so, by minimality of 𝕄_{0}, both of them are co-finite and so is their intersection, call it D. D is definable, infinite and has neither minimal nor maximal elements. It follows that for any d ∈ D both sets {x | x < d} and {x | x > d} are infinite, contradicting minimality of 𝕄_{0}. □

Remark 1.1. Satisfaction of (MIN) (or (MAX)) in a structure can be expressed by a set of first-order sentences; so if it is satisfied in some structure, it must be satisfied in all structures elementary equivalent to it.

Remark 1.2. The set of minimal (maximal) elements of a definable subset of M_{0} is finite: clearly it is a definable antichain, and if it were infinite it would have to be co-finite, contradicting the existence of arbitrary large finite chains in M_{0}.

Proposition 1.1. M_{0} is countable.

Proof. Let Lev(0) be the set of minimal and Lev^{∗}(0) the set of maximal elements of M_{0}. Inductively define Lev(n+1) as the set of minimal and Lev^{∗}(n+1) as the set of maximal elements of M_{0} ∖ ⋃_{i≤n}(Lev^{∗}(i) ∪ Lev(i)).

Note that if m ∈ M_{0} ∖ ⋃_{i∈ω}(Lev^{∗}(i) ∪ Lev(i)), then both {x ∈ M_{0} | x < m} and {x ∈ M_{0} | m < x} are infinite, contradicting the minimality assumption. Therefore M_{0} = ⋃_{i≤n}(Lev^{∗}(i) ∪ Lev(i)). But by the previous remark each Lev(i) (and also Lev^{∗}(i)) is finite so that the union is countable. □

Definition 1.1. We 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}.

Usually, we operate with a single ordering relation < inside a structure, in which case the subscript ‘<’ is omitted, i.e., we write simply L(M_{0}), U(M_{0}) and I(M_{0}).

Note that any element of M_{0} must belong to either L(M_{0}) or U(M_{0}) or I(M_{0}), i.e.:

M_{0} = L(M_{0}) ∪ U(M_{0}) ∪ I(M_{0}) and M = p(M) ∪ L(M_{0}) ∪ U(M_{0}) ∪ I(M_{0}).

Also we have L(M_{0}) < p(M) < U(M_{0}) and I(M_{0}) ⊥ p(M), in which sense we consider the set of realizations of p in 𝕄 = (M, <, …) ≻ 𝕄_{0} as the ‘middle’ part of M; then ‘L’ in L(M_{0}) = {x ∈ M | x < p(M)} indicates that the ‘lower’ part of M_{0} (actually of 𝕄) is in question. Similarly, U indicates the ‘upper’ and I the ‘incompatible’ part of 𝕄.

Note that m ∈ L(M_{0}) iff {x ∈ M_{0} | m < x} is co-finite or, equivalently, infinite. Similarly for U(M_{0}) and I(M_{0}). This fact shall be used often in what follows.

Lemma 1.3. (a) Every nonempty subset of U(M_{0}) has a maximal element.

(b) If U(M_{0}) is infinite, then 𝕄_{0} satisfies (MAX). Dually:

(a′) Every nonempty subset of L(M_{0}) has a minimal element.

(b′) If L(M_{0}) is infinite, then 𝕄_{0} satisfies (MIN).

Proof. (a) Suppose, on the contrary, that a nonempty subset of U(M_{0}) does not have a maximal element. Then there is m ∈ U(p) such that {x ∈ M_{0} | m < x} is infinite and hence (by minimality) co-finite. Then {x ∈ M_{0} | x < m} is finite, contradicting (x < m) ∈ p.

(b) Suppose U(M_{0}) is infinite and we prove that (MAX) holds. Let ϕ(x) define a nonempty subset D of M_{0}. If D is finite it clearly has a maximal element. Assume D is infinite. By minimality D must be co-finite and thus E = D ∩ U(M_{0}) ≠ ∅. By (a) E has a maximal element, say d, which is also maximal in D (if d < m and m ∈ D, then, since (x < d) is in p, (x < m) must be in p, too, i.e., m ∈ U(M_{0}) and m ∈ E). □

We shall describe L(M_{0}), U(M_{0}) and I(M_{0}) in more detail.

Lemma 1.4. If 𝕄_{0} satisfies (MIN), then L(M_{0}) is infinite, directed upwards (i.e., every finite subset of L(M_{0}) has a strict upper bound in L(M_{0})) and has no ascending chains of order type ω + 1.

Dually, if 𝕄_{0} satisfies (MAX), then U(M_{0}) is infinite, directed upwards and has no descending chains of order type (ω + 1)^{∗}.

Proof. Suppose that 𝕄_{0} ≺ 𝕄 = (M, <, …) and a ∈ M is a realization of p.

(1) Firstly, we prove that if m_{1}, m_{2}, …, m_{k} ∈ L(M_{0}), then there is n ∈ L(M_{0}) such that m_{1}, m_{2}, …, m_{k} < n.

Note that m_{1}, m_{2}, ..., m_{k} < a and let D(a) = {x ∈ M | m_{1}, m_{2}, ..., m_{k} <x<a}. By Lemma 1.1 a has a predecessor b realizing p. Then m_{1}, m_{2}, …, m_{k} < b, whence b ∈ D(a) and D(a) ≠ ∅ (showing that for any realization c of p D(c) ≠ ∅). By (MIN) D(a) has a minimal element n. But D(n) = ∅ so n is not a realization of p and from n < a we infer n ∈ L(M_{0})

(2) Now we show that L(M_{0}) ≠ ∅, which combined with (1) implies that there is an infinite chain of order type ω in L(M_{0}); in particular, L(M_{0}) is infinite.

By (MIN) (in 𝕄) the set {x ∈ M | x < a} has a minimal element m. By Lemma 1.1 m can’t realize p, so m ∈ M_{0}, i.e., L(M_{0}) ≠ ∅.

To complete the proof it remains to note that any chain of order-type ω + 1 in L(M_{0}) would, by (1), produce a chain of order-type ω + ω contradicting the minimality. □

Lemma 1.5. If one of U(M_{0}) and L(M_{0}) is finite, then I(M_{0}) is finite, too.

Proof. Without loss of generality, suppose U(M_{0}) is finite. Then M_{0}∖U(M_{0}) is definable and let A be the set of its maximal elements. A is finite by Remark 1.2. By Lemma 1.4 no element of L(M_{0}) is maximal, so A ⊆ I(M_{0}). Thus, for m ∈ A we have (x < m) ∉ p, and {x ∈ M_{0} | x ≤ m} is finite. Therefore B = ⋃_{m∈A}{x ∈ M_{0} | x ≤ m} is finite.

We claim that I(M_{0}) ⊆ B. Otherwise, there would exist n ∈ I(M_{0}) with no maximal elements above it. But the last implies that {x ∈ M_{0} | n < x} is infinite, i.e., (n < x) ∈ p and n ∈ L(M_{0}), contradicting n ∈ I(M_{0}). □

Proposition 1.2. I(M_{0}) is finite.

Proof. If either of U(M_{0}) or L(M_{0}) is finite we are done by previous lemma, so suppose that both of them are infinite. By Lemma 1.3 both (MIN) and (MAX) hold in M_{0}.

The proof goes as follows: assuming that I(M_{0}) is infinite we shall find another definable ordering relation ◁ on M_{0}, such that: (M_{0}, ◁, …) is also minimal ordered, I_{◁}(M_{0}) is also infinite, but U_{◁}(M_{0}) = ∅, contradicting the previous lemma.

Suppose that I(M_{0}) is infinite. Let 𝕄_{0} ≺ 𝕄 = (M, <, …) and let a ∈ p(M). For x ∈ M define Succ(x) to be the set of all immediate successors of x and:

D(x) = {t ∈ M | x < t and (∃y ∈ Succ(x))(y ⊥ t)}.

For x, y ∈ M with D(x), D(y) ≠ ∅ define: x ◁ y iff D(y) ⊂ D(x).

We continue with a sequence of claims:

(1) ∅ ≠ D(a) ⊂ p(M). In particular {x | D(x) ≠ ∅} is co-finite.

We leave to the reader to verify that Succ(a) has at least two elements in which case Succ(a) ⊆ D(a) and D(a) ≠ ∅. To prove the inclusion suppose b ∈ D(a); i.e., there is c ∈ Succ(a) such that a < b and b ⊥ c. By Lemma 1.1 c ⊧ p. Now, c < U(M_{0}) and b ⊥ c imply b ∉ U(M_{0}). Also a < b implies b ∉ L(M_{0}) ∪ I(M_{0}) and altogether b ⊧ p, completing the proof of (1).

(2) a ◁ b implies b ∈ p(M), i.e., U_{◁}(M_{0}) = ∅.

a ◁ b means ∅ ≠ D(b) ⊂ D(a) ⊂ p(M) which, by (1), implies D(b) ∩ p(M) ≠ ∅. If b ∈ M_{0} were true, then D(b), being definable in 𝕄_{0}, would have to contain the whole p(M), contradicting D(b) ⊂ D(a) ⊂ p(M).

(3) If m ∈ M_{0} and m ◁ a, then m ∈ L(M_{0}). Thus L_{◁}(M_{0}) ⊆ L(M_{0}).

m◁a implies D(m) ⊃ D(a), so by (1) D(m)∩p(M) ≠ ∅. But D(m) is definable in 𝕄_{0} so D(m) ⊇ p(M) implying m < p(M), i.e., m ∈ L(M_{0}).

(4) If m ∈ M_{0} and m ◁ a, then Succ(m) ∩ I(M_{0}) ≠ ∅.

By (3) m ∈ L(M_{0}) so Succ(m) ⊆ L(M_{0}) ∪ I(M_{0}). If Succ(m) ⊂ L(M_{0}), then, since L(M_{0}) is directed, we have Succ(m) < p(M) and D(m) ∩ p(M) = ∅ which contradicts m ◁ a.

(5) Conversely, if m ∈ L(M_{0}) and Succ(m) ∩ I(M_{0}) ≠ ∅, then m ◁ a.

If i ∈ I(M_{0}) ∩ Succ(m), then m < p(M) and i ⊥ p(M) imply p(M) ⊆ D(m) so m ◁ a by (1).

(6) If m ∈ L(M_{0}), then there exists n ∈ L(M_{0}) such that m ≤ n and n ◁ a. Thus {x ∈ L(M_{0}) | x ◁ a} is infinite

m ∈ L(M_{0}) implies that {x | m < x} is co-finite, so it must contain some i ∈ I(M_{0}). Going upwards along a chain connecting m and i we can find along the way some n ∈ L(M_{0}) having immediate successor in I(M_{0}) which, by (5), implies n < a.

(7) If m ∈ L(M_{0}) and m ◁ a, then there is n ∈ L(M_{0}) such that m ◁ n ◁ a. By (3), D(m) ⊇ p(M) is infinite, hence is co-finite by minimality. Let D(m) =

M ∖ {m_{1}, m_{2}, …, m_{k}}. Then m_{i} ∉ D(m) ⊃ D(a) implies m_{i} ∉ D(a) ≠ ∅ so, by minimality, the set {x | m_{i} ∉ D(x) ≠ ∅} must be co-finite. Therefore, the set E = ⋂_{i=1}^{k}{x | m_{i} ∉ D(x) ≠ ∅} is co-finite, too. Now, if x ∈ E, then m_{i} ∉ D(x) so M ∖ {m_{1}, m_{2}, …, m_{k}} = D(m) ⊇ D(x) ≠ ∅, which is m ⊴ x. Further, from (6) F = {x ∈ L(M_{0}) | x ◁ a} is infinite so E ∩ F is infinite, too. Thus for all x ∈ E ∩ F we have m ⊴ x ◁ a and the conclusion follows.

To finish the proof of the proposition note that by (7) we have that (M_{0}, ◁, …) is a minimal ordered structure. By (3) any element from U(M_{0}) ∪ I(M_{0}) is not in L_{◁}(M_{0}), and since by (2) U_{◁}(M_{0}) = ∅ we conclude that I_{◁}(M_{0}) ⊇ U(M_{0})∪I(M_{0}). In particular I_{◁}(M_{0}) must be infinite, completing the proof of the proposition. □

Summing altogether results of this section we come to a closer description of (M_{0}, <) in a minimal, ordered structure 𝕄_{0} = (M_{0}, <, …). First of all, by Proposition 1.2, I(M_{0}) is finite, so after rearranging its elements and possibly replacing ‘<’, as described in the introduction, we may assume I(M_{0}) = ∅. Now, we have two cases depending on whether one of L(M_{0}) and U(M_{0}) is finite or not. In the first case suppose that U(M_{0}) is finite (if L(M_{0}) is finite, reverse the order). Then after rearranging its elements, we may assume U(M_{0}) = ∅. Thus we have:

Type(ω) (M_{0}, <) has no maximal elements, it is directed upwards and has no increasing chains of order type ω + 1.

In the other case both L(M_{0}) and U(M_{0}) are infinite, so by Lemma 1.4 we have:

Type (ω + ω^{∗}) M_{0} can be partitioned into L(M_{0}) and U(M_{0}), such that: (L(M_{0}), <) has no maximal elements, is directed upwards and has no increasing chains of order type ω + 1 and (U(M_{0}), <) has no minimal elements, it is directed downwards and has no decreasing chains of order type ω^{∗} + 1.

2. Model-theoretic properties

We recall Pillay’s notion of semi-isolation. Let ℕ = (N, …) be a first-order structure, q ∈ S_{1}(∅) and a, b ∈ q(N). Then b is semi-isolated over a (or a semiisolates b) if there is a formula ϕ(x, y) (without parameters) such that ℕ ⊧ ϕ(a, b) and whenever ℕ ⊧ ϕ(a, c), then c ∈ q(N). Semi-isolation 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.

The following theorem is inspired by [5], see also Proposition 2.1 in [6].

Theorem 2.1. Let 𝕄_{0} = (M_{0}, …) be a minimal structure. Then the following two conditions are equivalent:

(A) 𝕄_{0} is ordered of Type (ω).

(B) There exists 𝕄 ≻ 𝕄_{0} such that semi-isolation is not symmetric on p(M).

Proof. (A) ⇒ (B). Suppose 𝕄_{0} = (M_{0}, <, …) is ordered by < so that M_{0} = L(M_{0}). Let 𝕄 = (M, <, …) ≻ 𝕄_{0} be ℵ_{1}-saturated and let a ∈ p(M). Consider the set C = {tp(m/M_{0} ∪ {a}) | m ∈ M_{0}} ⊂ S_{1}(M_{0} ∪ {a}). C is infinite so, by compactness, it has an accumulation point q ∈ S_{1}(M_{0} ∪ {a}). Let b ∈ M be a realization of q. We shall show that a is semi-isolated over b, and that b is not semi-isolated over a.

Note that (x < a) ∈ tp(m/M_{0} ∪ {a}) for all m ∈ M_{0}, so (x < a) ∈ q. Thus 𝕄 ⊧ b < a and b semi-isolates a via b < y. Further, note that any formula ϕ(x, a) (with parameters from M_{0} ∪ {a}) which is satisfied by b must belong to some tp(m/M_{0} ∪ {a}). Therefore, ϕ(x, a) can not witness that b is semi-isolated over a, and b is not semi-isolated over a. Semi-isolation is not symmetric on p(M).

(B) ⇒ (A). Suppose 𝕄 = (M, …) ≻ 𝕄_{0} = (M_{0}, …) and a, b ∈ p(M) are such that a semi-isolates b (witnessed by ϕ(x, y)) but b does not semi-isolate a. Also, by replacing ϕ(x, y) by ϕ(x, y) ∧ ¬ϕ(y, x) if necessary, we may assume that ϕ(x, y) is asymmetric, i.e., 𝕄 ⊧ ϕ(x, y) ⇒ ¬ϕ(y, x). For x, y ∈ M define:

x < y iff 𝕄 ⊧ ϕ(x, y) ∧ (∀t)(ϕ(y, t) → ϕ(x, t)).

We will prove a sequence of claims.

(1) < is irreflexive and transitive.

Asymmetry of ϕ(x, y) implies that < is irreflexive; checking transitivity is straightforward and is left to the reader.

(2) a < c implies c ⊧ p, i.e., U(M_{0}) = ∅.

If a < c, then 𝕄 ⊧ ϕ(a, c) and, since ϕ(x, y) witnesses semi-isolation, we have c ⊧ p.

(3) tp(a/M_{0} ∪ {b}) is in accumulation point of {tp(m/M_{0} ∪ {b}) | m ∈ M_{0}}. Otherwise, there is a formula ψ(x, b) ∈ tp(a/M_{0} ∪ {b}) (with possible pa-

rameters from M_{0} not displayed) which is not satisfied by any m ∈ M_{0}. Thus ψ(x, b) ⊢ p(x) and a is semi-isolated over b; a contradiction.

(4) a < b.

Choose, by (3), a sequence {m_{k} | k ∈ ω} of distinct elements of M_{0}, so that {tp(m_{k}/M_{0} ∪ {b}) | k ∈ ω} converges to tp(a/M_{0} ∪ {b}) (in S_{1}(M_{0} ∪ {b})). From ϕ(x, b) ∈ tp(a/M_{0} ∪ {b}) we derive that for all but finitely many k ∈ ω ϕ(x, b) ∈ tp(m_{k}/M_{0} ∪ {b}), i.e., 𝕄 ⊧ ϕ(m_{k}, b) and ϕ(m_{k}, x) ∈ p. Further, if 𝕄 ⊧ ϕ(b, c), then c ⊧ p, so 𝕄 ⊧ ϕ(m_{k}, c) and:

𝕄 ⊧ ϕ(m_{k}, b) ∧ (∀t)(ϕ(b, t) → ϕ(m_{k}, t)).

From the convergence of tp(m_{k}/M_{0} ∪ {b}) to tp(a/M_{0} ∪ {b}) we get:

𝕄 ⊧ ϕ(a, b) ∧ (∀t)(ϕ(b, t) → ϕ(a, t)).

We have just showed that (M_{0}, <) is ordered and that U(M_{0}) = ∅, completing the proof of the theorem. □

Condition (B) in the theorem does not mention any specific order which is definable in the structure. Therefore if it is satisfied then a minimal, ordered structure can not be of Type (ω) with respect to one ordering, and of Type (ω+ω^{∗}) with respect to some other. We get:

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

References

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

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

[3] K. Ikeda, Minimal but not strongly minimal structures with arbitrary finite dimension, J. Symbolic Logic 66 (2001), 117–126.

[4] W. E. Marsh, On ω_{1}-categorical and not ω-categorical theories, PhD Thesis, Darmouth College, 1966

[5] A. Pillay, Number of countable models, J. Symbolic Logic 43 (1978), 492–496.

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

Matematički Institut SANU (Received 17 05 2005) Kneza Mihaila 35 (Revised 28 12 2005) 11001 Beograd, p.p. 367 Serbia and Montenegro

    tane@mi.sanu.ac.yu