I'm working through Raymond Smullyan's books "Goedel's Incompleteness Theorems" and I can't for the life of me figure this exercise out:
Prove that if all true $\Sigma_0$-sentences are provable in $S$ and $S$ is $\omega$-consistent, then all $\Sigma_1$-sets are representable in $S$
So I figure that this is an exercise in using the lemma given in the book:
If $S$ is $\omega$-consistent then all enumerable sets are representable in $S$
So I just have to show that all $\Sigma_1$-sets are enumerable. The definition provided is that a formula $F(v_1,v_2)$ enumerates a set $A$ in $S$ if for all numbers $n$ it holds that:
(1) If $n \in A$ then there exists at least one $m \in \mathbb{N}$ such that $F(\bar{n},\bar{m})$ is provable in $S$
(2) If $n \notin A$ then $\forall m \in \mathbb{N}$, $F(\bar{n}, \bar{m})$ is refutable in $S$
But I'm not sure where to go from there. I figure I need a true $\Sigma_0$-sentence (so it will be provable by assumption, and if it isn't true then it will be refutable since $S$ is consistent) that fulfils the conditions above. I'm not sure how to go about this or if this is the right idea.
Thanks in advance for any help.
I assume that by "all true $\Sigma_0$ sentences" you are referring to the truth in the standard model of natural numbers, i.e. $\mathbb N$, and henceforth that $\mathbb N$ is a model of $S$.
By definition a $\Sigma_1$-set is one for which there is a formula $\varphi(x) \in \Sigma_1$ such that $n \in A$ if and only if $S \vdash \varphi(\bar n)$.
By definition of $\Sigma_1$ there must exists a formula $\psi(x,y) \in \Sigma_0$ such that $\varphi(x) \equiv \exists y. \psi(x,y)$. From this we have that $n \in X$ if and only if $S \vdash \exists y. \psi(\bar n,y)$
From this, using the $\omega$-consistency, you should be able to easily prove your claim, i.e. that $A$ is enumerable.
I hope this helps. If not feel free to ask additional details.