Let $\displaystyle T$ be a theory in a recursively numbered language (with 0 and S). Assume that all recursive subsets of $\displaystyle \mathbb{N}$ are weakly representable in $\displaystyle T$. Show that $\displaystyle \sharp T$ is not recursive. Suggestion: Construct a binary relation $\displaystyle P$ such that any weakly representable subset of $\displaystyle \mathbb{N}$ equals $\displaystyle \{b | <a, b> \in P\}$ for some $\displaystyle a$, and such that $\displaystyle P$ is recursive if $\displaystyle \sharp T$ is.

Consider the set $\displaystyle H=\{b|<b, b> \notin P\}$. See Section 3.0. The argument given there for the "diagonal approach" in the special case $\displaystyle T=\text{Th }N$ can be adapted here.

Remark: This exercise gives a version of the result, "Any sufficient strong theory is undecidable.".

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

Could you check if my following sketch of proof is O.K?

By assumption, there is a formula $\displaystyle \rho$ that weakly represents $\displaystyle P$ in $\displaystyle T$ such that

$\displaystyle <a, b> \in P \leftrightarrow \rho(S^a0, S^b0) \in T$ for all $\displaystyle a, b$ in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$ (referred to Enderton pp 241).

$\displaystyle P$ is recursive iff $\displaystyle T$ (including $\displaystyle \sharp T$) is recursive.

Consider the set $\displaystyle P_a = \{b | <a, b> \in P\}$ of P. If P is recursive, then P is definable in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$. Then any definable set of natural numbers is somewhere on the list $\displaystyle P_1, P_2, \ldots$ (Enderton pp 186). However, H is not definable in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$. (Enderton pp 186). Contradiction. Therefore, P is not recursive, so is $\displaystyle \sharp T$.