Enderton 3.5 Problem 1

Printable View

December 26th 2011, 05: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?
December 26th 2011, 11:14 AM
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$ .
December 27th 2011, 07: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.
December 27th 2011, 10: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$ .