Results 1 to 4 of 4

Math Help - Enderton 3.5 Problem 1

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.5 Problem 1

    Show that there is no recursive set R such that \sharp \text{Cn }A_E \subseteq R and \sharp \{\sigma\text{ }|\text{ } (\neg \sigma) \in \text{Cn }A_E\} \subseteq \overline{R}, the complement of R. (This result can be stated: The theorems of A_E cannot be recursively separated from the refutable sentences.) Suggestion: Make a sentence \sigma saying "My Gödel number is not in R." Look to see where \sharp \sigma is.

    The definition of A_E is given in the previous slides (cs.nyu.edu/courses/fall09/G22.2390-001/lec/lec11_h4.ps) and the Enderton textbook (page 203), while \text{Cn } A_E denotes a set of consequences of A_E.

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

    To start this problem, if \sigma says "My Gödel number is not in R.", then
    how do I see where \sharp \sigma is?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Enderton 3.5 Problem 1

    Suppose that there is a recursive set R with these properties. Since it is recursive, it is representable in A_E by some formula \rho(x) (lecture 12, slide 10). By the fixpoint theorem, there exists a formula \sigma such that A_E\vdash\sigma\leftrightarrow\neg\rho(S^{\sharp \sigma}0). Thus, \sigma says that its Gödel number is not in R.

    Consider two cases: \sharp\sigma\in R and \sharp\sigma\notin R and use the fact that R is representable in A_E by \rho.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.5 Problem 1

    Quote Originally Posted by emakarov View Post
    Suppose that there is a recursive set R with these properties. Since it is recursive, it is representable in A_E by some formula \rho(x) (lecture 12, slide 10). By the fixpoint theorem, there exists a formula \sigma such that A_E\vdash\sigma\leftrightarrow\neg\rho(S^{\sharp \sigma}0). Thus, \sigma says that its Gödel number is not in R.

    Consider two cases: \sharp\sigma\in R and \sharp\sigma\notin R and use the fact that R is representable in A_E by \rho.
    Could you check if the following attempt is O.K?

    Suppose there is a recursive set R having the required properties. Suppose also some formula \rho(x) represent R. By the fixed-point theorem, there exists a formula \neg \sigma such that A_E\vdash\ \neg \sigma\leftrightarrow\rho(S^{\sharp \neg\sigma}0). Then, \sharp(\neg \sigma) \in R. Either  \sigma \in \text{Cn }A_E or \neg \sigma \in \text{Cn }A_E (This part is not clear). Since \sharp \text{Cn }A_E \subseteq R by hypothesis, we have \neg \sigma \in \text{Cn }A_E.

    Since A_E\vdash\ \sigma\leftrightarrow \neg\rho(S^{\sharp \neg\sigma}0), we also have \neg \sigma \in \text{Cn }A_E and \sharp(\neg \sigma) \notin R, contradicting that \sharp \text{Cn }A_E \subseteq R.

    Therefore, no recursive set R having the required properties exists.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Enderton 3.5 Problem 1

    Quote Originally Posted by logics View Post
    Suppose there is a recursive set R having the required properties. Suppose also some formula \rho(x) represent R.
    This does not need to be supposed; the assumption that R is recursive implies this. It would be better to say, "Let \rho be the formula that represents R."

    Quote Originally Posted by logics View Post
    By the fixed-point theorem, there exists a formula \neg \sigma such that A_E\vdash\ \neg \sigma\leftrightarrow\rho(S^{\sharp \neg\sigma}0).
    The fixpoint theorem does not guarantee that the fixpoint formula is a negation. More importantly, here \neg\sigma is a fixpoint of \rho(x), i.e., \neg\sigma says, "I am in R." I am not sure it is possible to get a contradiction from this. The point of the fixpoint construction is to have a formula \sigma that says, informally,

    "I am not in R" (*)

    Then if \sigma is in R, then (*) means that \sigma is refutable, and all refutable formulas are not in R by the assumption about R. If, on the other hand, \sigma is not in R, then (*) means that \sigma is provable, and all provable formulas are in R. In both cases we get a contradiction.

    I suggest you follow this plan.
    Quote Originally Posted by emakarov View Post
    Consider two cases: \sharp\sigma\in R and \sharp\sigma\notin R and use the fact that R is representable in A_E by \rho.
    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