Results 1 to 4 of 4

Thread: 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 $\displaystyle R$ such that $\displaystyle \sharp \text{Cn }A_E \subseteq R$ and $\displaystyle \sharp \{\sigma\text{ }|\text{ } (\neg \sigma) \in \text{Cn }A_E\} \subseteq \overline{R}$, the complement of $\displaystyle R$. (This result can be stated: The theorems of $\displaystyle A_E$ cannot be recursively separated from the refutable sentences.) Suggestion: Make a sentence $\displaystyle \sigma$ saying "My Gödel number is $\displaystyle not$ in $\displaystyle R$." Look to see where $\displaystyle \sharp \sigma$ is.

    The definition of $\displaystyle 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 $\displaystyle \text{Cn } A_E$ denotes a set of consequences of $\displaystyle A_E$.

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

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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 $\displaystyle A_E$ by some formula $\displaystyle \rho(x)$ (lecture 12, slide 10). By the fixpoint theorem, there exists a formula $\displaystyle \sigma$ such that $\displaystyle A_E\vdash\sigma\leftrightarrow\neg\rho(S^{\sharp \sigma}0)$. Thus, $\displaystyle \sigma$ says that its Gödel number is not in R.

    Consider two cases: $\displaystyle \sharp\sigma\in R$ and $\displaystyle \sharp\sigma\notin R$ and use the fact that R is representable in $\displaystyle A_E$ by $\displaystyle \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 $\displaystyle A_E$ by some formula $\displaystyle \rho(x)$ (lecture 12, slide 10). By the fixpoint theorem, there exists a formula $\displaystyle \sigma$ such that $\displaystyle A_E\vdash\sigma\leftrightarrow\neg\rho(S^{\sharp \sigma}0)$. Thus, $\displaystyle \sigma$ says that its Gödel number is not in R.

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

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

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

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

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Enderton 3.5 Problem 1

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

    Quote Originally Posted by logics View Post
    By the fixed-point theorem, there exists a formula $\displaystyle \neg \sigma$ such that $\displaystyle 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 $\displaystyle \neg\sigma$ is a fixpoint of $\displaystyle \rho(x)$, i.e., $\displaystyle \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 $\displaystyle \sigma$ that says, informally,

    "I am not in R" (*)

    Then if $\displaystyle \sigma$ is in R, then (*) means that $\displaystyle \sigma$ is refutable, and all refutable formulas are not in R by the assumption about R. If, on the other hand, $\displaystyle \sigma$ is not in R, then (*) means that $\displaystyle \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: $\displaystyle \sharp\sigma\in R$ and $\displaystyle \sharp\sigma\notin R$ and use the fact that R is representable in $\displaystyle A_E$ by $\displaystyle \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: Jan 5th 2012, 11:49 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum