Construct a decidable-yet-incomplete theory

logicmodel-theory

An exercise from Boolos' Computability and Logic asks the reader to give an example of a theory which is decidable but not complete. I am wondering if the following suffices.

Let $T$ be a theory with the following axioms:
$$\begin{align}
\forall x(x\equiv x)\wedge\forall x\forall y(x\equiv y\rightarrow y\equiv x)\wedge\forall x\forall y\forall z((x\equiv y\wedge y\equiv z)\rightarrow x\equiv z)\qquad(1)\\
\forall x\exists y(xRy)\land\forall x\forall y(\neg(xRy\land yRx))\land \forall x\forall y\forall z((xRy\land yRz)\rightarrow xRz)\qquad(2)\\
\forall x\forall y(x\equiv y)\lor\forall x\forall y(x\equiv y\leftrightarrow x=y)\qquad(3)\\
\end{align}$$

(1) defines the equivalence relation, (2) defines an ordering relation $R$ and ensures that all models of $T$ are infinite, and (3) ensures that there are only two isomporphism types of denumerable models.

In particular, the two types of models of (3) are either one of the following:

  • ($\mathcal M_1$) models in which all elements are in the same equivalence class, or
  • ($\mathcal M_2$) models in which each element is in its own equivalence class.

Such a theory $T$, having no finite models, and having exactly two isomorphism types of denumerable models, is decidable, as discussed here. To show that $T$ is incomplete, is it enough to observe that $$\forall x\forall y (x\equiv y)\qquad(A)$$ is satisfied by $\mathcal M_1$ but not $\mathcal M_2$, and hence that neither $A$ nor $\neg A$ is a consequence of $T$?

If so, are there far simpler ways to construct decidable but incomplete models?

Best Answer

I'd say the simplest decidable-but-incomplete theory is the (set of consequences of the) single axiom "$\exists x,y\forall z(x=z\vee y=z)$" (in the empty language). This sentence has exactly two models up to isomorphism, the one-element structure and the two-element structure, and each of these structures is decidable; any theory with finitely many (up to isomorphism) at-most-countable models, each of which is decidable, is itself decidable. A model is decidable if its theory is decidable; note that the theory of a model is always a complete theory.


A less silly trick is the following: given sets $\Gamma,\Delta$ of sentences, consider the new set $$\Gamma\oplus\Delta=\{\gamma\vee\delta: \gamma\in\Gamma,\delta\in\Delta\}.$$ It's easy to check that every model of $\Gamma$ is a model of $\Gamma\oplus\Delta$, and every model of $\Delta$ is a model of $\Gamma\oplus\Delta$. The nontrivial observation is that the converse is also true! Suppose $\mathcal{M}\not\models\Gamma$ and $\mathcal{M}\not\models\Delta$. Then we can find $\gamma\in\Gamma$ and $\delta\in\Delta$ such that $\mathcal{M}\not\models\gamma$ and $\mathcal{M}\not\models\delta$. But then $\mathcal{M}\not\models(\gamma\vee\delta)$, and so $\mathcal{M}\not\models\Gamma\oplus\Delta$.

So the class of models of $\Gamma\oplus\Delta$ is exactly the union of the class of models of $\Gamma$ and the class of models of $\Delta$. In particular, if $\Gamma$ and $\Delta$ are each decidable, then so is $\Gamma\oplus\Delta$: we have $\Gamma\oplus\Delta\vdash\varphi$ iff $\Gamma\vdash\varphi$ and $\Delta\vdash\varphi$. So this lets us combine decidable complete theories to get decidable incomplete theories.

Related Question