Questions about the Strong Induction Principle and the Well Ordering Principle

Question

The Strong Induction Principle (SIP) is presented in Hrbacek and Jech's Introduction to Set Theory (3 Ed) as follows:

Let $P(x)$ be a property. Assume that, for all $n \in \mathbb{N}$,

• (*) if $P(k)$ holds for all $k < n$, then $P(n)$.

Then $P(n)$ holds for every $n \in \mathbb{N}$.

My first question is about the proof of the SIP, which I replicate below (the only results we are allowed to use are: (1) the standard induction principle, and (2) for all $k, n \in \mathbb{N}$, $k < n+1$ if and only if $k \leq n$ ):

Proof:

Let $Q(n)$ be the property 'for all $m \in \mathbb{N}$, if $m < n$, then $P(m)$'. We use standard induction to prove it holds for all $n \in \mathbb{N}$.

• For $n = 0$, the statement 'for all $m \in \mathbb{N}$, if $m < 0$, then $P(m)$' is true, since '$m < 0$' is false for natural $m$.
• Assume 'for all $m \in \mathbb{N}$, if $m < n$, then $P(m)$' for $n \in \mathbb{N}$ (we want 'for all $m \in \mathbb{N}$, if $m < n+1$, then $P(m)$'). So take $m < n+1$, which is equivalent to $m \leq n$. For $m=n$ we combine the induction hypothesis with (*) to get that $P(n) = P(m)$ is true. If $m < n$, then $P(m)$ is true by the induction hypothesis.
• By the induction principle we have proven that for all $n, m \in \mathbb{N}$, if $m<n$ then $P(m)$ is true.
• Finally, to prove $P(n)$ holds for all $n \in \mathbb{N}$, notice that $n < n+1$, for any natural $n$, and by the result we just proved $P(n)$ is thus true. $\blacksquare$

I want to know why is the last step (bullet) necessary. For me the result in the third bullet combined with (*) would imply $P(n)$ is true for all $n$.

---

My second question concerns the proof that the naturals are well ordered (i.e. every non empty subset of $\mathbb{N}$ has a least element). I will write the proof with my own words, but the argument is that of the book.

2. The set $(\mathbb{N}, <)$ is well ordered.

Proof:

Let $X$ be a non empty subset of $\mathbb{N}$ and assume, looking for a contradiction, that $X$ does not have a least element. Consider the set $\mathbb{N} - X$; we show that $\mathbb{N} - X = \mathbb{N}$. So assume, for $n \in \mathbb{N}$, that $k \in \mathbb{N} - X$ for every $k < n$ (we will use the SIP where $P(m)$ is the property '$m \in \mathbb{N} - X$'). Notice that if $n \in X$, then $n \leq x$, for all $x \in X$, making $n$ the least element of $X$. Thus $n \in \mathbb{N} - X$ and, by the SIP, we conclude that $n \in \mathbb{N} -X$ for all $n \in \mathbb{N}$, making $X = \emptyset$, a contradiction. $\blacksquare$

The thing that puzzles me is that there is no checking of a base case, and it is not intuitively clear to me that if you pick a random non empty subset of $\mathbb{N}$ you can assume '$k \in \mathbb{N} - X$ for every $k < n$'.

Answer 1

The third bullet point says that if $m$ is a natural number that is less than some natural number, then $P(m)$ is true. In order to use this to show that $P(n)$ is true for every $n\in\Bbb N$, we have to show that every $n\in\Bbb N$ is less than some natural number, and that’s exactly what is done in the fourth bullet point. There is nothing in the statement at the third bullet point that lets you apply (*): you have no $n$ such that $P(k)$ is known to hold for all $k<n$.

In the proof that $<$ well-orders $\Bbb N$ there is no need for a base case, because we’re using the SIP, which does not require one. We let $P(m)$ be the property $m\in\Bbb N\setminus X$. The SIP then says if

$$P(k)\text{ holds for all }k<n\implies P(n)\text{ holds}\;,\tag{1}$$

then $P(n)$ holds for every $n\in\Bbb N$. In order to apply it, we must check that $(1)$ is actually true for this property $P$. To show that it’s true, we must show that if $P(k)$ holds for all $k<n$, then $P(n)$ holds. We’re not actually assuming at this point that $P(k)$ really does hold for all $k<n$; we’re just asking whether this would, if true, imply that $P(n)$ holds. So we assume it for the sake of argument, to see whether $P(n)$ would necessarily follow, and we find that it would. The SIP now lets us conclude that $n\in\Bbb N\setminus X$ for all $n\in\Bbb N$, which is impossible, since we started with a non-empty $X$.