While reviewing old exercise sheets, I have found this question and am having difficulties understanding some of the logic:
Let $\mathbb{N}$(natural numbers) be a model for Peano Arithmetic, that means $\mathbb{N}$$\vDash$PA. Choose which of the following sentences are true in $\mathbb{N}$.
(a) $\lnot$$\exists$x((sx=0)$\to$(0=s0)) $\to$ (($\lnot$$\exists$x(sx=s0))$\to$(0=s0))
(b) (($\lnot$$\exists$x(sx=s0))$\to$(0=s0)) $\to$ $\lnot$$\exists$x((sx=s0)$\to$(0=s0))
(c) (($\exists$x(sx=0))$\to$(0=s0)) $\to$ $\exists$x((sx=s0)$\to$(0=s0))
For (a) I would say that it is true in $\mathbb{N}$, because if you set $\color{red}{x=0}$ then you get $\lnot$$\exists$x((s$\color{red}{0}$=0)$\to$(0=s0)) which is true. Then the second part of the implication I would also set x=0 again and in the end that part ends up also being true, so we have True implies True, hence (a) is true in $\mathbb{N}$.
For (b) I would start off by letting x=0 so then I would get (($\lnot$$\exists$x(s0=s0)) , which is false, and I can see that (0=s0) is also false, so False to False, hence first part of the implication is True.
Now this is is where i have run into some confusion. My professor had solved the second part of the implication by setting $\color{red}{x=s0}$,so we then have, $\lnot$$\exists$x((s$\color{red}{s0}$=s0)$\to$(0=s0)) , and this part would be false, so all together True to False, hence (b) is false in $\mathbb{N}$.
I can not understand the logic behind setting x=s0 in (b). Why is that allowed, when in (a) we didn't do that.
It would be greatly appreciated, if someone could please explain this and also provide some guidance for (c).
For (b) :
the "strategy" of you teacher is to prove it false showing that the antecedent is true and the consequent false.
But the RHS conditional is negated; thus we want that both the LHS : $¬∃x(sx=s0) → (0=s0)$ and the un-negated part of the RHS : $∃x((sx=s0)→(0=s0))$ are true.
i) Consider the LHS; it has $0=s0$ in the consequent, and this is always false (it means : $1=0$).
So, we have to find a value for $x$ such that the antecedent of the LHS conditional : $¬∃x(sx=s0)$ is false.
But $¬∃x(sx=s0)$ is false, because we can find some value for $x$ such that $sx=s0$ is true... it is enough to choose $0$ as value for $x$.
Thus, it is true that "there are values for $x$ such that $sx=s0$ holds", and so the negation of this sentence, i.e. $¬∃x(sx=s0)$ is false.
ii) Conider now the RHS; we want that the un-negated formula : $∃x((sx=s0)→(0=s0))$ is true.
So, the question is : can we find a value $n$ for $x$ such that : $(sn=s0)→(0=s0)$ is true ?
Again, we have the false consequent : $(0=s0)$; thus, in order to "verify" the conditional, we need a value $n$ for $x$ such that $(sn=s0)$ is false.
Now it is enough to choose $1$ (as our $n$) as value for $x$ and we have : $2 \ne 1$, i.e. :
this shows that "there are values for $x$ such that $sx=s0$ does not hold", i.e. $sx=s0$ is false for some value of $x$.
Summing up, we can find a value for $x$ such that $(sx=s0) \rightarrow (0=s0)$ is : $False \rightarrow TRUE$, i.e. $TRUE$, and so the sentence $∃x[(sx=s0) \rightarrow (0=s0)$ is true.
For (c), taking into account that in $\mathbb N$ $(0=s0)$ is false, we can rewrite it as :
Now, it is quite simple to find its truth value : $∃x(sx=0)$ is false in $\mathbb N$, because $0$ is not the successor of any number. Thus, we have :
Now, in order to have it true, we need a true consequent, and so we have to check if we can "verify" $∃x((sx=s0) → FALSE)$. Again, the only way to "verify" it is to find a value for $x$ such that $(sx=s0) → FALSE$ is true, i.e. we have to find a value for $x$ such that $(sx=s0)$ is false.
So, it is enough to choose $1$ and we have a value for $x$ such that $(sx=s0) → FALSE$ is true, i.e. $∃x((sx=s0) → FALSE)$ is true in $\mathbb N$, and also the complete formula is.