Peano Arithmetic - Decidability

227 Views Asked by At

I need to show that if Peano Arithmetic does not decide a sentence $\varphi$ then the standard model of Peano Arithmetic satisfies the negation of $\varphi$. I know this partly has to do with Godel's Incompleteness Theorem, but I'm really lost on where to start. Any help would be greatly appreciated.

EDIT TO ADD: "Let $\varphi$ be a $\Sigma_1$ sentence in the language of Peano Arithmetic" should be the first part of the problem, I left it out accidentally ^

1

There are 1 best solutions below

4
On

The only fact you need is that PA proves every true (i.e. true in the standard model) $\Sigma_1$ sentence. So if a $\Sigma_1$ sentence is undecidable in PA, it must be false.

This fact is somewhat tedious to prove, but I'm sure you have been given the hard part in some form. For instance, perhaps you've been given the fact that PA (or even the weak subtheory Robinson arithmetic) can correctly decide any instance of a computable relation. Then from there, you can use the fact that by definition, a $\Sigma_1$ sentence can be written $\exists x \varphi(x)$ for some $\varphi$ that is $\Delta_0$, hence computable. So if that's true, $\varphi(\mathbf n)$ is true for some $n,$ and since that's a $\Delta_0$ sentence, it can be proven in PA, and then PA can use existential instantiation to prove $\exists x\varphi(x)$ from there.