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?

Improve this question
$\endgroup$
4
  • 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, 2018 at 1:28
  • 2
    $\begingroup$ Do you have a reference for Goodstein being equivalent to Con(PA)? $\endgroup$
    – Wojowu
    Feb 18, 2018 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, 2018 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, 2018 at 16:51

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 21:01
  • $\begingroup$ I've edited my answer to reflect Will Sawin's observation. $\endgroup$
    – user103227
    Feb 20, 2018 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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