8
$\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$
5
  • 9
    $\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
    Commented Feb 18, 2018 at 1:28
  • 3
    $\begingroup$ Do you have a reference for Goodstein being equivalent to Con(PA)? $\endgroup$
    – Wojowu
    Commented 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
    Commented 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
    Commented Feb 20, 2018 at 16:51
  • 1
    $\begingroup$ @Wojowu It indeed isn't correct, as per this question: math.stackexchange.com/questions/5003237/… $\endgroup$
    – Kotlopou
    Commented Nov 30 at 9:38

2 Answers 2

Reset to default
10
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 18, 2018 at 21:01
  • $\begingroup$ I've edited my answer to reflect Will Sawin's observation. $\endgroup$
    – user103227
    Commented Feb 20, 2018 at 8:57
8
$\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$
1
  • $\begingroup$ Does this mean something fundamental, though, or is it just an artifact of the consistency statements considered in the question being all $\Pi_1$? After all, your example looks suspiciously like a consistency statement, too, just a level above. $\endgroup$
    – Kotlopou
    Commented Aug 29 at 23:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .