Is induction defined on natural numbers?

185 Views Asked by At

Whenever I use the inductive method to prove some questions, I usually start from the $n=1$ case and assume it holds for all $n$.

However, is the reason why we do not consider the $n=0$ case because induction is defined on natural numbers, or is it too trivial that we do not check this case?

2

There are 2 best solutions below

0
On

(for the purpose of this answer I assume $0\in\Bbb N$)

This really depends on what exactly you are trying to prove. If you want that property $P$ holds for all $n\in\Bbb N$, then it is necessary to either start the induction with base case $n=0$, or to start it with base case $n=1$ and then verify $P$ for $0$ separately (which might not be at all trivial!).

If you want to prove it only for positive $n\in\Bbb N$, then using base case $n=1$ is perfectly fine.

In greater generality, the following principle is valid (which coffeemath mentions in their comment): If $a$ is any integer (possibly negative!) and you want to prove $P$ holds for all integers $n\geq a$, then it's enough to prove that $P(a)$ holds (base case), and that $P(n)\Rightarrow P(n+1)$ (inductive step), when $P(x)$ is shorthand for "$P$ holds for $x$".

3
On

Mathematical Induction is true for every well ordered set. $\mathbb{N}$ is a natural example of well ordered set, but we have induction in other sets like: $$W=\left \{ \alpha |\alpha <\epsilon_0 \right \}$$ and $\epsilon_0=\sup{\left \{\omega,\omega^{\omega},\omega^{\omega^{\omega},...} \right \}}$ is an ordinal number. See Transfinite induction for more details.