Results 1 to 7 of 7

Math Help - Enderton 3.5 Problem 3

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.5 Problem 3

    Let T be a theory in a recursively numbered language (with 0 and S). Assume that all recursive subsets of \mathbb{N} are weakly representable in T. Show that \sharp T is not recursive. Suggestion: Construct a binary relation P such that any weakly representable subset of \mathbb{N} equals \{b | <a, b> \in P\} for some a, and such that P is recursive if \sharp T is.
    Consider the set H=\{b|<b, b> \notin P\}. See Section 3.0. The argument given there for the "diagonal approach" in the special case 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 \rho that weakly represents P in T such that
    <a, b> \in P \leftrightarrow \rho(S^a0, S^b0) \in T for all a, b in N=(\mathbb{N}; 0, S, <, +, \cdot, E) (referred to Enderton pp 241).
    P is recursive iff T (including \sharp T) is recursive.

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.5 Problem 3

    Quote Originally Posted by logics View Post
    By assumption, there is a formula \rho that weakly represents P in T such that <a, b> \in P \leftrightarrow \rho(S^a0, S^b0) \in T for all a, b in N=(\mathbb{N}; 0, S, <, +, \cdot, E) (referred to Enderton pp 241).
    What is P? The hint contains the desired properties of P, not the definition of P. You have to define it first. Second, why is P weakly representable?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 3

    Quote Originally Posted by emakarov View Post
    What is P? The hint contains the desired properties of P, not the definition of P. You have to define it first. Second, why is P weakly representable?
    P is defined in the textbook page 186 (Please refer to the textbook page 186 for detailed descriptions of the definition).

    <a, b> \in P \leftrightarrow a is the Gödel number of a formula \alpha(v_1) (with just v_1 free) and \models_N\alpha(S^b0).

    By weakly representability and assumption, <b> \in P_a \leftrightarrow \rho(S^a0, S^b0) \in T for all b and for some a (The definition of P_a is in #1 post), where \rho weakly represents P_a in a theory T. Is this true? How do I proceed from here?

    Any help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.5 Problem 3

    Quote Originally Posted by logics View Post
    <a, b> \in P \leftrightarrow a is the Gödel number of a formula \alpha(v_1) (with just v_1 free) and \models_N\alpha(S^b0).
    In this case, P is not recursive because formulas true in \mathbb{N} represent a highly complex set (far more complex than decidable or enumerable sets). Besides, the definition is supposed to depend on T.

    P should be \{\langle a,b\rangle\mid a=\sharp\alpha(x)\text{ and }T\vdash\alpha(S^b0)\}. Then P is recursive if \sharp T is, in conformance to the hint.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 3

    I am trying to revise my previous attempt to the proof. Could you check if the following is O.K? Except P and A, definitions and notations are basically reused from the previous posts.

    <a, b> \in P \leftrightarrow a is the Gödel number of a formula \alpha(v_1) (with just v_1 free) and \models_A\alpha(S^b0) for A \in K, where K is a class of structures for which T is a theory in a recursive numbered language with 0 and S and T=\{\sigma| \sigma \text{ is true in every member of } K\}.

    By weakly representability and assumption, <b> \in P_a \leftrightarrow \rho(S^a0, S^b0) \in T for all b and for some a, where \rho weakly represents P_a in a theory T.

    Furthermore, <b> \in P_a \rightarrow <a, b> \in P by definition of P and P_a.

    Since the choice of a is arbitrary, we have \rho(S^a0, S^b0) \in T \rightarrow <a, b> \in P for all a and b. Therefore, if \sharp T is recursive, then P is recursive. However, P is not recursive by (*). Therefore, \sharp T is not recursive.

    (*) P is not recursive.

    Proof. Any definable (in A) set of natural numbers is somewhere on the list P_1, P_2, \ldots. However, H = \{b : <b, b> \notin P\} is not definable in A. If P is recursive, then H should be definable in A. Contradiction. Therefore, P is not recursive.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.5 Problem 3

    A general remark is that the proof should be more precise and contain more details. Parts of it are hard to understand.

    Quote Originally Posted by logics View Post
    <a, b> \in P \leftrightarrow a is the Gödel number of a formula \alpha(v_1) (with just v_1 free) and \models_A\alpha(S^b0) for A \in K, where K is a class of structures for which T is a theory in a recursive numbered language with 0 and S and T=\{\sigma| \sigma \text{ is true in every member of } K\}.
    This is one place that is hard to understand. What is K? Is it Mod T? It seems much simpler to say "... and T\models\alpha(S^b0)." In fact, in what follows you need an equivalent condition T\vdash\alpha(S^b0) 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.

    Quote Originally Posted by logics View Post
    By weakly representability and assumption, <b> \in P_a \leftrightarrow \rho(S^a0, S^b0) \in T for all b and for some a, where \rho weakly represents P_a in a theory T.
    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?

    Quote Originally Posted by logics View Post
    Since the choice of a is arbitrary, we have \rho(S^a0, S^b0) \in T \rightarrow <a, b> \in P for all a and b. Therefore, if \sharp T is recursive, then P is recursive.
    To conclude that P is recursive, you need the implication is both directions: \rho(S^a0, S^b0) \in T \leftrightarrow \langle a, b\rangle \in P.

    Quote Originally Posted by logics View Post
    (*) P is not recursive.

    Proof. Any definable (in A) set of natural numbers is somewhere on the list P_1, P_2, \ldots.
    What is A? It seems like K = Mod T and then A is some element of K, but which one?

    Quote Originally Posted by logics View Post
    However, H = \{b : <b, b> \notin P\} is not definable in A.
    Why?

    As I suggested in post #4, define P=\{\langle a,b\rangle\mid a=\sharp\alpha(x)\text{ and }T\vdash\alpha(S^b0)\}. Then for every weakly representable subset G of \mathbb{N} there exists a number a such that G=P_a. Indeed, suppose G is represented by some formula \gamma(x), i.e., b\in G iff T\vdash\gamma(S^b0) for all b. Then G=P_{\sharp\gamma}.

    Moreover, if \sharp T is recursive, then we know whether T\vdash\alpha(S^b0) for each \alpha and b, and so P is recursive. Therefore, for each b we know whether \langle b,b\rangle\in P, so H=\{b\mid\langle b,b\rangle\notin P\} 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 a such that H=P_a. Now consider two cases: a\in H and a\notin H.

    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., G=P_a for some a. 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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.5 Problem 3

    Just a remark. I am used to thinking about theories as given by axioms, but the book defines a theory as a set of formulas containing all its corollaries. Therefore, everywhere above T\vdash\alpha can be replaced by \alpha\in T for all formulas \alpha.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton Problem 3.5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 5th 2012, 11:49 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum