Existence of a stable Ehrenfeucht theory (Lachlan's problem) and the source framework of expanding a stable powerful digraph without producing the strict order property

Open problem originating from S. V. Sudoplatov, 'On expansions and extensions of powerful digraphs' (Siberian Math. J. 50 (2009) 498-502). Powerful digraphs are the combinatorial skeletons that sit locally inside every known Ehrenfeucht theory, i.e. every complete countable theory with finitely many but more than one countable model. The paper proves that the simplest scheme for expanding such a digraph to an Ehrenfeucht theory (a 1-inessential ordered coloring plus locally existentially definable relations that mutually realize all nonprincipal types) always produces the first-order strict order property, hence instability. The open core is whether any expansion or extension scheme avoids this. An affirmative answer to the source's question - an expansion or extension of a stable powerful digraph to the structure of a stable Ehrenfeucht theory - would exhibit a stable Ehrenfeucht theory and thereby resolve Lachlan's problem (open since 1973); the converse implication is not established, since it is not known whether every stable Ehrenfeucht theory is representable as such an expansion. The paper's locally countably categorical (LCC) dominance criterion is one reduction discussed in the paper for producing the required powerful type inside the LCC class. The problem is open: every known Ehrenfeucht theory defines an infinite order, and every published obstruction (superstable, supersimple, unions of omega-categorical theories, almost omega-categorical) covers only a proper subclass of stable theories.

Background

For a countable complete first-order theory $T$, write $I(T,\omega)$ for the number of pairwise non-isomorphic countable models of $T$. Vaught proved $I(T,\omega)\neq 2$, and the classical example $\mathrm{Th}(\mathbb{Q},<,0,1,2,\dots)$ shows $I(T,\omega)=3$ is possible; a theory with $1<I(T,\omega)<\omega$ is called an Ehrenfeucht theory. Any such theory is automatically small, i.e. has only countably many complete types over $\emptyset$. A theory is stable if no formula has the order property, i.e. no formula $\varphi(\bar x,\bar y)$ admits tuples $\bar a_n$ with $\models\varphi(\bar a_i,\bar a_j)$ exactly when $i\le j$; a stronger failure is the strict order property (SOP), where some formula defines on a definable set a strict partial order with infinitely many pairwise comparable elements. SOP implies instability. Every classical Ehrenfeucht theory defines an infinite linear order and is therefore unstable.

By a theorem of Benda (1974), every Ehrenfeucht theory has a nonprincipal powerful type: a complete type $p\in S(\emptyset)$ such that any model realizing $p$ realizes every type of $T$. On the locus of such a type one has the semi-isolation quasi-order $SI_p$, where $\bar a$ semi-isolates $\bar b$ if some formula $\varphi(\bar x,\bar y)$ with $\models\varphi(\bar a,\bar b)$ satisfies $\varphi(\bar a,\bar y)\vdash p(\bar y)$; in an Ehrenfeucht theory this relation is necessarily non-symmetric, and non-symmetric semi-isolation is the standard mechanism forcing order phenomena. Sudoplatov (1990, 2007) extracted a combinatorial skeleton from this mechanism: a powerful digraph is a countable acyclic digraph $\langle X,Q\rangle$ with transitive automorphism group in which $Q$ is equivalent in $\mathrm{Th}(Q)$ to a disjunction of principal (isolating) formulas, every vertex has reachable images and preimages at all finite distances, for every vertex $a$ no vertex other than $a$ is algebraic over the union of the $Q$-cones of $a$, and any two vertices with a common reachable successor have arbitrarily long common routes. Powerful digraph structures occur locally inside the saturated structure of any nonprincipal powerful type with the global pairwise intersection property, hence inside every known Ehrenfeucht theory; conversely, in a simple theory a powerful digraph structure induces infinite forking weight, which is why no supersimple theory is Ehrenfeucht.

Sudoplatov (2003, 2006) developed a construction technique: expand a generic powerful digraph by an inessential coloring, i.e. a coloring $\mathrm{Col}:X\to\omega\cup\{\infty\}$ that remains 1-inessential (each color class carries no new structure), and by locally $(\exists,1,\mathrm{Col})$-definable relations, i.e. relations which on each color class are Boolean combinations of existential formulas of the colored digraph; such an enrichment is called $p_\infty$-powerful (where $p_\infty$ is the type of the infinite color) when, in addition, the semi-isolation relation on realizations of $p_\infty$ is non-symmetric via $Q$, $p_\infty$ is a powerful type of the expanded theory, every nonprincipal type of the expanded theory is realized inside $p_\infty$ by a principal formula of one of the new relation symbols, and these new relations respect route existence in the digraph. These $p_\infty$-powerful expansions mutually realize all nonprincipal types and realize every possible Ehrenfeucht behavior - every Rudin-Keisler preorder on the nonprincipal types (the quasi-order in which $p\le q$ when some realization of $q$ semi-isolates a realization of $p$, controlling which prime models over tuples are isomorphic) and every distribution of the number of limit models (countable models that are not prime over a tuple but are unions of elementary chains of prime models over tuples) - but all of them are unstable.

The 2009 source paper studies exactly the residual question. It first defines type-level analogues of the classification properties: a (partial) type $q(\bar x,\bar y)$ has the type strict order property if there are tuples $\bar a_n$, $n\in\omega$, with strictly $\supsetneq$-decreasing sets of realizations $q(\bar a_n,\mathfrak M)$. Every loopless acyclic digraph with an infinite chain, in particular every powerful digraph, has the type strict order property. Its main theorem (Theorem 2.1) then lifts this from types to formulas: every locally $(\exists,1,\mathrm{Col})$-definable $p_\infty$-powerful expansion of a powerful digraph with unbounded shortest-route lengths has the first-order SOP; and by Sudoplatov (1990, Prop. 3.2), bounded shortest-route lengths already give SOP for the powerful digraph's own theory. So the simplest expansion scheme can never yield a stable theory. The paper also introduces locally countably categorical (LCC) theories - theories with finitely many nonprincipal 1-types $p_1,\dots,p_n$ such that every definable set avoiding them is $\omega$-categorical - and proves (Theorem 3.1, Corollary 3.2) that in an LCC theory any $(p_1,\dots,p_n)$-dominant type is powerful, where $q$ is $(p_{i_1},\dots,p_{i_k})$-dominant if in every model realizing $q$ all types $r(\bar y)$ whose each variable satisfies one of the $p_{i_j}$ are realized; this reduces the search for powerful types to internal dominance: a nonprincipal 1-type $p_1(x)$ is internally powerful if it is $p_1$-dominant, and by Corollary 3.2 a unique internally powerful nonprincipal 1-type of an LCC theory is powerful. Its final remark shows the LCC framework is not vacuous, since generic constructions give LCC theories with a powerful type and unbounded route lengths, while noting that in an LCC theory with a nonprincipal powerful 1-type the shortest route lengths are bounded on each definable set avoiding the nonprincipal 1-types, and a single uniform upper bound for these lengths already implies the strict order property.

The surrounding negative boundary is classical. Lachlan (1973) proved that a countable superstable theory has either one or infinitely many countable models, so no superstable theory is Ehrenfeucht; the question whether a stable (necessarily non-superstable) Ehrenfeucht theory exists is known as Lachlan's problem and is the subject of Sudoplatov's Russian-language monograph 'The Lachlan problem'. Pillay (1983) and successors extended the exclusion to further stable classes (as collected in the 2012 survey of Baizhanov-Sudoplatov-Verbovskiy: normal, 1-based, and finitely codable theories). Tsuboi (1985, 1986) proved that an Ehrenfeucht theory which is a union of an increasing chain of $\omega$-categorical theories defines a non-identical dense order on a definable set (hence has SOP), and Kim (1999) that no countable supersimple theory is Ehrenfeucht. Ikeda-Tsuboi-Pillay (1998) showed that an almost $\omega$-categorical theory (a small theory all of whose $(p_1,\dots,p_n)$-types are principal over their restrictions) with exactly three countable models interprets a dense linear order. Thus every framework close to $\omega$-categoricity in which Ehrenfeucht theories can currently be built provably forces an infinite definable order, while the general stable case remains untouched.

Problem Statement

Does there exist a stable Ehrenfeucht theory - a complete countable first-order theory $T$ that is stable and has $1<I(T,\omega)<\omega$?

In the formulation of the source paper: can the structure of a stable powerful digraph be expanded or extended - by adding colorings and relations witnessing mutual realization of all nonprincipal types - to the structure of a stable Ehrenfeucht theory? Here a stable powerful digraph means a powerful digraph $\Gamma_{pg}$ whose own theory $\mathrm{Th}(\Gamma_{pg})$ is stable; by Sudoplatov (1990, Prop. 3.2), bounded shortest-route lengths already force the strict order property for $\mathrm{Th}(\Gamma_{pg})$, so such a digraph would necessarily have unbounded shortest-route lengths, and the source paper does not establish that such a digraph exists. An affirmative answer to the source formulation exhibits a stable Ehrenfeucht theory and hence resolves the general question above; the converse implication is not established, since powerful digraph structures are known to occur locally inside every known Ehrenfeucht theory (with the global pairwise intersection property), and it is not known whether every stable Ehrenfeucht theory arises as an expansion of a stable powerful digraph. Sudoplatov (2009), Theorem 2.1, already excludes the simplest such scheme: every locally $(\exists,1,\mathrm{Col})$-definable $p_\infty$-powerful expansion of a powerful digraph with unbounded shortest-route lengths has the first-order strict order property and is therefore unstable, and with bounded shortest-route lengths the powerful digraph's own theory already has the strict order property (Sudoplatov 1990, Prop. 3.2). The question is whether any other expansion scheme can avoid the strict order property.

An affirmative answer consists of an explicit complete countable theory $T$ (or an explicit expansion of a given stable powerful digraph) together with proofs that $T$ is stable and that $1<I(T,\omega)<\omega$. A negative answer consists of a proof that no such theory exists - equivalently, that every complete countable theory with finitely many but more than one countable model is unstable. A nonexistence proof restricted to expansions of stable powerful digraphs, or to any other proper subclass of stable theories, would not by itself settle the general question.

References

1. S. V. Sudoplatov, On expansions and extensions of powerful digraphs, Siberian Mathematical Journal 50 (2009), no. 3, 498-502 (Russian original: Sibirskii Matematicheskii Zhurnal 50 (2009), no. 3, 625-630). DOI: 10.1007/s11202-009-0056-x, https://doi.org/10.1007/s11202-009-0056-x (full text at http://mi.mathnet.ru/smj1987)
2. S. V. Sudoplatov, Powerful digraphs, Siberian Mathematical Journal 48 (2007), no. 1, 165-171. DOI: 10.1007/s11202-007-0017-1, https://doi.org/10.1007/s11202-007-0017-1 (full text at http://mi.mathnet.ru/eng/smj17)
3. S. V. Sudoplatov, Complete theories with finitely many countable models. II, Algebra and Logic 45 (2006), no. 3, 180-200. DOI: 10.1007/s10469-006-0016-5, https://doi.org/10.1007/s10469-006-0016-5
4. S. V. Sudoplatov, Inessential combinations and colorings of models, Siberian Mathematical Journal 44 (2003), no. 5, 883-890. DOI: 10.1023/A:1025901223496, https://doi.org/10.1023/A:1025901223496
5. S. V. Sudoplatov, Syntactic approach to constructions of generic models, Algebra and Logic 46 (2007), no. 2, 134-146. DOI: 10.1007/s10469-007-0012-4, https://doi.org/10.1007/s10469-007-0012-4
6. S. V. Sudoplatov, Powerful types in small theories, Siberian Mathematical Journal 31 (1990), no. 4, 629-638 (Russian original: Sibirskii Matematicheskii Zhurnal 31 (1990), no. 4, 118-128). DOI: 10.1007/BF00970635, https://doi.org/10.1007/BF00970635 (Zbl 0723.03018)
7. B. S. Baizhanov, S. V. Sudoplatov, V. V. Verbovskiy, Conditions for non-symmetric relations of semi-isolation, Siberian Electronic Mathematical Reports 9 (2012), 161-184. Zbl 1330.03073, open full text: http://semr.math.nsc.ru/v9/p161-184.pdf
8. S. Sudoplatov, P. Tanovic, Semi-isolation and the strict order property, Notre Dame Journal of Formal Logic 56 (2015), no. 4, 555-572. DOI: 10.1215/00294527-3153579, https://doi.org/10.1215/00294527-3153579 (preprint arXiv:1307.0604, https://arxiv.org/abs/1307.0604)
9. B. Sh. Kulpeshov, S. V. Sudoplatov, Linearly ordered theories which are nearly countably categorical, Mathematical Notes 101 (2017), no. 3, 475-483 (Russian original: Matematicheskie Zametki 101 (2017), no. 3, 413-424). DOI: 10.1134/S0001434617030099, https://doi.org/10.1134/S0001434617030099 (full text at http://mi.mathnet.ru/eng/mzm11094)
10. M. Benda, Remarks on countable models, Fundamenta Mathematicae 81 (1974), no. 2, 107-119. DOI: 10.4064/fm-81-2-107-119, https://doi.org/10.4064/fm-81-2-107-119
11. A. H. Lachlan, On the number of countable models of a countable superstable theory, in: Proceedings of the International Congress for Logic, Methodology and Philosophy of Science, North-Holland, Amsterdam, 1973, 45-56. DOI: 10.1016/S0049-237X(09)70347-7, https://doi.org/10.1016/S0049-237X(09)70347-7 (also MR0446949)
12. A. Pillay, Countable models of stable theories, Proceedings of the American Mathematical Society 89 (1983), no. 4, 666-672. DOI: 10.1090/S0002-9939-1983-0718994-3, https://doi.org/10.1090/S0002-9939-1983-0718994-3
13. B. Kim, On the number of countable models of a countable supersimple theory, Journal of the London Mathematical Society 60 (1999), no. 3, 641-645. DOI: 10.1112/S0024610799008054, https://doi.org/10.1112/S0024610799008054
14. A. Tsuboi, On theories having a finite number of nonisomorphic countable models, Journal of Symbolic Logic 50 (1985), no. 3, 806-808. DOI: 10.2307/2274332, https://doi.org/10.2307/2274332
15. A. Tsuboi, Countable models and unions of theories, Journal of the Mathematical Society of Japan 38 (1986), no. 3, 501-508. DOI: 10.2969/jmsj/03830501, https://doi.org/10.2969/jmsj/03830501
16. K. Ikeda, A. Tsuboi, A. Pillay, On theories having three countable models, Mathematical Logic Quarterly 44 (1998), no. 2, 161-166. DOI: 10.1002/malq.19980440203, https://doi.org/10.1002/malq.19980440203
17. S. V. Sudoplatov, The Lachlan problem, Novosibirsk State Technical University, Novosibirsk, 2008, 245 pp., in Russian (no DOI/ISBN indexed)
18. P. E. Alaev, E. I. Khlestova, Decidable Models of Ehrenfeucht Theories, Algebra and Logic 63 (2024), no. 3, 155-163. DOI: 10.1007/s10469-025-09779-0, https://doi.org/10.1007/s10469-025-09779-0
19. E. I. Khlestova, Limit Models of Ehrenfeucht Theories, Algebra and Logic 64 (2025), no. 3, 171-181. DOI: 10.1007/s10469-026-09823-7, https://doi.org/10.1007/s10469-026-09823-7
20. D. Gonzalez, D. Rossegger, D. Turetsky, Scott Analysis below the Vaught Ordinal (2026). arXiv:2606.15205, https://arxiv.org/abs/2606.15205