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 .
P is defined in the textbook page 186 (Please refer to the textbook page 186 for detailed descriptions of the definition).
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.
This is one place that is hard to understand. What is K? Is it Mod T? It seems much simpler to say "... and ." In fact, in what follows you need an equivalent condition because weak representability involves provability, not logical consequence. It is not clear why involve model theory and completeness theorem into a problem that is purely about proof theory, i.e., syntax.
By weak representability of which relation? To use the assumption that every recursive relation is weakly representable, you need to show that some relation is recursive. Which relation is it?
To conclude that P is recursive, you need the implication is both directions: .
What is A? It seems like K = Mod T and then A is some element of K, but which one?
Why?
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.