Complete finitely axiomatizable theory of a single binary relation with any finite number of countable models other than 1 or 2.

Question

I am interested in this question, which asks for a complete finitely axiomatizable theory with three countable models.

The standard example of $(\mathbb{Q}, <)$ with an ascending sequence of constants $c_1, c_2, \cdots$ doesn't work here because we need infinitely many sentences to capture the $c_i < c_{i+1}$ relationships among the constants.

However, starting with a Dense Linear Orders Without Endpoints (DLOWEs) and tweaking in some way is really the only trick I know for producing a complete theory with finitely many countable models.

Adding in another unary predicate $P(\cdot)$ identifying the ascending sequence causes us to lose completeness. We can use $P$ to ask whether the sequence $c_1, c_2, \cdots$ (or some equivalent construction) grows without bound or not and, indeed, whether the sequence approaches a rational.

So, I'm wondering what we can do with just a single binary relation $R$. Is there any way to get a finite number of countable models other than 1 or 2 (which is impossible by the never two theorem) with finitely many sentences?

Answer 1

In fact this question is as hard to answer as the (AFAIK) open one you originally link to:

Every finitely axiomatizable theory $T$ (in a finite language $\Sigma$) is "equivalent" to a finitely axiomatizable $\{R\}$-theory $T'$, where $R$ is a single binary relation symbol.

Equivalence here means bi-interpretability, but all we really need is that $T$ and $T'$ each have the same number of models and that $T'$ is complete if $T$ is. I'll prove this in the specific case where $\Sigma=\{U,V\}$ with both $U$ and $V$ binary; the general case is no harder. More substantively, I'll talk about how to transform one structure into another; I think this makes things clearer (and I think that the translation to theories is straightforward), but let me know if I should add more details.

Suppose $\mathcal{M}=(M;U^\mathcal{M},V^\mathcal{M})$ is a $\Sigma$-structure. We can think of $U^\mathcal{M}$ and $V^\mathcal{M}$ together as defining a "four-valued binary relation:" given (distinct) $m,n\in M$, there are four possibilities for the quantifier-free theory of the substructure $\{m,n\}$. We'll encode these four possibilities via graphs as follows:

• If $(m,n)\in U^\mathcal{M}\cap V^\mathcal{M}$, then we'll build a length-three chain between them.

• Similarly, the other three possibilities will be represented by length-four, -five, and -six chains.

• Finally, to distinguish our "original" elements from our "chain-building" elements, we'll also add a loop from each $m$ to itself.

For example, let $M=\{1,2,3\}$, let $U^\mathcal{M}$ be the usual $\le$-relation, and let $V^\mathcal{M}=\{(1,2)\}$. Then our new structure $\mathcal{M}'$ looks like the following:

Basically, directed graphs are maximally complicated from a model-theoretic perspective.