Why is well-ordering needed to define the statement "$\forall i, \, P(i) \implies P(i + 1)$"?

Question

I have learned a proof that the well ordering principle is equivalent to the inductive property for $\mathbb{N}$, and have understood it. However, I am confused as to the following statement my notes make:

Induction relies on the well-ordering principle: the statement "$\forall i, \, P(i) \implies P(i + 1)$" only makes sense if there is a well-defined order imposed on the natural numbers (i.e., that $3$ comes before $4$, and $4$ comes before $5$, etc. . . )

I am confused as to why the well-ordering principle is needed to justify the meaning of the statement "$\forall i,\, P(i) \implies P(i + 1)$", which is a different statement than the inductive property or the principle of mathematical induction. I have two questions about this:

1. It seems the only thing we need defined to interpret this statement is addition, propositions, implications, and $\forall$, none of which seem to require the well-ordering principle to define. Why do we need to define an order to the natural numbers in order to render the statement $\forall i P(i) \implies P(i + 1)$ meaningful?
2. Even if we wanted to define the natural numbers as being ordered before making this statement, why do we need the well ordering principle to do so? I understand that the well-ordering principle is sufficient to show an order, but it seems we could define an order just using addition and showing the natural numbers to be one apart each- although I am unsure of this because this itself may require induction, which is supposedly undefined at this point before we have shown an order to the naturals. Why is the well-ordering principle necessary to show $\mathbb{N}$ is ordered?

Answer 1

Let us first outline a proof that the mathematical (it might be more precise to call “arithmetic”) induction principle (MIP) and the well-ordering principle (WOP) are equivalent:

$$\mathrm{MIP}\iff\mathrm{WOP}$$

Recall that WOP states that every non-empty set of natural numbers contains a least element. In both directions, we shall employ reductio ad absurdum.

$\mathbf{MIP\implies WOP.}$ Suppose $U$ be a non-empty subset of natural numbers with no least element and $V$ is the complement of $U$.

$0\not\in U$, otherwise, it would be the least element. Therefore, $0\in V$.

Suppose every natural number $\leq n$ is in $V$. In case that $n+1\in U$, it would be the least element of $U$, since every natural number smaller is in the complement of $U$. But this is contradictory to that $U$ has no least element, therefore $n+1\in V$.

Carrying on in this fashion, every natural number is in $V$, by induction. Hence, $U=\emptyset$.​

$\mathbf{WOP\implies MIP.}$ Suppose $P$ is a property of a natural number such that $P(0)$ is true, and $P(n)$ being true implies that $P(n+1)$ is true. Let $U$ be a non-empty set of natural numbers $k$ such that $P(k)$ is false.

Let $l$ be the least element of $U$. Since $P(0)$ is true, $0\not\in U$, so $l\neq 0$ and $l−1$ is a natural number. Since $l$ is the least element, $l-1\not\in U$. So, $l$ falls in the set such that $P(l−1)$ is true. But then by the property of $P$, $P(l−1)$ being true implies that $P(l)$ is true. So $l\in U$, contradictory to our assumption.

Therefore, $U=\emptyset$ and $P(k)$ is true for all $k$.

Hence, from a general vantage point, MIP and WOP do not have a priority one over another.

Then, we shall turn to Peano Arithmetic (PA) for a more foundational level. The non-logical vocabulary of the language of (first-order) PA (the logical vocabulary as the standard first-order predicate logic is assumed) consists of the constant ‘$\mathbf{0}$’, the one-place successor function symbol ‘$\mathbf{S}$’, and the two-place function symbols ‘$\mathbf{+}$’, ‘$\mathbf{\cdot}$’. In model-theoretic signature form:

$$\langle\mathbb{N},\mathbf{S},\mathbf{+},\mathbf{\cdot},\mathbf{0}\rangle$$

with the ordinary intended interpretation. The axioms are the universal closures of the following statements (there are alternative axiomatisations; in fact, Giuseppe Peano's original formulation was different):

1. $\mathbf{0}\neq\mathbf{S}x$
2. $\mathbf{S}x =\mathbf{S}y\rightarrow x = y$
3. $x+\mathbf{0}=x$
4. $x+\mathbf{S}y=\mathbf{S}(x + y)$
5. $x\mathbf{\cdot}0=0$
6. $x\mathbf{\cdot}y=(x\mathbf{\cdot}y)+x$

and the Induction Schema for any property $\mathbf{P}$

$$((\mathbf{P}(0)\wedge\forall x(\mathbf{P}(x)\rightarrow\mathbf{P}(Sx))\rightarrow\forall(x)\mathbf{P}(x)$$

We have seen that addition is defined by the primitive terms $\mathbf{0}$ and $\mathbf{S}$. It may be helpful to cite Bertrand Russell at this point (Introduction to Mathematical Philosophy, 2nd edition, pp.5-6):

The three primitive ideas in Peano’s arithmetic are:

                       0, number, successor.

By “successor” he means the next number in the natural order. That is to say, the successor of 0 is 1, the successor of 1 is 2, and so on. By “number” he means, in this connection, the class of the natural numbers.2 He is not assuming that we know all the members of this class, but only that we know what we mean when we say that this or that is a number, just as we know what we mean when we say “Jones is a man,” though we do not know all men individually.

The five primitive propositions [beware: not the axioms -T.B.] which Peano assumes are:

(1) 0 is a number.

(2) The successor of any number is a number.

(3) No two numbers have the same successor.

(4) 0 is not the successor of any number.

(5) Any property which belongs to 0, and also to the successor of every number which has the property, belongs to all numbers.

As the upshot of the foregoing discussion, we can say that

• Addition is not the most basic operation in respect of the current foundational theory.

• It is a matter of choice to start with MIP or WOP. But, with the primitive notions of number and one number succeeding the other, we have to admit that the notion of ordering is built-in. Indeed, the Induction Schema can be replaced with:

• $\forall x(\mathbf{SS\ldots S}x\neq x)$

• $\forall x(x\neq 0\rightarrow\exists y(\mathbf{S}y = x))$