# Enderton 3.5 Problem 1

• Dec 26th 2011, 06:42 AM
logics
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?
• Dec 26th 2011, 12:14 PM
emakarov
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$.
• Dec 27th 2011, 08:33 AM
logics
Re: Enderton 3.5 Problem 1
Quote:

Originally Posted by emakarov
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.
• Dec 27th 2011, 11:59 AM
emakarov
Re: Enderton 3.5 Problem 1
Quote:

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