A few questions:
- If $T$ is a decidable and consistent theory, can there be any theory $T' \subset T$ that isn't decidable?
- Is there a decidable theory which isn't complete?
- How can I prove that any recursively-axiomatizable and complete in the number theory language $(+,*,S,0)$ is decidable?
Thanks.
$1.$ Let $T$ be the theory of algebraically closed fields of characteristic $0$. Then $T$ is decidable. Let $T'$ be the theory over the same language with all axioms removed. Or more interestingly let $T'$ be the theory of integral domains. Both of the $T'$ are undecidable: there is no algorithm that, on input any formula $\varphi$, will always halt, and report (correctly) whether or not $\varphi$ is a theorem of $T'$. The proof is by showing that within a suitable finite extension of $T'$, we can develop enough of arithmetic for the classical undecidability results to apply.
Or else let $T$ be the theory with a single binary relation symbol $R$, and axioms that say that $R$ is a dense order with no first or last element. This theory is decidable, but the theory of the single binary relation $R$ with no axioms is not decidable.
$2.$ Let $T$ be the theory over the language which has only the equality symbol, and that has axioms that say that there are at most two objects. Decidable (very), and incomplete.
$3.$ Here is an informal argument. Given a sentence $\varphi$, start listing all formal proofs (of anything) systematically. If the theory is recursively axiomatized, there is an algorithm for generating all proofs.
For each proof, check whether one of $\varphi$ or $\lnot \varphi$ is at the end of the proof. If not, continue listing. By the assumed completeness of the theory, for any input $\varphi$ the algorithm will terminate.