7
$\begingroup$

Most true statements independent of PA that I know of is equivalent to some consistency statement. For example

  • Con(PA), Con(PA + Con(PA)), Con(PA + Con(PA) + Con (PA + Con(PA)), $\dots$
  • Goodstein's theorem is equivalent to Con(PA)
  • Any conjunction or disjunction of the above.

Is every true statement independent of PA equivalent to some consistency statement?

By "equivalent to some consistency statement", I mean that $PA \vdash S \iff Con(T)$, for some theory $T$. Also, $T$ should be either finite, or specified by a Turing machine that outputs its axioms (and such that PA proves that the Turing machine never stops outputting statements), so that the description of $T$ doesn't throw PA off.

EDIT: In particular, are there are $\Pi^0_1$ examples?

$\endgroup$
  • 8
    $\begingroup$ No, far from it. Consistency statements, in the sense you intend, are $\Pi^0_1$ statements. It would be more interesting to ask the version of your question where you add this additional syntactical requirement. $\endgroup$ – Andrés E. Caicedo Feb 18 '18 at 1:28
  • 2
    $\begingroup$ Do you have a reference for Goodstein being equivalent to Con(PA)? $\endgroup$ – Wojowu Feb 18 '18 at 8:50
  • $\begingroup$ @SimonHenry I'm afraid that can't be correct. Well-foundedness of $\varepsilon_0$ is a statement much stronger than Con(PA) (in particular, I believe it implies Con(PA+Con(PA))). Also, I don't think Goodstein's theorem (a single sentence) implies full Kirby-Paris theorem (which, formally, can't be even stated in the language of PA, but we can express it as a scheme like well-foundedness). I have recently discovered a reference to the fact that adding a single sentence can't increase the proof-theoretic ordinal, but I don't have it at hand. $\endgroup$ – Wojowu Feb 20 '18 at 16:30
  • $\begingroup$ By all strategy are winning strategy I mean't all recursive strategy. But you're right I went back to Kirby & Paris paper and it seems that you are right and my memories of it were largely oversimmplified. This being said what they proof made me doubt that Goodstein theorem is not stronger than the consistency of PA. $\endgroup$ – Simon Henry Feb 20 '18 at 16:51
9
$\begingroup$

The theory $PA + Con(PA)$ has the property you are asking for, this is the so called Friedman-Goldfarb-Harrington principle (see, e.g., Fifty years of self-reference in arithmetic, p. 366). Formally, for every $\Pi_1$ sentence $\pi$, there is a $\Pi_1$ sentence $\psi$ such that $PA + Con(PA) \vdash \pi \leftrightarrow Con(PA + \psi)$.

EDIT:

That being said, my hunch is that the answer must be "no" for plain $PA$ even though I can't produce a counterexample at the moment.

As observed by Will Sawin, we have that for every $\Pi_1$ sentence $\pi$, there is a $\Pi_1$ sentence $\psi$ such that $PA \vdash \pi \leftrightarrow Con(EA + \psi)$, which gives a positive answer to the OP's modified question.

My hunch is that $Con(EA + \psi)$ can not be replaced by $Con(PA + \psi)$ in the above.

$\endgroup$
  • $\begingroup$ Does that theorem really need the full strength of $PA$ to be proved? f we can prove that $T + Con(T)$ prove $\pi$ is equivalent to $Con(T+ Psi)$ for some theory $T$ weaker than $PA$, then as long as $PA$ proves consistency of $T$, $PA$ will prove the same theorem. $\endgroup$ – Will Sawin Feb 18 '18 at 16:31
  • 1
    $\begingroup$ It is safe to replace PA with elementary arithmetic EA throughout my answer. See Visser's Faith and Falsity in Annals of Pure and Applied Logic, 131(1-3), 2005, pp. 103-131 for a proof. $\endgroup$ – user103227 Feb 18 '18 at 16:41
  • 7
    $\begingroup$ Right, so the answer is "yes" for plain PA, because it is stronger than $EA + Con(EA)$. $\endgroup$ – Will Sawin Feb 18 '18 at 16:45
  • $\begingroup$ Excellent point. If you post that as an answer I'll be happy to upvote yours and remove mine. $\endgroup$ – user103227 Feb 18 '18 at 21:01
  • $\begingroup$ I've edited my answer to reflect Will Sawin's observation. $\endgroup$ – user103227 Feb 20 '18 at 8:57
7
$\begingroup$

$1$-consistency of $PA$ is a true $\Pi_3$ sentence which is not provable in $PA$+{all true $\Pi_1$ sentences} (see this article). Simple (iterated) consistency statements (as you mentioned above) are all (true) $\Pi_1$ sentences, so it is not equivalent to any $\Pi_1$ sentence.

$\endgroup$

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.