Existence of a binary Ehrenfeucht theory without the strict order property

The paper of Sudoplatov and Tanović on semi-isolation and the strict order property (arXiv:1307.0604; Notre Dame J. Formal Logic 56(4), 2015) poses as its motivating Question 1: does there exist a binary Ehrenfeucht theory without the strict order property (SOP) — in particular, one with exactly three countable models? Here an Ehrenfeucht theory is a complete countable first-order theory with finitely many but more than one countable model, and a binary theory is one in which every formula is equivalent to a Boolean combination of formulas with at most two free variables. Every known Ehrenfeucht theory is obtained from an omega-categorical theory that already has SOP (dense orders, meet-trees) by adding infinitely many constants or predicates, and the conjecture that SOP is unavoidable in Ehrenfeucht theories has circulated since the 1970s. The problem is to settle the binary case definitively: construct a binary Ehrenfeucht theory that is NSOP (with exactly three countable models, ideally), or prove that every binary Ehrenfeucht theory — in particular every binary theory with exactly three countable models — has the strict order property. The question is open: its three-model form is restated as open Problem 6 of the August 2025 survey by Pillay and Tanović, in which the general conjecture that every Ehrenfeucht theory has the strict order property is described as having circulated since the 1970s and as still widely open.

Background

For a complete first-order theory $T$ in a countable language (a consistent, deductively closed set of sentences), a basic invariant is $I(\aleph_0,T)$, the number of countably infinite models of $T$ up to isomorphism. A classical theorem says that no complete theory has exactly two countable models, while examples with any finite number $n\ge 3$ of countable models exist. A theory with $1<I(\aleph_0,T)<\aleph_0$ is called an Ehrenfeucht theory. The original example is the theory of the dense linear order $(\mathbb{Q},<)$ expanded by constants $c_0<c_1<c_2<\cdots$: its three countable models are distinguished by whether the constant sequence is unbounded, converges to a supremum that is realized, or is bounded with no realized supremum. Theories with exactly three countable models are the smallest nontrivial case and have been studied intensively since the 1970s.

Classification theory divides theories by combinatorial "dividing lines" — properties of single formulas that separate well-structured theories from wild ones. The strict order property (SOP) holds if some formula $\varphi(x,y)$ defines, in every model of $T$, a partial order with arbitrarily long finite chains (equivalently, with an infinite chain); NSOP means the theory lacks this property. Stability, the absence of the order property (no formula $\varphi(\bar x,\bar y)$ and sequence $\bar a_i$ with $\models\varphi(\bar a_i,\bar a_j)$ if and only if $i<j$), is strictly stronger than NSOP, since a definable partial order with infinite chains yields such a formula. All known Ehrenfeucht theories — including the classical example above and its dense meet-tree variant — are built from $\omega$-categorical theories (theories with a unique countable model up to isomorphism) that already have SOP, by adding infinitely many constants or unary predicates. Whether this is forced is unknown: the assertion that every Ehrenfeucht theory has the strict order property is a conjecture that has circulated since the 1970s and is described as still widely open in the 2025 survey of Pillay and Tanović; the weaker assertion that no stable theory is Ehrenfeucht is also open.

A theory is binary if every formula is equivalent modulo $T$ to a Boolean combination of formulas with at most two free variables; the classical Ehrenfeucht example is binary, and binarity makes the combinatorics of types tractable, so the binary case is the natural first target for the conjecture. Several partial exclusions are known: no superstable theory is Ehrenfeucht (Lachlan 1973; superstable theories form a strong subclass of stable theories in which forking — the canonical stability-theoretic notion of dependence between types — obeys a finite-weight calculus); no supersimple theory is Ehrenfeucht (Kim 1999); and a countable non-$\aleph_0$-categorical NSOP$_1$ theory (NSOP$_1$ being the weakest level of the hierarchy of properties strictly between simplicity and NSOP) with "nonforking existence" and finitely many countable models must contain a tuple of self preweight $\omega$ (Kim 2019; self preweight is a weight-theoretic invariant from stability theory measuring how many mutually independent realizations of the same type a given realization can be forking-dependent on). On the other side, Woodrow (1976) showed that a theory with three countable models and quantifier elimination in the language of the classical example must be very close to it, and Ikeda–Tsuboi–Pillay (1998) showed that every almost $\aleph_0$-categorical theory with three countable models interprets a dense linear order (almost $\aleph_0$-categorical means that for any two complete types $p(\bar x)$ and $q(\bar y)$, the partial type $p(\bar x)\cup q(\bar y)$ has only finitely many complete extensions); Herwig (1995) constructed a small stable theory (one realizing only countably many complete types over $\emptyset$) with a type of infinite self preweight, showing the known obstructions are not mere stability-theoretic bookkeeping.

