Three models and never two

Two lists that are one order proved, by Cantor’s back-and-forth, that any two countable dense orders without endpoints are isomorphic. The theory of such orders therefore has exactly one countable model up to isomorphism, and by the Łoś–Vaught test it is complete: it decides every first-order sentence. The graph that coin tosses always make found a second theory with the same property, the theory of the random graph. Theories with one countable model are called $\aleph_0$-categorical, and they are the simplest a theory can be. Their countable models are pinned down by finitely many conditions at each size, which is why finite structures such as the Paley graphs can approximate them so well.

Most complete theories have more models than that, and the natural question is how many. A complete theory in a countable language can have one countable model, or infinitely many, or as many as there are real numbers. Andrzej Ehrenfeucht found in the 1950s a theory with exactly three, and Robert Vaught proved in 1961 that no complete theory has exactly two. This essay draws Ehrenfeucht’s three, shows why there are three and no more, and follows Vaught’s argument on them, where it is short enough to see whole.

Why the countable models are the question #

Counting countable models is the natural question because every theory in a countable language that has an infinite model has a countable one. That is the downward Löwenheim–Skolem theorem, which a countable field that passes for the line built by adding a witness for every existential sentence. Compactness, the theorem an infinite tree has an infinite path reduced to König’s lemma, supplies models of the other sizes. Together they say that a first-order theory can never pin down the size of its infinite models. The question that remains is how many different models it has of a given size, and the countable size is the first and most concrete.

The answer measures how much a theory leaves undetermined about its models. A theory with one countable model, like the dense orders, determines its countable models completely. A theory with $2^{\aleph_0}$ of them, like arithmetic, leaves almost everything open; a number larger than every number built one of arithmetic’s nonstandard models, and there are continuum many. Ehrenfeucht’s theory sits close to the bottom of this scale: it determines everything except one thing, and that one thing has exactly three possibilities.

A dense order with constants #

The language has one relation, an order $<$, and infinitely many constant symbols $c_0, c_1, c_2, \ldots$. The axioms say that $<$ is a dense linear order without a least or greatest element — the axioms the rationals obey — together with one axiom for each $n$, saying $c_n < c_{n+1}$. Every model is a dense order with a marked increasing sequence of points in it.

The hero figure builds three inside the rationals. In A, $c_n = n$, and the constants are unbounded. In B, $c_n = -1/(n+1)$, rising to 0, which is a rational and so a point of the model. In C, the constants are the fractions $1, 7/5, 41/29, 239/169, \ldots$ that approach $\sqrt 2$ from below, the convergents of its continued fraction taken two at a time. Their limit is not a rational, so the model contains points above all of them but no least such point. Each figure is checked in exact rational arithmetic: the constants increase strictly, and every constant of C squares to less than 2.

The three are genuinely different, and the way to prove it is the method two worlds that both obey the rules used for the parallel postulate: exhibit structures and compare them. In A nothing lies above all the constants. In B and C something does, and in B the set of such points has a least element while in C it does not. An isomorphism must carry each $c_n$ to $c_n$, since the constants are part of the language, so it must carry the points above all constants to the points above all constants. Having a least element is preserved by any order isomorphism. No two of A, B and C are isomorphic.

Why the theory cannot tell them apart #

Yet the three satisfy exactly the same first-order sentences. A sentence is finite and mentions finitely many constants, say up to $c_N$. Every sentence the theory can state about a finite set of constants is decided by the axioms. They fix the order of $c_0, \ldots, c_N$, and density without endpoints fixes everything else. The proof of completeness is quantifier elimination: any formula is equivalent to a combination of order relations among its free variables and finitely many constants. A, B and C agree on all of those.

What differs is “above every $c_n$”, and that is an infinite conjunction — above $c_0$, and above $c_1$, and above $c_2$, and so on. No single sentence can say it. The theory is complete because every sentence is about finitely many constants, and the models differ only in what lies beyond all of them at once.

The places a point can sit #

