Conjectures concerning natural numbers which could be settled by a counterexample can, as far as I understand, not be proved to be undecidable without being proved not having a counterexample at the same time. Or?

  • $\begingroup$ Not sure what answer can be given here except "yes, that's right". $\endgroup$ – Ben Millwood Dec 7 '14 at 7:29
  • 2
    $\begingroup$ It can be unprovable without it being provable that it's unprovable. $\endgroup$ – aes Dec 7 '14 at 7:54
  • 1
    $\begingroup$ If Goldbach's conjecture is proved to be undecidable in Peano arithmetic, there are models of arithmetic in which it is true, and models in which it is false. The existence of counterexamples is model-dependent, while provability of Goldbach's conjecture depends on the theory. But finding a counterexample in some model would prove that Goldbach's conjecture is either undecidable or false. $\endgroup$ – zarathustra Dec 7 '14 at 8:00
  • 3
    $\begingroup$ I just don't see how there could be a counterexample in one model, and not in another. Can there be a number that's prime in one model, but not in another? Can there be two primes that add up to different numbers in two different models? $\endgroup$ – Gerry Myerson Dec 7 '14 at 8:50
  • 1
    $\begingroup$ Since $\mathbb N$ is a minimal model a counterexample would be a counterexample in every model, but @aes is right of course, that a conjecture could be unprovable unprovable. $\endgroup$ – Lehs Dec 7 '14 at 10:54

If the Goldbach conjecture is undecidable (independent) of PA, then it is true for the standard model of arithmetic, i.e. the model $(\mathbb{N}, +, \times, 0, 1, <)$ with their normal interpretations.

Proof: Recall that $\mathbb{N}$ is the prime model of PA, (i.e. it embeds into every model $M$ such that $M\models$ PA). Further more, $\mathbb{N}$ is the initial segment of all models of PA. Assuming that $GC$ is independent of PA, we note that PA + $GC$ and PA + $\neg GC$ are consistent. Then, by Gödel's completeness theorem, there exists models $M_1$ and $M_2$ such that $M_1 \models$ PA + $GC$ and $M_2 \models$ PA + $\neg GC$. Suppose that $\mathbb{N} \models$ PA + $\neg GC$. Then, there exists some element $a \in \mathbb{N}$ such that $a$ cannot be written as the sum of two primes. Since $\mathbb{N}$ is the prime model of PA, we recall the fact that $\mathbb{N}$ embeds into all models of arithemtic. Therefore, if $\varphi(x)\equiv$ "$x$ cannot be written as the sum of two primes", and $\mathbb{N} \models \varphi(a)$.

By above, we showed there exist an $M_1$ such that $M_1 \models $ PA + $GC$. However, since $\mathbb{N}$ embeds into $M_1$, we note that $M_1 \models \varphi(\pi(a))$ (where $\pi$ is the embedding). However this implies that $M_1\models \neg GC$ which is a contradiction.

Thus, if $GC$ is independent of PA, then $\mathbb{N}\models GC$.

| cite | improve this answer | |
  • $\begingroup$ Are you sure the question isn't asking i Goldbach is independent of ℕ? Almost all references to PA are really to ℕ. $\endgroup$ – Joshua Dec 27 '14 at 19:59
  • 1
    $\begingroup$ @Joshua: I hope they are referencing PA (or some non-specified theory). When you talk about decidability, it should be in relation to a theory and not a model. $\endgroup$ – Kyle Gannon Dec 27 '14 at 20:04
  • 1
    $\begingroup$ @Joshua: Someone reference non-standard elements in the comments and so I think they are actually referring to a theory. $\endgroup$ – Kyle Gannon Dec 27 '14 at 20:05

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.