Does mathematical induction assume that non-negative integers are infinite?

Question

Does mathematical induction assume that the non-negative integers continue indefinitely? A friend of mine was attempting to show me that there are an infinite number of non-negative integers using mathematical induction but I always thought that, since one of the two main parts of mathematical induction relies on showing that what holds for $n$ must also hold for $n+1$, it already assumes that non-negative integers are infinite in number, for it assumes that there will always be a $n+1$ (that is, there will always be a successor). However, after seeing a formulation of the counting numbers using nested sets and mathematical induction then used to show that these constructions must be indefinite in number, I am not sure what to believe (I didn't understand the proof very well). Life doesn't make sense anymore. Please help me.

Answer 1

No, mathematical induction does not assume that the class of natural numbers is infinite. One can use the axiom saying that every natural number has a successor together with the axioms saying

• zero is not the successor of any natural number,

• different natural numbers have different successors,

and an axiom from the induction schema, to prove that the class of natural numbers is infinite. No one of these axioms is enough on its own to establish this.

One can have other structures, such as $\mathbb{Z}/5\mathbb{Z}$, that are finite but nevertheless have an $n+1$ for every $n$. Here the relevant difference from $\mathbb{N}$ is that zero does have the form $n+1$ for some $n$. This example shows that it is possible to have a structure with a total operation—which can therefore be iterated indefinitely—but such that this iteration does not produce an unlimited number of distinct elements. Just as for $\mathbb{N}$, the induction schema is valid for $\mathbb{Z}/5\mathbb{Z}$. However, such abstract considerations are unnecessary here because the structure is finite and one can simply write down the whole structure.

The point of the induction schema for $\mathbb{N}$ is that it allows us to get a handle on the structure even though we cannot simply write down the whole thing. In particular, it means that $\mathbb{N}$ is not "too large" and that no natural number itself is infinite. It is mainly the role of the other axioms to prove that $\mathbb{N}$ is not "too small". For example, without using induction one could prove that $\mathbb{N}$ has more than 5 elements, or more than 5,000,000 elements. (Although it is true that induction is required for a formal proof that $\mathbb{N}$ is infinite, because we have to prove that for all $n \in \mathbb{N}$ the structure $\mathbb{N}$ does not have size $n$, not just for $n=5$ or $n = \text{5,000,000}$, and induction is generally required to prove such universal statements.)