1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ *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? $\endgroup$ – user525966 Mar 31 '18 at 17:23
  • $\begingroup$ @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)$ . $\endgroup$ – Bram28 Mar 31 '18 at 18:08
  • $\begingroup$ 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 $\endgroup$ – user525966 Mar 31 '18 at 18:33
  • $\begingroup$ @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. $\endgroup$ – Bram28 Mar 31 '18 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.