My question is: within a system $S$ where $S$ is any extension of $Q$ (Robinson's Arithmetic), and when $P(y)$ is a provability predicate for $S$, when is $(X \rightarrow P(X))$ provable?

By definition of a provability predicate, it is always the case that if $X$ is provable in $S$ then $P(X)$ is provable in $S$. But this, as I understand it, is not the same as $(X \rightarrow P(X))$ being provable in $S$. So when is this the case?


One instance where this holds is when $P$ is $\Sigma_1$ and $S$ is a bit stronger than $Q$: a sufficiently strong (consistent, recursively axiomatizable) theory of arithmetic (PA is massive overkill) proves that it proves every true $\Sigma_1$ sentence. I don't recall if $Q$ has this property.

We can get a partial reversal under a correctness assumption on $S$. Suppose $T$ is an appropriately-strong theory which proves "$S$ is sound" *(this is really a scheme: $T$ proves $P(X)\rightarrow X$ for each $X$, where again $P$ is the provability predicate for $S$)*. Then for each $X$, $T$ proves "If $S$ proves $X\rightarrow P(X)$, then $X\iff P(X)$," and $P(X)$ is a $\Sigma_1$ sentence regardless of the complexity of $X$.

  • Note that $S$ itself doesn't prove its own soundness, and see Lob's theorem.

Another example occurs whenever $S$ proves its own inconsistency, which can happen even if $S$ is consistent (consider PA + $\neg$Con(PA)). In this case $S$ trivially proves $X\rightarrow P(X)$ for each $X$, since $S$ proves $P(X)$ for each $X$.

  • Note that this means that we can't get a general reversal to the situation above.

Meanwhile, when you write

this, as I understand it, is not the same as $(X\rightarrow P(X))$ being provable in $S$,

you're absolutely right. Let's assume PA is sound. We know that the $\Sigma_2$-theory of arithmetic is not recursively enumerable, but the set of PA-provable $\Sigma_2$-sentences is; thus, since by soundness there is no false $\Sigma_2$-sentence which is PA-provable, there must be a true $\Sigma_2$-sentence which is not PA-provable. Letting $X$ be such a sentence, we have (again, by soundness of PA) that PA can't prove $X\rightarrow P(X)$.

  • $\begingroup$ Correct (+1), but everything you wrote about $\Sigma_2$ in the last paragraph is also correct for $\Pi_1$. And of course, we actually know some specific true but PA-unprovable $\Pi_1$ sentences, e.g., Con(PA) or Gödel's "I am PA-unprovable." $\endgroup$ – Andreas Blass Apr 2 at 18:03
  • $\begingroup$ Thank you very much for the detailed answer, very informative and an interesting read! $\endgroup$ – Atlas Apr 2 at 19:53

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.