Vaught Conjecture

Vaught Conjecture

Definitions and mathematical statement

For a complete first-order theory $T$ in a countable language, let $I(T,\aleph_0)$ be the number of isomorphism classes of its countable models. Completeness means that for each sentence, $T$ decides it or its negation. Vaught's assertion is \[ I(T,\aleph_0)\le\aleph_0\quad\text{or}\quad I(T,\aleph_0)=2^{\aleph_0}. \] Thus no intermediate uncountable number of countable models is permitted. Models are compared by isomorphism, not elementary equivalence, which all models of $T$ already share. The statement is about arbitrary complete countable theories; a result for one relational signature or a selected structural class is only a subcase.

Formulation and concept references: [S1].

Short English statement

Must a complete theory in a countable language have either at most countably many countable models or as many as there are real numbers?

Research attempt: coding the upper bound and constructing continuum many models

Status. We prove the assertion under CH and exhibit a complete countable theory with continuum many countable models by an explicit construction. Neither result settles Vaught's conjecture without CH. The primary article [S1], whose indexed abstract and introduction were inspected, treats specified classes of partial orders; this attempt does not claim its conclusions for all theories.

1. The general coding bound and its limited CH consequence

There are at most $2^{\aleph_0}$ structures on universe $\mathbb N$ in a countable finitary language. Each relation is a subset of a finite Cartesian power of $\mathbb N$, each function can be coded by its graph, and constants by their values. The union of the countably many coordinate sets is countable, so one binary sequence codes the whole structure. Every countably infinite structure is isomorphic to one on $\mathbb N$. Finite structures add at most countably many possibilities. Hence \[I(T,\aleph_0)\leq2^{\aleph_0}.\] Under CH the continuum is $\aleph_1$, with no cardinal strictly between countable and continuum, and the conjectured dichotomy follows immediately. This is a conditional proof only: assuming CH to remove the intermediate cardinals is not a proof that theories cannot realize them in other universes.

2. A complete theory of independent unary predicates

Take language $L=\{P_n:n\in\mathbb N\}$. Let $T$ assert that every finite Boolean combination of the predicates is realized by infinitely many elements. More explicitly, for each disjoint finite $I,J\subset\mathbb N$ and each positive integer $k$, assert at least $k$ elements satisfying all $P_i$ for $i\in I$ and all $\neg P_j$ for $j\in J$.

This theory eliminates quantifiers. To check the existential step, put a quantifier-free formula involving an extra variable $z$ into disjunctive normal form. In each conjunction, an equality $z=x_i$ allows substitution and removes $z$. If no such equality occurs, the constraints on $z$ are finitely many unary literals and finitely many inequalities $z\ne x_i$. An inconsistent pair of unary literals makes the conjunction false; otherwise the relevant Boolean cell is infinite, so avoiding finitely many parameters is possible. All remaining constraints involve the free variables only. Iterating removes quantifiers. Sentences then have fixed truth values, so $T$ is complete.

3. An explicit injection from reals into isomorphism types

Let $D\subset2^{\mathbb N}$ be the countable set of eventually-zero binary sequences. Every finite pattern occurs in some member of $D$. For each $r\in2^{\mathbb N}\setminus D$, define a countable structure $M_r$ with universe $(D\cup\{r\})\times\mathbb N$ by \[P_n(s,k)\quad\Longleftrightarrow\quad s(n)=1.\] Each finite Boolean cell is infinite because a suitable $s\in D$ has infinitely many copies $(s,k)$. Thus $M_r\models T$. An isomorphism preserves every named predicate, and therefore preserves the full binary sequence of truth values of each element. The set of realized sequences in $M_r$ is exactly $D\cup\{r\}$. If $r\ne r'$, these sets differ, so $M_r$ and $M_{r'}$ cannot be isomorphic. Removing countably many reals leaves continuum many, yielding $I(T,\aleph_0)=2^{\aleph_0}$ by the upper bound.

4. Verification and the missing general theorem

The finite-pattern axiom is weaker than requiring every infinite binary pattern to occur. The construction exploits exactly that distinction: all $M_r$ agree on every first-order sentence, yet differ on which complete unary types they realize. A purported back-and-forth based only on the finite patterns can fail when it tries to map an element realizing $r$ to a structure omitting $r$. This is the adversarial test of completeness versus isomorphism, and it explains why quantifier elimination does not imply countable categoricity in a countably infinite language. The argument uses no computational census or claimed search of all theories. A uniform dichotomy for arbitrary countable complete theories in the absence of CH remains the exact unresolved step.

Sources

• S1 Sharp Vaught's conjecture for some classes of partial orders. https://www.sciencedirect.com/science/article/abs/pii/S0168007224000083. Formulation source.