# Decidable but incomplete arithmetical theories?

There are celebrated examples of theories that are both decidable and incomplete (the theory of algebraically closed fields, various toy theories with only finite models). But are there any examples of arithmetical theories that are both decidable and incomplete?

I'm not entirely sure what I mean by "arithmetical theory", but at a first pass I suppose I mean any theory whose signature is some sub-signature of (0, s, +, ×, <) and which has the associated standard model of the natural numbers as a model. And for the avoidance of doubt, by "incomplete" I mean negation-incomplete, i.e. there is some sentence S such that neither S nor not-S is a theorem.

Since the theory is decidable, it must be recursively enumerable. It must also be weaker than Robinson arithmetic. Since it has the standard model of the natural numbers as a model, it must be omega-consistent.

That's as far as I've got and now I'm stuck. Any guidance would be greatly appreciated.

• While not in the spirit of what you're asking, the empty theory in the empty signature satisfies all the requirements you've imposed. I'm not sure how to formally specify what you're looking for (you want it to actually contain some non-trivial arithmetic), but maybe this is a "you'll know it when you see it" kind of thing. Commented Jul 18 at 15:37
• @ChrisEagle Ah, of course you're right. Thank you. Maybe one way to sharpen the challenge is to demand that the theory have no finite models, or that all of its models contain an ω-sequence. Commented Jul 18 at 15:43

Take the language $$\{+,<,s\}$$ and the theory consisting of:

• All true sentences in $$\{+,<\}$$ (so basically, Presburger arithmetic without successor).

• The sentence saying "Either for all $$x$$ we have $$s(x)=x$$ or for all $$x$$ we have $$s(x)$$ = the smallest number $$>x$$."

This is clearly incomplete, and is decidable since Presburger arithmetic itself is. To avoid this (and similar) tricks, we could require the theory to not have any extensions by finitely many sentences which are (consistent and) complete (i.e. the Lindenbaum algebra of the theory should not have any coatoms).

EDIT: in response to a comment, here's another example. In the language $$\{s,0,1,+,<\}$$ for simplicity, look at the theory consisting of the following:

• Presburger arithmetic phrased in the language $$\{0,1,+,<\}$$, but without reference to $$s$$.

• The sentences $$\forall x,y[y and $$\forall x[s(x)=x+1\vee s(x)=x]$$, so $$s$$ behaves like successor "for a while" and then is the identity function.

• Sentences asserting that $$\{x: s(x)=x+1\}$$ forms a model of Presburger arithmetic.

Basically, a model of this theory looks like a pair $$(M,N)$$ of models of Presburger arithmetic, where $$M$$ is an initial segment of $$N$$; the behavior of $$s$$ just serves to "locate" $$M$$ inside $$N$$. This theory is decidable and incomplete, but all of its models extend the standard model (and in particular have $$s$$ behave as successor there), so "incompleteness is confined to nonstandard elements" in a reasonable sense.

Again, this trick can be blocked by strengthening "incomplete" to "not complete-mod-finite."

• Wonderful! Thank you. I appreciate the strategy of tweaking PrA to get an independent sentence. I would still be fascinated to know if there is an example where the source of the incompleteness is confined to non-standard elements (if that makes sense). Commented Jul 18 at 20:45
• @ac2357 See my edit! Commented Jul 18 at 20:56
• Lovely, thanks again! Commented Jul 18 at 21:42