$PA \vdash \forall x(S(S(S...(S(x))...))) \neq \bar{0} $

75 Views Asked by At

I sign $\bar{k}$ the elements in $\mathbb{N}$ model for $PA$, and I use $\neq$ instead of $\neg(a=b)$ andd $S^n(x)$ as $S(S(...S(x))))$ just for convenience.

I was trying to show $PA\vdash \forall x(S^n(x)\neq \bar{0})$, using Peano's induction axiom, with $\varphi(x) = S^n (x) \neq \bar{0}$ and by trying to use a (regular) induction over $n$ , means start from $PA\vdash S(x)\neq \bar{0}$ (which as long as I know is an axiom) and then assume $S^k(x)\neq 0 $ for $k<n$

But I don't see how to proceed from this point, casue when trying to use the induction axiom, I couldn't find a way to apply the induction assumption.

$\forall x(\forall y(y<x)\rightarrow\ S(y)\neq \bar{0})\rightarrow S(x)\neq \bar{0})\rightarrow\forall x(S^n(x)\neq \bar{0})$

Sure that any other way to prove it will be appreciated.

1

There are 1 best solutions below

4
On BEST ANSWER

Let $M$ be a model of PA. Since PA proves $\forall x (S(x) \neq 0)$, then let $x$ be an arbitrary element of $M$ and let $a = S^{n-1}(x)$. So then $M \models S(a) \neq 0$. Since $x$ is arbitrary, this means $M \models \forall x (S^{n}(x) \neq 0)$. Since this statement is true for every model $M$, by the completeness theorem it is provable from PA.