# Proving that for $x \neq 0$ there exists a $y$ such that $S(y) = x$.

In another proof of mine I had written:

Since $d \neq 0$ we can write $S(k) = d$ for some $k$ without violating Peano's 3rd axiom.

Apparently this isn't a valid step in a proof so I want to more explicitly prove that

$\forall x (x \not = 0 \rightarrow \exists y : S(y) = x)$

where $S$ is the successor function.

I wish to prove this via induction.

Now I don't know technically what kind of induction I am allowed to use, since Peano's 5th axiom is more like "For any property $P$ of a natural number, if $P(0)$ holds and $P(k)$ implies $P(k+1)$ then $P(n)$ is true for every natural number $n$."

So I need my base case to be a $k=0$ case, but since $x \neq 0$ I don't know if I am allowed to induct on $x$ starting at $1$. But even if I am I am not sure how to prove it correctly since it's a very different type of proof than what I am used to.

Base Case: Let $x=1$. Then $y=0$ satisfies $S(y) = S(0) = 1$.

Inductive Step: Suppose there exists a $z$ such that $S(z) = x$. We must show that there exists a $y$ such that $S(y) = S(x)$. By Peano's 4th axiom (which states that if $m=n$ then $S(m)=S(n)$), we have $S(S(z)) = S(x)$. If we let $y=S(S(z))=x$, we are done.

Is this correct? Am I even allowed to do this? Does this even prove what I want to prove?

## 1 Answer

You can (and must) start with the base case of $0$.

That means you have to prove $0 \not =0 \rightarrow \exists y \ 0 =S(y)$

But this is trivially true, exactly because $0 \not =0$ is false. That is: if you assume $0 \not = 0$ you have an immediate contradiction, from which you can infer anything you want ... which is of course that $\exists y \ 0 =S(y)$, and that proves the conditional, i.e. $P(0)$

Also, the step can be done a little simpler: you need to show that $P(S(k))$, which is that $S(k) \not = 0 \rightarrow \exists y \ S( k ) = S(y)$. But of course the consequent is trivially true, since you can just take $y=k$. So, you don't even need to use the inductive hypothesis!

• *vacuously true as well since F->T and F->F are with true, correct? But then are we allowed to "start" from 1 as the base case after proving the 0 case? Commented Mar 31, 2018 at 17:23
• @user525966 yes, exactly. And yes, you can start with $1$ after doing the $0$ case, but that won't be necessary, since the step includes $P(0) \rightarrow P(1)$ . Commented Mar 31, 2018 at 18:08
• Whoa, so we can use vacuously true base cases? What if it's undefined for 0 but true for eeverything else? I'm trying to envision a case where you have to start the base case higher but it happens to be true along with all k and k+1 after that Commented Mar 31, 2018 at 18:33
• @user525966 If you want to show something is true for all natural numbers, you have to start at $0$ ... if a case is vacuously true, hey great! Easy! If you ever want to prove something is true for all natural numbers greater or equal than $k$, then of course make $k$ your base case. Commented Mar 31, 2018 at 19:24