The paper of Sudoplatov and Tanović attacks the binary case through semi-isolation. A tuple $b$ is semi-isolated over $a$ if some formula $\varphi(a,x)\in\mathrm{tp}(b/a)$ implies the complete type of $b$; on the locus $p(M)$ of a non-isolated complete type $p$ this defines a quasi-order $SI_p$. A non-isolated type $p$ is powerful if the prime model (the model elementarily embeddable in every model) over a single realization of $p$ realizes all finitary types; Benda showed powerful types exist in every Ehrenfeucht theory, and with exactly three countable models they classify the models: the prime model omits $p$, the saturated model realizes $p$ with no minimal elements, and the middle model realizes $p$ with a minimal element under $SI_p$. The paper proves that under additional topological assumptions on the compact space $S_{p,p}$ of complete extensions of $p(x)\cup p(y)$ — for instance closed asymmetric links, i.e. the set of complete 2-types of pairs on the locus in which semi-isolation holds in exactly one direction being non-empty and closed in $S_{p,p}$ — $SI_p$ contains a relatively definable quasi-order with infinite chains (a $p$-order), which forces SOP; and it proves two opposing facts in the binary NSOP three-model setting: there are at least two complete types of $SI_p$-incomparable pairs (the semi-isolation order is "wide", suggesting a positive example may exist), while under the paper's PGPIP condition (a technical strengthening of downward directedness of $SI_p$) the Cantor–Bendixson rank of $S_{p,p}$ (the ordinal rank measuring how many iterations of deleting accumulation points remove a point) is forced to be finite, suggesting no such theory exists in that case. The motivating Question 1 of that paper — whether a binary Ehrenfeucht theory without SOP exists at all — is the problem posed here.

Problem Statement

Question (Sudoplatov–Tanović, Question 1): Does there exist a binary, Ehrenfeucht theory without the strict order property? In particular, is there such a theory with exactly three countable models?

An affirmative answer must be witnessed by a complete first-order theory $T$ in a countable language such that:

1. $T$ is binary: every formula is equivalent modulo $T$ to a Boolean combination of formulas with at most two free variables;
2. $T$ is Ehrenfeucht: $T$ has finitely many but more than one countable model up to isomorphism — most sharply, exactly three countable models, matching the 'in particular' clause;
3. $T$ is NSOP: no formula of $T$ defines, in any model of $T$, a partial order with arbitrarily long chains.

A negative answer must prove that no such theory exists: every binary Ehrenfeucht theory — over any finite number $>1$ of countable models, not only three — has the strict order property.

The general clause is the target and the three-model clause is its flagship special case. An affirmative answer on either clause settles the question as a whole (a theory with exactly three countable models is in particular an Ehrenfeucht theory). A negative answer settles the question as a whole only if it covers the general clause: a refutation limited to the three-model case would settle only the 'in particular' clause — Problem 6 of the Pillay–Tanović survey — and would count as major partial progress rather than a full resolution.

References

