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?
Best 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?