That difference has a precise form in the language of types. A type is a complete description, in the theory’s language, of where one new point could sit.

For this theory the types are easy to list. A new point is below $c_0$, or equal to some $c_n$, or strictly between some $c_n$ and $c_{n+1}$, and each of these is said by a single formula. Those types are isolated, and every model must realise every isolated type of a complete theory: the model must contain a point that the formula describes, and density supplies one. The remaining type, “above every $c_n$”, is not isolated. It is the limit of “above $c_0$”, “above $c_1$”, and so on, and a model is free to realise it or not. A omits it; B and C realise it.

Vaught’s analysis of countable models runs entirely through this distinction. The isolated types are forced and the non-isolated ones are optional. A theory whose types over finite sets are all isolated has exactly one countable model. Ehrenfeucht’s theory has exactly one optional type, and it can be omitted, realised with a least witness, or realised without one. That gives three models.

Omitting a type #

Model A omits the type “above every $c_n$”, and the reason it is allowed to is a theorem that runs the other way from compactness. Compactness realises types: if every finite part of a description can be satisfied, some model satisfies all of it. The omitting types theorem, proved by Henkin and Orey in the 1950s, says when a model can avoid one. In a countable language, a complete theory has a countable model omitting a type exactly when the type is not isolated — when no single formula implies it. “Above every $c_n$” is implied by no single formula, since any formula mentions only finitely many constants, so some model omits it. Here that model is A.

The theorem is constructive in spirit. It builds the model step by step, as Löwenheim–Skolem does, and at each step it makes sure that the point being added fails at least one formula of the type. That is possible exactly when no formula already forces the whole type. An isolated type cannot be dodged this way, because the formula isolating it is true of some point in every model, and that point realises the type.

The same reasoning shows when a model is as small as possible. A model that realises only isolated types is atomic, and a countable atomic model is prime: it embeds in every model of the theory. A complete theory in a countable language with few types — only countably many over the empty set — always has one. So Ehrenfeucht’s A exists for a general reason, not just because it can be written down.

Why there are exactly three #

The three models are not three among many. Every countable model is isomorphic to one of them, and the reason is a decomposition into pieces that back-and-forth can match.

Cut a countable model into the stretch below $c_0$, the points $c_n$ themselves, the open intervals between consecutive constants, and the part above every constant. Each of the first kind of piece is a countable dense order without endpoints — dense because the whole order is, and without endpoints because the constants bounding it are excluded. By Cantor’s theorem each is isomorphic to the rationals, and therefore to the corresponding piece of any other model. Matching the pieces one by one, with each constant sent to the same constant, gives an isomorphism of everything below the top.

The top piece, if nonempty, is a countable dense order with no greatest element. It has none because the whole order has none, and it is dense because the whole order is. Such an order either has a least element or does not. If it has none, it is a dense order without endpoints and is a copy of the rationals. If it has one, removing that point leaves a copy of the rationals, so it is a least point followed by the rationals. So there are three possibilities for the top piece and therefore exactly three countable models.

Back-and-forth across different limits #

The decomposition says that models of kind C are all isomorphic, whatever irrational number their constants approach. That is worth seeing on an example, because it looks false. A model whose constants approach $\sqrt 2$ and one whose constants approach $\sqrt 7$ seem to have different “limits”.

The figure carries out Cantor’s construction on the two top pieces. It alternately takes the next unmatched rational above $\sqrt 2$ in a fixed enumeration and finds a partner above $\sqrt 7$ in the same position relative to every pair already made, then does the reverse. A partner always exists, because both orders are dense and neither has an endpoint, and the twelve pairs drawn never cross. Continued for ever, the matching exhausts both sides and is an isomorphism.

The irrational number is not part of either model, and nothing in the matching ever needs to know which irrational it is. At every step the only question is where a new point sits relative to finitely many points already matched, and density answers it on both sides in the same way. Within a model of kind C there is no point at $\sqrt 2$, only a gap where it would be, and a gap has no properties the theory can see beyond the fact that nothing fills it. The models know about their constants and their order, not about the real line they were drawn on. The same is why every model of kind B is like every other, wherever its supremum sits.

