How can a theory be decidable but incomplete?

Question

I can see how a theory can be complete but undecidable.

But I have trouble with the decidable but incomplete.

I saw some examples, but is there a property or how?

Edit: I saw the question marked as duplicate, but I am hoping to learn what property makes theories both decidable and incomplete rather than examples. The answers there focus more on complete and undecidable

Answer 1

For simplicity, by "theory" I mean "consistent, but not necessarily deductively closed, set of sentences."

---

There is an easy recipe for whipping up decidable incomplete theories in a given language:

Suppose $\Sigma$ is a finite language (= finitely many function, constant, and relation symbols). Let $T_\Sigma$ be the $\Sigma$-theory consisting of the single sentence $$\forall x,y,z(x=y\vee y=z\vee x=z).$$ The models of $T$ are exactly the $\Sigma$-structures with at most two elements.

• Decidability: Since $\Sigma$ is finite, there are (up to isomorphism) only finitely many models of $T$ (this is a fancy way of saying that up to isomorphism there are only finitely many structures of bounded finite size in a given finite language). Fix representatives $\mathcal{M}_i$ ($1\le i\le n$). Each $\mathcal{M}_i$ is finite, and we can computably check whether a sentence is true in a finite structure (this is a good exercise), so to tell whether $T\models\varphi$ we just ask "Is $\varphi$ true in each $\mathcal{M}_i$?"

  • That is: $T$ is decidable since it has finitely many models, each of which has a decidable theory.

• Incomplete: $T$ does not decide whether the sentence $$\forall x,y(x=y)$$is true, since (this is a good exercise) $T$ has at least one model of size exactly $1$ and at least one model of size exactly $2$.

Basically, $T$ is strong enough to limit us to an "easily-checkable" set of possibilities, but still leaves some variety amongst those possibilities. Knowing all the options doesn't mean there aren't any options.

The following generalization of the above is a good exercise:

Suppose $T_1,...,T_n$ are decidable theories in a given language. Then the theory $$S=\{\varphi_1\vee...\vee\varphi_n: \varphi_1\in T_1,...,\varphi_n\in T_n\}$$ is decidable. (HINT: show the models of $S$ are exactly the structures satisfying some $T_i$.)

This lets us build incomplete decidable theories from complete decidable theories: simply take as our $T_i$s a bunch of decidable, complete, but mutually inconsistent theories.

---

It is worth noting that there are simple-looking theories which are not in fact decidable. For example, consider the empty theory $E$ in the language of arithmetic. There is a finitely axiomatizable undecidable theory $Q$ in this language; letting $\varphi$ be the conjunction of the axioms of $Q$, we have (by the deduction theorem) $$Q\models \theta\quad\iff\quad E\models\varphi\rightarrow\theta.$$ Basically, the set of consequences of the empty theory in a given language is at least as complicated as the set of consequences of any finitely axiomatizable theory in that language. (See also here for some notes on the behavior of finitely axiomatizable theories which are somewhat relevant to this question.)