Why does the well ordering principle imply induction.

Question

The proof tends to run something like so:

Let

$$\mathbb{S} \subset \mathbb{Z}^+ \mid 1 \in \mathbb{S}\ and\ k \in \mathbb{S} \implies (k+1) \in \mathbb{S}$$

The well ordering principle is then applied to state that there is a minimum member $$m \in \mathbb{{Z}^+\setminus{S}}$$ which by definition can not be 1. It then follows that $$ (m-1) \in \mathbb{S}$$ and since $$ k \in \mathbb{S} \implies (k+1) \in \mathbb{S}$$ it also follows that $$m \in \mathbb{S}$$ which is a contradiction.

All of the logical steps make total sense. What I don't understand is why we can assume that a set fulfilling the requirements of $$\mathbb{S}$$ necessarily exists.

This seems like a very artificial construct which mirrors the definition of the positive integers? And at no point do we prove that such a set, irrespectively of whether or not the set difference is empty, even exists?

Answer 1

You are right in one sense. The argument doesn't say that such a set exists. It says that if a set $\mathbb{S}$ has that property then its complement must be empty, so it's all of $\mathbb{Z}^+$.

The argument does mirror the definition of the positive integers in some versions of the foundations of arithmetic. In elementary number theory it's customary to take the integers as given and induction (in one or the other form) as an axiom.

Answer 2

You prove that such a set exists every time you carry out a proof by induction in the usual fashion. If, for instance, you use induction to prove that $$\sum_{k=1}^nk=\frac12n(n+1)\tag{1}$$ for each $n\in\Bbb Z^+$, you let $\Bbb S$ be the set of positive integers $n$ such that $(1)$ is true. You then show that $1\in\Bbb S$ and that $k+1\in\Bbb S$ whenever $k\in\Bbb S$. The argument given in your question then shows that $\Bbb S=\Bbb Z^+$.

That argument itself doesn’t actually depend on the existence of $\Bbb S$: it shows that if such an $\Bbb S$ exists, it must be $\Bbb Z^+$.