0
$\begingroup$

I have three questions (without any real background, this is just something I've been wondering about recently)

  1. Can PA prove that PA can't prove nor disprove, say, Goodstein theorem (or any natural independent statement)?
  2. Can PA prove that ZFC can't prove, say, CH nor it's negation?
  3. Can PA prove that ZFC can prove that ZFC can't prove, say, CH nor it's negation?

I highly suspect the first two questions to have a negative answer, because PA can't talk about any kind of models (there can be some work around though, e.g. some kind of approximating countable models with finite somethings), while I'm pretty sure that for the last one answer is affirmative, as ZFC can prove such statements in finite length which can be coded and proven to be right by PA.

As usual, let's work under assumption that PA and ZFC are consistent. (Edit: I actually want to add the axiom "ZFC is consistent" to PA, so that we can avoid problems as mentioned in the comments)

Thanks in advance

$\endgroup$
4
  • $\begingroup$ As for (1), it is a quick consequence of Lob's theorem that if $PA\vdash \lnot\square A$ for any sentence $A$, then $PA$ is inconsistent. $\endgroup$ Jun 4, 2015 at 17:40
  • 1
    $\begingroup$ The same goes for all three. For example, 3 would imply that PA proves that ZFC proves that ZFC is consistent, hence by Gödel’s theorem (formalized in PA), PA proves that ZFC is inconsistent, hence by the soundness of PA, ZFC is inconsistent. $\endgroup$ Jun 4, 2015 at 17:43
  • $\begingroup$ @EmilJeřábek How would things change if we actually added an axiom "ZFC is consistent" to PA? $\endgroup$
    – Wojowu
    Jun 4, 2015 at 17:45
  • $\begingroup$ That’s not going to help with 3. The answer to the questions you should have asked is that PA (or something much weaker, for that matter) proves that “if ZFC is consistent, then so are ZFC + CH and ZFC + ¬CH”, and “Goodstein’s theorem is equivalent to the $\Sigma_1$-soundness of PA”. Now figure out the correct questions. $\endgroup$ Jun 4, 2015 at 17:56

1 Answer 1

4
$\begingroup$

As observed in the comments, PA can't prove any unconditional statement of the form "PA does not prove X", because that would imply that PA proves its own consistency. The best you could hope for PA to prove is something like "If PA is consistent, then it proves neither X nor its negation". (By the deduction theorem, this should be equivalent to working in PA + "PA is consistent".)

A few years ago I played around with this sort of sentence, and came to the conclusion that there is some sentence $X$ such that PA proves "If PA is consistent, then it proves neither $X$ nor its negation", but I have no idea how to construct such a sentence -- in particular I have no idea whether this is true for any "natural" sentences. You can find what I wrote about it here, but I'll warn you that I wrote it as an undergrad and have made no attempt at publishing it -- it's had no peer review, errors may abound, and it may not be particularly well written. Caveat lector.

$\endgroup$
2
  • 9
    $\begingroup$ You can just take for X the Rosser sentence of PA. $\endgroup$ Jun 4, 2015 at 18:48
  • $\begingroup$ Thanks for pointing that out -- as much fun as I had fussing around with modal logic for the nonconstructive proof, it's certainly better to have an explicit example. (Is it obvious that this example works? It's been a while since I've thought about these things.) $\endgroup$ Jun 4, 2015 at 22:17

Your Answer

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

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