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