Smullyan's Godel's Incompleteness Theorems Chapter 2, Exercise 8

Question

The question asks to prove that for any two Arithmetic sets $A$ and $B$ there are sentences $X$ and $Y$ such that $X$ is true iff $A$ contains the Godel number of $Y$, and $Y$ is true iff $B$ contains the Godel number of $X$.

Since $A$ is arithmetic there is a predicate $F_A(v_1)$ that expresses $A$ and an predicate $H_A(v_1)$ that expresses $A^{\ast} := \left\{m \in \mathbb{N} : d(m)\in A\right\}$, where $d(m)$ is the diagonal of the Godel number $m$. Then, if $h_A$ is the Godel number of $H_A$, then $H_A(h_A)$ is a sentences that is true iff the $A$ contains Godel number of $H_A(h_A)$. I can't figure out how to cross-reference: finding $X$ that asserts the Godel number of $Y$ is in $A$ and finding $Y$ that asserts the Godel number of $X$ is in $B$. Any help is appreciated.

Answer 1

I believe the following proof will work:

Let $H_A$ be a predicate that expresses $A^{\ast}$ and $H_B$ a predicate that expresses $B^{\ast}$. Define $X_1:=H_A\left(\overline{g(H_B(\overline{v_1}))}\right)$, $X:=X_1\left[\overline{g(X_1)}\right]$, and $Y:=H_B\left(\overline{g(X_1)}\right)\left[\overline{g(H_B(\overline{g(X_1)})})\right]$.

Now, $X$ is true iff $X_1\left(\overline{g(X_1)}\right)$ is true iff $H_A\left(\overline{g(H_B(\overline{g(X_1)}))}\right)$ is true iff $g\left( H_B(\overline{g(X_1)})\left[\overline{g(H_B(\overline{g(X_1)})}\right]\right)\in A$ iff $g(Y)\in A$.

And, $Y$ is true iff $H_B(\overline{g(X_1)})$ is true iff $g\left(X_1\left[\overline{g(X_1)}\right]\right)\in B$ iff $g(X)\in B$.

Answer 2

Here is Jeon's answer:

Let $A \subseteq \mathbb{N}$ and $B \subseteq \mathbb{N}$ be two Arithmetic sets.

Then there exist two formulas $H_A \left( v_1 \right)$ and $H_B \left( v_1 \right)$ such that $$ \left( \forall n \in \mathbb{N} \right) \left[ H_A \left( \overline{n} \right) \in \mathcal{T} \leftrightarrow n \in A \right] $$ and $$ \left( \forall n \in \mathbb{N} \right) \left[ H_B \left( \overline{n} \right) \in \mathcal{T} \leftrightarrow n \in B \right] $$ hold.

Denote $F \left[ \overline{x} , \overline{y} \right] : \equiv \forall v_1 \forall v_2 \left( v_1 = \overline{x} \supset \left( v_2 = \overline{y} \supset F \right) \right) $, where $F$ is any formula and $x$ and $y$ are any numbers.

Define $\mathrm{fst} : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ and $\mathrm{snd} : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ by $$\mathrm{fst} \left( x , y \right) := g \left( E_x \left[ \overline{x} , \overline{y} \right] \right)$$ and $$\mathrm{snd} \left( x , y \right) := g \left( E_y \left[ \overline{x} , \overline{y} \right] \right)$$ respectively.

Since $\mathrm{fst}$ and $\mathrm{snd}$ are Arithmetic functions, there exist two formulas $\mathrm{Fst} \left( v_1, v_2, v_3 \right)$ and $\mathrm{Snd} \left( v_1, v_2, v_3 \right)$ such that $$\left( \forall x \in \mathbb{N} \right) \left( \forall y \in \mathbb{N} \right) \left( \forall z \in \mathbb{N} \right) \left[ \mathrm{Fst} \left( \overline{x} , \overline{y} , \overline{z} \right) \in \mathcal{T} \leftrightarrow \mathrm{fst} \left( x , y \right) = z \right]$$ and $$\left( \forall x \in \mathbb{N} \right) \left( \forall y \in \mathbb{N} \right) \left( \forall z \in \mathbb{N} \right) \left[ \mathrm{Snd} \left( \overline{x} , \overline{y} , \overline{z} \right) \in \mathcal{T} \leftrightarrow \mathrm{snd} \left( x , y \right) = z \right]$$ hold.

Define $$\begin{align*} F_1 \left( v_1 , v_2 \right) & : \equiv \forall v_3 \left( \mathrm{Snd} \left( v_1 , v_2 , v_3 \right) \supset H_A \left( v_3 \right) \right) , \\ F_2 \left( v_1 , v_2 \right) & : \equiv \forall v_3 \left( \mathrm{Fst} \left( v_1 , v_2 , v_3 \right) \supset H_B \left( v_3 \right) \right) . \end{align*}$$

Then $$F_1 \left[ \overline{g \left( F_1 \right)} , \overline{g \left( F_2 \right)} \right] \in \mathcal{T} \leftrightarrow H_A \left( \overline{g \left( F_2 \left[ \overline{g \left( F_1 \right)} , \overline{g \left( F_2 \right)} \right] \right)} \right) \in \mathcal{T}$$ and $$F_2 \left[ \overline{g \left( F_1 \right)} , \overline{g \left( F_2 \right)} \right] \in \mathcal{T} \leftrightarrow H_B \left( \overline{g \left( F_1 \left[ \overline{g \left( F_1 \right)} , \overline{g \left( F_2 \right)} \right] \right)} \right) \in \mathcal{T}$$ hold.

Now, take $X : \equiv F_1 \left[ \overline{g \left( F_1 \right)} , \overline{g \left( F_2 \right)} \right]$ and $Y : \equiv F_2 \left[ \overline{g \left( F_1 \right)} , \overline{g \left( F_2 \right)} \right]$.

Then $X \in \mathcal{T} \iff g \left( Y \right) \in A$ and $Y \in \mathcal{T} \iff g \left( X \right) \in B$.

And we are done.