Let be a theory in a recursively numbered language (with 0 and S). Assume that all recursive subsets of are weakly representable in . Show that is not recursive. Suggestion: Construct a binary relation such that any weakly representable subset of equals for some , and such that is recursive if is.

Consider the set . See Section 3.0. The argument given there for the "diagonal approach" in the special case 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 that weakly represents in such that

for all in (referred to Enderton pp 241).

is recursive iff (including ) is recursive.

Consider the set of P. If P is recursive, then P is definable in . Then any definable set of natural numbers is somewhere on the list (Enderton pp 186). However, H is not definable in . (Enderton pp 186). Contradiction. Therefore, P is not recursive, so is .