I'm still reading Raymond Smullyan's book on Gödel's incompleteness theorems. He uses the following terminology:
- A set $A$ of natural numbers is represented by a formula (in the language of first order arithmetic) $F$ if $F = \{n \mid \text{$F(n)$ is true.}\}$.
- A set $A$ of natural numbers is expressed by a formula (in the language of first order arithmetic) $F$ if $F = \{n \mid \text{$F(n)$ is provable.}\}$, where truth is meant in the standard model of natural numbers here.
He defines a predicate $P(x)$ such that $P(x)$ such that the set $Q$ of Gödel numbers of the provable sentences is expressed by $P$, which is then used for proving the first incompleteness theorem.
Statement. He then states that under the assumption that the logical system in question is $\omega$-consistent, it is true that $Q$ is even represented by the formula $P(x)$.
Question. How to show this?
My attempt. Assume for an $n$ that $P(n)$ be true. We have to show that $P(n)$ is provable. The formula $P(n)$ is given by
$$ \exists m (\mathit{IsAProof}(m) \land \mathit{ContainsFormula}(m, n)), $$
where $\mathit{IsAProof}$ and $\mathit{ContainsFormula}(m, n)$ are formulas with the expectable meaning. By $\omega$-consistency, there exists a number $m$ such that $(\mathit{IsAProof}(m) \land \mathit{ContainsFormula}(m, n))$ is not refutable. From there, I don't know how to continue.
For the converse direction, we assume that $P(n)$ is provable. We have to show that $P(n)$ is true. I guess it would be reasonable to show that under the assumption of $\omega$-consistency, every provable formula is also true. There I don't know how to start.