$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$.


  • $\begingroup$ $\sum\neq\Sigma$. $\endgroup$ – 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.

This weaker fact is still enough to finish the proof, though.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.