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?

  • 1
    $\begingroup$ 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". $\endgroup$ – Asaf Karagila Apr 22 at 17:54

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?

  • $\begingroup$ 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? $\endgroup$ – Doubt Apr 24 at 2:49
  • $\begingroup$ @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$. $\endgroup$ – Noah Schweber Apr 24 at 2:52
  • $\begingroup$ 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\}$? $\endgroup$ – Doubt Apr 24 at 16:21
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Apr 24 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.