I was reading R. Smullyan's book, Gödel's Incompleteness Theorems and got stuck at an exercise:
In the following problem $P$ denotes the set of Gödel numbers of provable statements in system $\mathcal{L}$. A set of natural number $A$ is said to be expressible in $\mathcal{L}$ if there exists a predicate $H$ such that, $H(n)\ \text{is true}\iff n\in A$. For any natural number $n$, let $E_n$ be the sentence in $\mathcal{L}$ with Gödel number $n$. Let $d(n)$ be the Gödel number of the sentence $E_n(n)$. Now for any set $A$ of natural numbers we denote by $A^{\ast}$, the set of natural numbers which satisfies the condition: $n\in A^{\ast}\iff d(n)\in A$. A system $\mathcal{L}$ is said to be incomplete if there is a sentence that is neither provable nor refutable in $\mathcal{L}$. A system $\mathcal{L}$ is said to be correct if all provable statements are true and all refutable statements are false.
Problem: Suppose $\mathcal{L}$ is a correct system such that the following two conditions hold:
- The set $P^{\ast}$ is expressible in $\mathcal{L}$,
- For any predicate $H$, there is a predicate $H'$, such that for every $n$, the sentence $H'(n)$ is provable in $\mathcal{L}$ if and only if $H(n)$ is refutable in $\mathcal{L}$.
Then $\mathcal{L}$ is incomplete.
My attempt: Let $H$ be the predicate that expresses $P^{\ast}$. Let $H'$ be the predicate corresponding to $H$ as guaranteed by condition 2. Let $h$ be the Gödel number of $H'$. Then \begin{multline} H'(h)\ \text{is provable}\iff H(h)\ \text{is refutable}\implies H(h)\ \text{is not true}\\\iff h\not\in P^{\ast}\iff d(h)\not\in P\implies H'(h)\ \text{is not provable} \end{multline} Hence I have shown that the sentence $H'(h)$ cannot be provable. Now I need to show that $H'(h)$ is also not refutable. This is where I am stuck. Any help will be appreciated.
Addendum: I have figured out a way to prove the problem. I just want you to verify the proof.
Suppose $H'(h)$ is refutable. This would mean $H'(h)$ is not true and hence not provable, which means $H(h)$ is not refutable. If the system $\mathcal{L}$ were indeed complete, then this would mean that $H(h)$ is true (because a false statement which is not refutable makes the system incomplete, as that statement is also not provable under the assumption of correctness). $$H(h)\ \text{is true}\iff h\in P^{\ast}\iff d(h)\in P$$ Now $d(h)$ is the Gödel number of $H'(h)$, so $d(h)\in P$ means that $H'(h)$ is provable, contradicting our assumption that it is refutable. Hence the system cannot be complete.