3

I'm preparing for an exam and encounter the following exercise in the notes I use.

In the next chapter we shall see that there are $\Sigma_1$-sentences which are false in $\mathcal{N}$ but consistent with PA. Use this to show that the following implication does not hold: for a $\Sigma_1$-formula $\phi(w)$ with only free variable $w$, if $\exists!w\phi(w)$ is true in $\mathcal{N}$, then $\mathrm{PA} \vdash \exists!w\phi(w)$.

So we want to find a $\Sigma_1$-formula $\phi(w)$ such that $\mathcal{N} \models \exists!w\phi(w)$, but $\mathrm{PA} \not\vdash \exists!w\phi(w)$.

We are given the fact that there exists a $\Sigma_1$-sentence $\psi$, such that $\mathcal{N} \not\models \psi$ and $\mathrm{PA} \not\vdash \psi \to \bot$. But then also $\mathcal{N} \models \psi \to \bot$, hence, the sentence $\psi \to \bot$ is already what we are looking for.

But this $\psi$ doesn't have a free variable. Now we could tack on a $\wedge w = 0$ or something like that, but I suspect I've made an error somewhere.

Garogolun
  • 212
  • I would use something like $ w = 0$,,, but I am not sure why you are looking at $\psi \to \bot$. What is your formula $\phi$, and why does $\mathbb{N}$ satisfy $(\exists ! w)\phi(w)$? – Carl Mummert May 20 '15 at 11:29
  • If I'm correct (not totally sure about this), then $\mathrm{PA} \not\vdash \psi \to \bot$ states that $\psi$ is consistent with PA. Choosing $\phi(w) = (\psi \to \bot) \wedge w = 0$ seems like a solution. But it doesn't seem correct since I didn't really use the free variable at all. – Garogolun May 20 '15 at 13:07
  • 1
    Your answer certainly meets all the requirements of the exercise. I guess it's just not a very "deep" exercise. – Rob Arthan May 20 '15 at 21:40
  • Thank you, I know then that I've probably understood it. :) – Garogolun May 21 '15 at 07:51

1 Answers1

1

The answer you give works, but I think here's what they're looking for: replace $\varphi(x)$ with $\varphi'(x)\equiv\varphi(x)\wedge\forall y(y<x\implies \neg\varphi(y)$). By induction, $\varphi$ has a solution iff $\varphi'$ has a unique solution. This is a trick which is frequently useful and nontrivial.

Noah Schweber
  • 245,398
  • Thank you for the trick. I've found out that my original solution is incorrect since it isn't a $\Sigma_1$-formula. However, I've trouble finding a $\Sigma_1$-formula with this trick. Suppose $\exists x \psi(x)$ is a $\Sigma_1$-formula false in $\mathcal{N}$, but consistent with PA. Then, $\phi(x) = \neg \psi(x) \wedge \forall y (y < x \to \psi(x))$ would do the trick, but is $\Pi_1$... – Garogolun May 26 '15 at 15:26