# Enderton 3.7 Problem 2

• Jan 14th 2012, 08:32 AM
logics
Enderton 3.7 Problem 2
2. Let $T$ be a theory in a recursively numbered language, and assume that there is an interpretation of $\text{Cn }A_E$ into $T$. Show that $T$ is strongly undecidable; i.e., whenever $T^\prime$ is a theory in the language for which $T \cup T^\prime$ is consistent, then $\sharp T^\prime$ is not recursive.

===============

This is my first attempt to the sketch of the proof based on Theorem 37D. Could you check the following?

Let $\pi$ be such an interpretation of $\text{Cn }A_E$ into $\Pi$ for which $\Pi \subseteq T$. Let $\Delta$ be the consistent theory $\text{Cn}(T^\prime \cup \Pi)$. Let $\Delta_0$ be the corresponding theory $\pi^{-1}[\Delta]$ in the language of number theory. Since $\Delta$ is the consistent theory, $\Delta_0$ is a consistent theory such that $A_E \subseteq \Delta_0$ (from Section 2.7). By Theorem 35C, $\sharp \Delta_0$ is not recursive, which follows that $\sharp \Delta$ is not recursive (by the arguments in page 273).

We also have $\tau \in \Delta$ iff $(\phi \rightarrow \tau) \in T^\prime$, where $\phi$ is the conjunction of the members of $\Pi$.

Therefore, $T^\prime$ is not recursive, nor is $\sharp T^\prime$.