Every count except two #

Ehrenfeucht’s example shows that three is possible. Varying it shows much more.

Split the order into $k$ classes, each dense in every interval, by adding $k$ unary predicates. The theory stays complete and the analysis is the same. But the least point above the constants, in a model of kind B, now has a colour, and different colours give non-isomorphic models. That makes $1 + 1 + k = k + 2$ models: A, C, and one B for each colour, and the same back-and-forth shows there are no others. So every count from 3 upward is possible.

Larger counts come from other theories. The integers with a successor function have countable models consisting of one copy of the integers, or two, or any finite number, or countably many, so $\aleph_0$ in all. Arithmetic, and any theory rich enough to encode arbitrary sets of natural numbers, has the maximum, $2^{\aleph_0}$. The only count missing from the list below $\aleph_0$ is two.

Vaught’s argument #

Vaught’s proof that two is impossible can be carried out on Ehrenfeucht’s theory, where every step can be pointed at.

A complete theory with only finitely many countable models has two special ones. The prime model realises only isolated types, and embeds in every other model; here it is A. The countable saturated model realises every type over every finite set of its own points, and every countable model embeds in it; here it is C. If the theory has a non-isolated type at all, as this one does, the prime model omits it and the saturated model realises it, so they differ.

Now take a point $a$ realising the non-isolated type and build the prime model over $a$, the model that realises as little as possible while containing $a$. It realises the non-isolated type, at $a$, so it is not the prime model. But it omits the type “above every $c_n$ and below $a$”, because that type is not isolated over $a$. So $a$ is the least point above the constants, and the model is not saturated either. In Ehrenfeucht’s theory it is B. A third model is forced into existence by the first two, and that happens in every theory with finitely many models and a non-isolated type, which is why the count can never be two.

What the drawings show and do not #

The figures are drawings of three specific models inside the rationals, with every ordering statement checked exactly. They show the models’ difference and the decomposition that limits it to three. What they cannot show is completeness, which is a statement about every sentence, or the isomorphism of all models of one kind, which needs the infinite back-and-forth that the matching figure only begins. Both are proofs, and the figures illustrate them rather than replace them.

The model theory here is about countable models only. Ehrenfeucht’s theory has models of every infinite size, and how many it has of each size is a different question with a different answer: uncountably many in every uncountable size. Morley’s theorem of 1965 says that a theory with one model in one uncountable size has one model in every uncountable size, and the counting in uncountable sizes has its own, largely completed theory, due to Saharon Shelah.

Still open: Vaught’s conjecture #

Vaught’s conjecture asks whether a complete theory in a countable language can have a number of countable models strictly between $\aleph_0$ and $2^{\aleph_0}$. If the continuum hypothesis holds there is no such number, so the conjecture has content only as a statement that holds without assuming it, and it is open. Michael Morley proved in 1970 that the count is at most $\aleph_1$ or exactly $2^{\aleph_0}$. The conjecture is that $\aleph_1$ cannot occur either. Closed sets obey the continuum hypothesis described why statements of this shape — a definable set is either countable or as large as the line — are the natural form for such problems.

The conjecture has been proved for many classes of theories, among them the theories of trees, the o-minimal theories, and the $\omega$-stable theories, by methods that combine model theory with descriptive set theory. A counterexample would be a theory whose countable models are uncountably many yet impossible to parametrise by real numbers in any definable way. Whether one exists is open.

A theory that is complete and still has choices #

Ehrenfeucht’s theory decides every sentence, and still its countable models come in three kinds, because the one thing they disagree about cannot be said in a single sentence. The disagreement sits above all the constants at once. It can be nothing, a least point, or a gap without one, and back-and-forth makes everything else identical. Vaught’s argument turns that example into a law: a theory with any optional type and finitely many models has at least three. The prime model and the saturated model, built from a point that realises the optional type, force a third one between them.