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 .
is the Gödel number of a formula (with just free) and .
By weakly representability and assumption, for all b and for some a (The definition of P_a is in #1 post), where weakly represents in a theory T. Is this true? How do I proceed from here?
Any help will be appreciated.
I am trying to revise my previous attempt to the proof. Could you check if the following is O.K? Except and , definitions and notations are basically reused from the previous posts.
is the Gödel number of a formula (with just free) and for , where is a class of structures for which is a theory in a recursive numbered language with 0 and S and .
By weakly representability and assumption, for all b and for some , where weakly represents in a theory T.
Furthermore, by definition of and .
Since the choice of is arbitrary, we have for all and . Therefore, if is recursive, then is recursive. However, is not recursive by (*). Therefore, is not recursive.
(*) is not recursive.
Proof. Any definable (in ) set of natural numbers is somewhere on the list . However, is not definable in . If is recursive, then should be definable in . Contradiction. Therefore, P is not recursive.
A general remark is that the proof should be more precise and contain more details. Parts of it are hard to understand.
As I suggested in post #4, define . Then for every weakly representable subset G of there exists a number such that . Indeed, suppose G is represented by some formula , i.e., iff for all b. Then .
Moreover, if is recursive, then we know whether for each and , and so P is recursive. Therefore, for each we know whether , so is recursive. By the assumption that every recursive relation is weakly representable and the fact proven above that every weakly representable relation is a projection of P, there exists an such that . Now consider two cases: and .
In summary, the idea of the proof is the following. We build a relation P that encodes weak representability, i.e., G is a weakly representable set if G is a projection of P, i.e., for some . Then we build a diagonalization of P, i.e., a set H that is different from all projections of P. If we were able to prove that H is weakly representable, we would get a contradiction. We prove that H is weakly representable by showing that P and therefore H are recursive and using the assumption.