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

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 $\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.

Re: Enderton 3.5 Problem 1

Quote:

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."

Quote:

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.

Quote:

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