# An incomplete yet decidable theory

I am working on the following exercise from Boolos' Computability and Logic:

Problem. Suppose an axiomatizable theory $$T$$ has only infinite models. Suppose $$T$$ is not complete, [yet has] two isomorphism types of denumerable models. Show that $$T$$ is decidable.

We are told to use the following two results:

Prop. 1 If an axiomatizable theory $$T$$ is complete, then $$T$$ is decidable.

Prop. 2 If $$\Gamma$$ is a denumerably categorical set of sentences having no finite models, then $$\Gamma$$ is complete.

Here is how I would proceed. Take a sentence $$A$$ which for which neither $$A$$ nor $$\neg A$$ is a theorem of $$T$$. Then take $$\Gamma = T\cup\{A\}$$. If we can show that $$\Gamma$$ is a denumerably categorical set, then by Props. 1 and 2 we are finished.

Any hints, though, on how to show that $$T\cup\{A\}$$ is a denumerably categorical set? In other words, why is it the case that adding $$A$$ to $$T$$ causes the isomorphism type to drop from two to one?

• Here's one example. Consider the language $\{R\}$ and the axioms stating "if $R$ is anti-symmetric, then $R$ is a dense linear order without endpoints" and "if $R$ is not anti-symmetric, then $R$ is the trivial equivalence relation". – Asaf Karagila Apr 22 at 17:54

## 1 Answer

If neither $$A$$ nor $$\neg A$$ is a theorem of $$T$$, then both $$T\cup\{\neg A\}$$ and $$T\cup\{A\}$$ must be satisfiable - by the Lowenheim-Skolem theorem, that means that there are denumerable models.

Now when we add (say) $$A$$ to $$T$$, we "lose" a(n isomorphism type of a) denumerable model - namely, the model of $$T\cup\{\neg A\}$$. Since $$T$$ only had two denumerable models to begin with, how many does that leave?

• But how do we know that adding a sentence $A$ to a theory $T$ does not increase (rather than decrease) the number of unique denumerable models? – Doubt Apr 24 at 2:49
• @Doubt You can't gain models by adding sentences. Adding sentences makes it harder, not easier, to satisfy the whole theory: if $\Theta\subseteq\Gamma$ then the class of models of $\Gamma$ is a subclass of the class of models of $\Theta$. Contrapositively, you can't lose models by removing sentences: if $\mathcal{M}\models\Gamma$ and $\Theta\subseteq\Gamma$ then $\mathcal{M}\models\Theta$. – Noah Schweber Apr 24 at 2:52
• Thanks Noah. But suppose $M_1$ and $M_2$ are non-isomorphic models for $T$. Isn't it possible that $M_1$ and $M_2$ are both models of $T\cup\{A\}$, but neither is a model of $T\cup\{\neg A\}$? – Doubt Apr 24 at 16:21
• @Doubt No, that's not possible if $T$ has only two countable models and $T\cup\{\neg A\}$ is consistent: since $T\cup\{\neg A\}$ is consistent, it has a countable model, which can't be isomorphic to either $M_1$ or $M_2$ in the situation you describe (you can't be isomorphic to something satisfying $A$ while satisfying $\neg A$ yourself). But then we get too many isomorphism types of countable models. – Noah Schweber Apr 24 at 16:23