10
$\begingroup$

The Goldbach Conjecture asserts:

It is possible to write every even number greater that 2 as the sum of two primes.

Assume I can prove that the Goldbach Conjecture is unprovable from the Peano arithmetic. That would mean I could not prove the conjecture, nor the negation.

But wouldn't that mean that I can not find a counter-example? Because that would be a finite proof to show that its negation is true. And if I can't find an counter example, doesn't that imply that the conjecture is true?

In other words, wouldn't it be a proof to the conjecture if I can show that it is unprovable?

$\endgroup$
11
  • 7
    $\begingroup$ Is true that if you cannot find a counter-example, then there is no counter example? $\endgroup$
    – Fimpellizzeri
    May 10, 2018 at 19:25
  • 1
    $\begingroup$ If the Goldbach conjecture is false, then you can verify this, since you can run a computer long enough to find you a counterexample $2n$. So if the Goldbach Conjecture is false, then it's provable. $\endgroup$
    – Alex R.
    May 10, 2018 at 19:35
  • 1
    $\begingroup$ Do you believe you can prove it is unprovable in Peano arithmetic? $\endgroup$
    – it's a hire car baby
    May 10, 2018 at 19:48
  • 1
    $\begingroup$ Take a different example such as Goodstein's theorem about certain fast-growing arithmetically defined sequences ending at $0$ - it cannot be proved in Peano arithmetic (that statement is the Kirby–Paris theorem) but it is true (and can be proved using techniques outside Peano arithmetic) so there are no counter-examples $\endgroup$
    – Henry
    May 10, 2018 at 22:29
  • 1
    $\begingroup$ @Fimpellizieri At least in the context of natural numbers, yes. Because not being able to find a counter example is equivalent to saying that a program that enumerates natural numbers and halts when it finds a counter example never terminates. $\endgroup$
    – DanielV
    May 10, 2018 at 22:30

1 Answer 1

Reset to default
16
$\begingroup$

Unprovable ≠ Undecidable. If PA can prove neither the conjecture nor its negation, it is undecidable in PA.

If you ever prove such a result, you certainly cannot be working within PA, because PA cannot prove that it cannot prove something, otherwise PA can prove that it cannot prove contradiction, which is impossible by Godel's second incompleteness theorem (assuming PA is consistent). Thus there is no paradox; your proof of unprovability over PA has to be a proof in some system other than PA.

So let's fix your foundational system MS as any reasonable formal system (at least proves existence of a model of PA), and let's reason within MS. If PA does not disprove Goldbach, then PA does not prove its negation, which is a $Σ_1$-sentence, and hence that negation cannot be true because PA is $Σ_1$-complete. So if PA does not disprove Goldbach, then Goldbach is actually true.

The caveat is that you are working within MS, so you should at least convince yourself that MS is consistent. Observe that if MS is inconsistent, you (working within MS) would be able to prove that PA does not prove Goldbach, but that would not mean anything.

Note that this argument does not necessarily apply to other open problems. For example the twin-prime conjecture can be written as a $Π_2$-sentence, and currently it is not known to be equivalent to a sentence of lower complexity, so the argument does not work, since PA is not $Σ_2$-complete.

$\endgroup$
3
  • $\begingroup$ For a brief overview on the sentence classification, see this Wikipedia article. $\endgroup$
    – user21820
    May 10, 2018 at 19:33
  • $\begingroup$ Thank you! What do you mean with MS? Couldn't find it in the related article. $\endgroup$
    – Adam
    May 11, 2018 at 8:29
  • 1
    $\begingroup$ @Adam: Sorry forgot to explain that acronym. I generally use "MS" to denote "meta-system", especially when I want to reason at 3 levels, NL (natural language) and MS (meta-system) and the formal system under study. =) $\endgroup$
    – user21820
    May 11, 2018 at 11:32

You must log in to answer this question.

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