1. Sergey Sudoplatov, Predrag Tanović, "Semi-isolation and the strict order property", Notre Dame Journal of Formal Logic 56(4) (2015), 555–572. DOI: 10.1215/00294527-3153579. https://doi.org/10.1215/00294527-3153579 (preprint: arXiv:1307.0604, https://arxiv.org/abs/1307.0604)
2. Anand Pillay, Predrag Tanović, "The number of countable models of first-order theories", preprint (2025; revised August 2026). arXiv:2508.06854. https://arxiv.org/abs/2508.06854
3. A. H. Lachlan, "On the number of countable models of a countable superstable theory", Studies in Logic and the Foundations of Mathematics, vol. 74 (1973), 45–56. DOI: 10.1016/S0049-237X(09)70347-7. https://doi.org/10.1016/S0049-237X(09)70347-7
4. Akito Tsuboi, "Countable models and unions of theories", Journal of the Mathematical Society of Japan 38(3) (1986), 501–508. DOI: 10.2969/jmsj/03830501. https://doi.org/10.2969/jmsj/03830501
5. Predrag Tanović, "On constants and the strict order property", Archive for Mathematical Logic 45(4) (2006), 423–430. DOI: 10.1007/s00153-005-0323-x. https://doi.org/10.1007/s00153-005-0323-x
6. Predrag Tanović, "Theories with constants and three countable models", Archive for Mathematical Logic 46(5–6) (2007), 517–527. DOI: 10.1007/s00153-007-0054-2. https://doi.org/10.1007/s00153-007-0054-2
7. A. Pillay, "Instability and theories with few models", Proceedings of the American Mathematical Society 80(3) (1980), 461–468. DOI: 10.1090/S0002-9939-1980-0581006-6. https://doi.org/10.1090/S0002-9939-1980-0581006-6
8. Robert E. Woodrow, "A note on countable complete theories having three isomorphism types of countable models", The Journal of Symbolic Logic 41(3) (1976), 672–680. DOI: 10.2307/2272044. https://doi.org/10.2307/2272044
9. Robert E. Woodrow, "Theories with a finite number of countable models", The Journal of Symbolic Logic 43(3) (1978), 442–455. DOI: 10.2307/2273520. https://doi.org/10.2307/2273520
10. Koichiro Ikeda, Akito Tsuboi, Anand Pillay, "On theories having three countable models", Mathematical Logic Quarterly 44(2) (1998), 161–166. DOI: 10.1002/malq.19980440203. https://doi.org/10.1002/malq.19980440203
11. Byunghan Kim, "On the number of countable models of a countable NSOP$_1$ theory without weight $\omega$", The Journal of Symbolic Logic 84(3) (2019), 1168–1175. DOI: 10.1017/jsl.2019.47. https://doi.org/10.1017/jsl.2019.47
12. Byunghan Kim, "On the number of countable models of a countable supersimple theory", Journal of the London Mathematical Society 60(3) (1999), 641–645. DOI: 10.1112/S0024610799008054. https://doi.org/10.1112/S0024610799008054
13. Bernhard Herwig, "Weight $\omega$ in stable theories with few types", The Journal of Symbolic Logic 60(2) (1995), 353–373. DOI: 10.2307/2275836. https://doi.org/10.2307/2275836
14. Miroslav Benda, "Remarks on countable models", Fundamenta Mathematicae 81 (1974), 107–119. DOI: 10.4064/fm-81-2-107-119. https://doi.org/10.4064/fm-81-2-107-119
15. Slavko Moconja, Predrag Tanović, "Stationarily ordered types and the number of countable models", Annals of Pure and Applied Logic 171(3) (2020), 102765. DOI: 10.1016/j.apal.2019.102765. https://doi.org/10.1016/j.apal.2019.102765
16. P. E. Alaev, E. I. Khlestova, "Decidable Models of Ehrenfeucht Theories", Algebra and Logic 63(3) (2024), 155–163. DOI: 10.1007/s10469-025-09779-0. https://doi.org/10.1007/s10469-025-09779-0
17. David Gonzalez, Dino Rossegger, Dan Turetsky, "Scott Analysis below the Vaught Ordinal", preprint (2026). arXiv:2606.15205. https://arxiv.org/abs/2606.15205
18. Sergey V. Sudoplatov, "Combinations related to classes of finite and countably categorical structures and their theories", preprint (2017). arXiv:1701.00205. https://arxiv.org/abs/1701.00205