# Is a set recursively enumerable iff it's a set of provable instances of a formula in Peano arithmetic?

$S$ is recursively enumerable $\iff$ There's some formula $S(x)$ in $PA$ such that $PA\vdash S(\bar{n})$ iff $n\in S$.

Is this claim true? Intuitively I would think so. But I only have a somewhat rough reasoning whose corretness I'm not sure about at all. Any suggestions or different perspectives are welcome.

My reasoning is：

1. The "$\Rightarrow$" direction

Every r.e. set is definable by a $\Sigma_1^0$-formula. Hence if $S$ is r.e., there's some $S(x)=\exists n_1,...,n_k \phi(n_1,...,n_k,x)$, where $\phi$ has only bounded quantifiers, such that $\mathcal{N}\vDash S(\bar{n})$ iff $n\in S$.

Now we only need to show $PA\vdash S(\bar{n})$ iff $\mathcal{N}\vDash S(\bar{n})$. By soundness of $PA$, $PA\vdash S(\bar{n})$ implies $\mathcal{N}\vDash S(\bar{n})$. On the other hand, $\mathcal{N}\vDash S(\bar{n})$ implies $\mathcal{N}\vDash \phi(\bar{a_1},...,\bar{a_k},\bar{n})$ for some finite numbers $a_1$,...,$a_k$. Since $\phi$ has only bounded quantifiers, this means $\phi(\bar{a_1},...,\bar{a_k},\bar{n})$ must be a valid sentence (Does it?). Hence $PA\vdash S(\bar{n})$ by completeness of FOL.

2. The "$\Leftarrow$" direction

It's sufficient to show that the set $\{\bar{n}|PA\vdash S(\bar{n})\}$ is r.e.. If we can show it's the domain of some computable function $f$, we are done. Let $F(n)=G(S(\bar{n}))$ where $G(X)$ is the godel number of formula $X$. Now "$m$ is the godel number of a proof of a sentence whose godel number is $n$" is decidable. let $P(m,n)$ be such an algorithm. Then $P(m,F(n))$ is decidable for all $m$ and $n$. Define $f$ by the following algorithm:

for $m,n\ge1$; if $P(m,F(n))=1$, then $f(n)=1$; end

Then $f$ is computable and its domain is $S$.

Q.E.D.

• $\sum\neq\Sigma$. – Asaf Karagila Feb 20 '17 at 15:54

It is indeed a true statement. Your proof is mostly correct, but there's one small mistake (or maybe just an unclear bit) in the "$\implies$" direction: $\phi$ need not be valid. Instead, all we know is that $\phi$ is true in every model of PA - that is, PA$\models\phi$. This isn't quite the same - e.g. in a structure which isn't a model of PA, $\phi$ could fail.