Let $E_n$ be an expression with Godel number $n\in\mathbb{N}$. Then we denote the Gödel number of $E_n(n)$ as $d(n)$. Now for a set of natural numbers $A$, we define a set $A^{\ast}$ as follows: $$\forall\ n,\ n\in A^{\ast}\iff d(n)\in A$$ We denote the complement of a set $A$ as $A^c$. First of all note that $$n\in (A^c)^{\ast}\iff d(n)\in A^c\iff d(n)\not\in A\iff n\not\in A^{\ast}\iff n\in(A^{\ast})^c$$ Hence we have $(A^c)^{\ast}=(A^{\ast})^c$ for any natural number set $A$.
Let $P$ be the set of Gödel numbers of sentences provable in a system $\mathcal{L}$. $\mathcal{L}$ is said to be correct if all provable statements are true and all refutable statements are false. Also $E_n$ is said to be a Gödel sentence for a natural number set $A$ if $E_n\ \text{is true}\iff n\in A$. Now below is the problem I am confused about:
Problem: Suppose $\mathcal{L}$ is a correct system that satisfies the following three conditions:
- $E_7$ is the predicate that expresses $P$.
- For any number $n$, if $E_n$ is a predicate, then so is $E_{3n}$, and $E_{3n}$ expresses the complement of the set expressed by $E_n$.
- For any number $n$, if $E_n$ is a predicate, then $E_{3n+1}$ is a predicate, and if $A$ is the set expressed by $E_n$, then $A^{\ast}$ is the set expressed by $E_{3n+1}$.
Now show the following for this system:
(a) Find numbers $a$ and $b$ (either the same or different) such that $E_a(b)$ is a true sentence not provable in $\mathcal{L}$. [There are two solutions in which a and b are both less than 100. Can the reader find them both? ]
(b) Show that there are infinitely many pairs $(a, b)$ such that $E_a(b)$ is true but not provable in $\mathcal{L}$.
(c) Given that $E_{10}$ is a predicate, find numbers $c$ and $d$ such that $E_c(d)$ is a Gödel sentence for the set expressed by $E_{10}$.
[R.Smullyan says that this problem emphasizes the constructive nature of Gödel's proof of his incompleteness theorems.]
My Attempt: $E_7$ expresses $P$ $\implies$ $E_{21}$ expresses $P^c$ $\implies$ $E_{64}$ expresses $(P^c)^{\ast}$. Hence $$E_{64}(64)\ \text{is true}\iff 64\in (P^c)^{\ast}\iff d(64)\in P^c$$ But $d(64)$ is the Gödel number of $E_{64}(64)$. Hence $d(64)\not\in P$ means that $E_{64}(64)$ is not provable. Thus if $E_{64}(64)$ is true then its not provable. The above reasoning also implies that if $E_{64}(64)$ is not true then it is provable, which is impossible as we have assume that our system $\mathcal{L}$ is correct. Hence $E_{64}(64)$ is indeed true but not provable.
Also $E_7$ expresses $P$ $\implies$ $E_{22}$ expresses $P^{\ast}$ $\implies$ $E_{66}$ expresses $(P^{\ast})^c$. So by above reasoning $E_{66}(66)$ has to be true but not provable. Thus I have found two solutions of $(a,b)$ with $a,b<100$, namely $(64,64)$ and $(66,66)$.
Now $E_{66}$ expresses $(P^{\ast})^c$ $\implies$ $E_{3\times 66}$ expresses $P^{\ast}$ $\implies$ $E_{9\times 66}$ expresses $(P^{\ast})^c$. Continuing in this way we have infintely many solutions for $(a,b)$, namely $(9^k\times66, 9^k\times66)$.
From my solution it implies that there are infinitely many predicates that expresses the same set, which seems a little confusing for me. Also I need to know if there can be any solutions for $(a,b)$ with $a\ne b$.
Part (c) is also quite easy. It turns out that if $E_{10}$ expresses $A$, then $E_{31}$ expresses $A^{\ast}$. Then $$E_{31}(31)\ \text{is true}\iff 31\in A^{\ast}\iff d(31)\in A$$ But $d(31)$ is the Gödel number of $E_{31}(31)$. And hence $E_{31}(31)$ is a Gödel sentence for $A$.