Demonstration by induction without using the induction hypothesis

Question

my definition of sum:

$\sigma_n(0)=n$

$ \sigma_n(s(m)) = s(\sigma_n(m))$

in which $\sigma_n$ is obtained from the recursion theorem.

I want to show directly from the axioms of peano that if $n,m \in \mathbb{N} $ then $n+m=0 \Leftrightarrow n=m=0$. (can use that sum is commutative)

To prove this consider $m \neq 0$ and $S=\{ n \in \mathbb{N}: n+m \neq 0\}$.

• $0 \in S:$ Trivial ($m \neq 0$)
• $i \in S \Rightarrow s(i) \in S$: $m+s(i)=s(m+i) \neq 0$

then $S= \mathbb{N}$. We conclude $n+m=0 \Rightarrow n=m=0$

I have not used the induction hypothesis, is this a problem?

Answer 1

In the induction step, the induction hypothesis is available for you to use. But there's no requirement that you use it, if you can reach the desired conclusion without it.

It is only rarely possible to reach that goal without appealing to the induction hypothesis, so when you find yourself having done so, it is indeed a good habit to stop and check what is going on. It may be that either you have made a mistake along the way, or that you actually don't need induction at all -- that is, what you thought was an induction step would work as a free-standing proof of your final conclusion.

In this particular case, it looks like you've hit on one of the rare cases where it is meaningful to do an induction proof without using the induction hypothesis. What's going on here is that you have two things you're allowed to use in the induction step:

1. The number you're looking at is one plus something.

2. The induction hypothesis holds for that "something".

In your proof it turns out that part (1) is enough for you and you don't need to use part (2). That's completely fine. It is not one of the cases where the induction could have been omitted, because without the induction you wouldn't have (1).

(The only other case of this happening I can recall offhand is proving "every natural number is either 0 or a successor" by induction. You could instead have used that fact as a lemma and then instead of the induction just do a case analysis on whether $n$ is $0$ or a successor. But doing it the way you do is valid too).