# Enderton 3.7 Problem 2

Printable View

• Jan 14th 2012, 08:32 AM
logics
Enderton 3.7 Problem 2
2. Let $\displaystyle T$ be a theory in a recursively numbered language, and assume that there is an interpretation of $\displaystyle \text{Cn }A_E$ into $\displaystyle T$. Show that $\displaystyle T$ is strongly undecidable; i.e., whenever $\displaystyle T^\prime$ is a theory in the language for which $\displaystyle T \cup T^\prime$ is consistent, then $\displaystyle \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 $\displaystyle \pi$ be such an interpretation of $\displaystyle \text{Cn }A_E$ into $\displaystyle \Pi$ for which $\displaystyle \Pi \subseteq T$. Let $\displaystyle \Delta$ be the consistent theory $\displaystyle \text{Cn}(T^\prime \cup \Pi)$. Let $\displaystyle \Delta_0$ be the corresponding theory $\displaystyle \pi^{-1}[\Delta]$ in the language of number theory. Since $\displaystyle \Delta$ is the consistent theory, $\displaystyle \Delta_0$ is a consistent theory such that $\displaystyle A_E \subseteq \Delta_0$ (from Section 2.7). By Theorem 35C, $\displaystyle \sharp \Delta_0$ is not recursive, which follows that $\displaystyle \sharp \Delta$ is not recursive (by the arguments in page 273).

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

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