0
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ The axioms you wrote down do not do what you want. (1) and (3) say that $\equiv$ is an equivalence relation which is either the trivial relation or the equality relation - and as you noted, there are only two such equivalence relations on a countably infinite set, up to isomorphism. But you also also have a relation $R$ in the language, and condition (2) only says that $R$ is a partial order with no greatest element. There are lots of relations like this on a countably infinite set (continuum many up to isomorphism, in fact). $\endgroup$
    – Alex Kruckman
    May 2, 2019 at 3:29
  • $\begingroup$ I guess you included $R$ and (2) in order to make sure $T$ has no infinite models. There's an easier way to do this: include the infinite axiom scheme $\{\varphi_n\mid n\in \mathbb{N}\}$ where $\varphi_n$ is the sentence asserting that there are at least $n$ elements. $\endgroup$
    – Alex Kruckman
    May 2, 2019 at 3:30
  • $\begingroup$ @Noah Schweber do you agree with Alex's first comment? $\endgroup$
    – Doubt
    May 4, 2019 at 13:36
  • 1
    $\begingroup$ Example: Consider $(\mathbb{Z},=,<)$, $(\mathbb{N},=,<)$, and $(\mathbb{Q},=,<)$. In each structure, we interpret $\equiv$ as equality $=$ and $R$ as the standard order relation $<$. These are three non-isomorphic denumerable models of your theory. $\endgroup$
    – Alex Kruckman
    May 4, 2019 at 13:45
  • 1
    $\begingroup$ Yes, that's right. There's no single axiom that will do this, but you can add an infinite scheme of axioms like I suggested in my first comment. If you really want your theory to be finitely axiomatizable, another option is to include $R$, but add extra axioms saying that $R$ is a dense linear order without endpoints - since there is only one denumerable DLO up to isomorphism. $\endgroup$
    – Alex Kruckman
    May 4, 2019 at 15:36

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks Noah. And can you comment on the theory in my original post? Is it indeed decidable yet incomplete? $\endgroup$
    – Doubt
    May 3, 2019 at 17:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .