# When is $X \rightarrow P(X)$ provable?

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

• 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." – Andreas Blass Apr 2 at 18:03
• Thank you very much for the detailed answer, very informative and an interesting read! – Atlas Apr 2 at 19:53