Skip to main content
4 of 4
give a reference
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

Any theory that can represent all recursive functions has no consistent decidable extension, however there are such theories that do not interpret even as weak an arithmetic as Robinson’s theory $R$, see my paper Recursive functions and existentially closed structures (arXiv:1710.09864 [math.LO], to appear in Journal of Mathematical Logic).

You don’t even need to represent all recursive functions. Fix a recursively inseparable pair of r.e. predicates $A,B\subseteq\mathbb N$. Let $L$ be the language consisting of one unary predicate $P$, and constants $\overline n$ for every $n\in\mathbb N$, and let $T$ be the (recursively axiomatizable) theory axiomatized by $P(\overline n)$ for $n\in A$, and $\neg P(\overline n)$ for $n\in B$. Then $T$ has no decidable consistent extension, and it does not interpret much of anything (in particular, if $S$ is a theory in a finite language interpretable in $T$, then $S$ is also interpretable in a finite-language fragment of $T$, and as such does have a decidable extension).

Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208