Largest decidable subsystem of Robinson's arithmetic $\mathbb{Q}$

Question

What is the largest decidable subsystem of $\mathbb{Q}$? Is there any nice axiomatization of it known?

Edit: Given Noah Schweber's comment, let me rephrase the question, why is there no largest decidable subsystem of $\mathbb{Q}$?

Answer 1

In fact, the situation is even worse than my comment suggests:

$Q$ has no decidable subtheories at all!

First, let's fix a couple definitions for explicitness:

• A theory will mean any set of sentences which is consistent.

  • Most texts don't require consistency, and some texts do require deductive closure (in the jargon to be introduced below: that $T=Thm(T)$). But I think this definition is the best for the current situation.

• When we say that a theory $T$ is decidable, we mean that the set of theorems of $T$ $$Thm(T):=\{\varphi: T\vdash\varphi\}$$ (also called the deductive closure of $T$) is computable.

  • It's worth noting that in computability theory, when talking about a general set of natural numbers (or things "morally equivalent" to such, like sentences via Godel numbering), the words "decidable," "computable," and "recursive" are all synonyms. We're really bad at terminology, y'all.

The key point now is the following:

Lemma: Suppose $T_0\subseteq T_1$ are theories, $T_1$ is finitely axiomatizable over $T_0$ (= there is some single sentence $\varphi$ such that $Thm(T_1)=Thm(T_0\cup\{\varphi\})$), and $T_1$ is undecidable. Then $T_0$ is also undecidable.

Proof: We have $$\psi\in Thm(T_1)\quad\iff\quad \varphi\rightarrow\psi\in Thm(T_0)$$ for every sentence $\psi$. So if we could compute $Thm(T_0)$ we could compute $Thm(T_1)$. $\quad\Box$

Corollary: No subset of $Q$ is decidable.

Proof: $Q$ is finitely axiomatizable, hence is finitely axiomatizable over all its subsets, and is undecidable. Now apply the lemma. $\quad\Box$

On that note, it's worth observing that smaller theories aren't necessarily simpler: Presburger arithmetic is decidable, but the empty theory in the same language isn't. Adding more axioms sometimes results in more simplicity by ruling out those possibilities which could lead to complexity.

---

There's a related, slightly less trivial, situation which is also worth understanding: that of computably enumerable sets. Sets of the form $Thm(T)$ for $T$ a computable theory are c.e., but not all c.e. sets "look like" this, and indeed we can have much more variety in general c.e. sets:

Lemma: If $X$ is c.e. and infinite then $X$ has an infinite computable subset. (In particular, since any finite set is computable, every c.e. but non-computable set has an infinite computable subset.)

Proof: Since $X$ is c.e. we have $X=ran(f)$ for some (total) computable function $f$. Now the computable sequence $$f(0),f(1),f(2),...$$ need not enumerate $X$ in order, but we can extract an increasing subsequence computably: we define by recursion

• $s_0=0$,

• $s_{i+1}=\min\{s>s_i: f(s)>f(s_i)\}$,

and let $a_i=f(s_i)$. Then $$a_0,a_1,a_2,...$$ is a computable increasing sequence, and so the set $$A=\{a_i: i\in\mathbb{N}\}$$ is computable - we have $$n\in A\iff n=a_0\mbox{ or }n=a_1\mbox{ or } ...\mbox{ or }n=a_n,$$ the point being that since the sequence of $a$s is increasing we know when to stop searching. Meanwhile, clearly $A$ is an infinite subset of $X$, so we're done. $\quad\Box$

Incidentally, note that this $A$ depends on $f$; there are many $f$s corresponding to a given $X$, so we do not have a "canonical" computable subset of $X$ in any sense.

So for general c.e. sets the situation is more interesting than for sentences, at least as far as the OP is concerned. Despite this we still never have maximal computable subsets:

Suppose $X$ is a c.e. set which is not computable. Then $X$ has no largest computable subset.

Proof: Suppose $C\subseteq X$ is computable. Since $X$ isn't computable, we have $C\subsetneq X$. Let $a\in X\setminus C$; then $C\cup\{a\}$ is also computable (adding one element to a computable set leaeves it computable), is a subset of $X$, and is a proper superset of $C$. $\quad\Box$