Return to Answer

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 these slides for a bit more details. (A paper is coming soon, hopefully.)

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).

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).

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 these slides for a bit more details. (A paper is coming soon, hopefully.)

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.

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 these slides for a bit more details. (A paper is coming soon, hopefully.)

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).

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 these slides for a bit more details. (A paper is coming soon, hopefully.)

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 these slides for a bit more details. (A paper is coming soon, hopefully.)

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.