# Thread: Enderton 3.5 Problem 1

1. ## 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?

2. ## 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$.

3. ## Re: Enderton 3.5 Problem 1

Originally Posted by emakarov
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.

4. ## Re: Enderton 3.5 Problem 1

Originally Posted by logics
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."

Originally Posted by logics
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.
Originally Posted by emakarov
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$.