Is PA provably definable

incompletenesslogicpeano-axioms

A set of sentences $S$ from the language of arithmetic is called definable if there is a formula $\phi(x)$ such that $\mathbb{N} \models \phi(n)$ iff $n$ is the Gödel number of a formula from $S$.

A stronger notion:

$S$ is called provably definable if there is a formula $\phi(x)$ such that $PA \vdash \phi(n)$ iff $n$ is the gödel number of a member of $S$ and $PA \vdash \neg \phi(n)$ otherwise.

I know that PA is definable. However it seems that some of the provability rules used in the proof of Gödel's theorem require PA to be provably definable, e.g.

For any sentence $\phi$, if $PA \vdash \phi$ then $PA \vdash Pr_{PA}(\ulcorner \phi \urcorner)$.

Here $Pr_{PA}$ denotes the provability predicate. So is PA provably definable and how might one prove this? Many thanks!

Best Answer

No. If the set of theorems of $\sf PA$ were provably definable by the formula $\phi(x),$ then we could use the diagonalization lemma to find a sentence $S$ such that $ \mathsf{PA}\vdash S\leftrightarrow \lnot \phi(\ulcorner S\urcorner).$ But then we have $$\ulcorner S\urcorner \in \operatorname{Th}(\mathsf{PA}) \iff \mathsf{PA}\vdash S \iff \mathsf{PA}\vdash \lnot\phi(\ulcorner S\urcorner) \iff \ulcorner S\urcorner \notin \operatorname{Th}(\mathsf{PA}).$$

The example you give just means that $\sf PA$ can prove all positive instances of membership in $\operatorname{Th}(\sf PA) $, not necessarily the negative ones.

In fact, the provably definable sets are exactly the computable sets, whereas $\operatorname{Th}(\sf PA)$ is a set that is computably enumerable but not computable.