Why the priciple of strong induction stated in such way?

Question

In most books,the principle of strong induction is stated as follows:

Let $X$ be a well ordered set with an ordering relation $\leq$,and let $P(n)$ be a property pertaining to an element $n\in X$.Let $x_0$ be the smallest element in $X$.$p(x_0)$ is true,and

$$\forall m<n,P(m) \text{ is true}\Rightarrow P(n)\text{ is true}$$ Then we can say that $\forall x\in X$,$P(x)$ is true.

---

I wonder whether the principle of strong induction can be stated as such:

Let $X$ be a well ordered set with an ordering relation $\leq$,and let $P(n)$ be a property pertaining to an element $n\in X$.Let $x_0$ be the smallest element in $X$.$p(x_0)$ is true,and

$$P(y)\text{ is true} \Rightarrow P(\min (X\backslash\{x\in X:x\leq y \}))\text{ is true}$$Then we can say that $\forall x\in X$,$P(x)$ is true.

Answer 1

For general well-ordered sets your statement of well-ordered (strong) induction does not work for two reasons:

1. A well-ordered set can have elements without an immediate predecessor. An example of this is the ordinal $\omega + 1 = \{ 0 , 1, \ldots \} \cup \{ \omega \}$, ordered by extending the usual ordering on the natural numbers by declaring $x \leq \omega$ for all $x \in \omega+1$.

   Given such an element $z$ in a well-ordered set $X$ there would be no $y \in X$ such that $z = \min ( X \setminus \{ x \in X : x \leq y \} )$, and so the induction step would never concern itself with $z$. Or, to be a bit more precise, if this $z$ happened to be the least element of $X$ for which $P(x)$ fails, then you could not derive a contradiction by using your inductive implication to discover a yet smaller element for which $P(x)$ fails.

2. A well-ordered set can have maximum elements, for example $X = \{ 0 , 1 , 2 , \ldots , 424 \}$ has $424$ as its maximum. Note that if $y$ is the maximum element of $X$ then $$X \setminus \{ x \in X : x \leq y \} = X \setminus X = \emptyset$$ which has no elements, let alone a minimum element. Therefore the implication $$P(y) \rightarrow P (\min (X \setminus \{x\in X:x\leq y \}))$$ would either be meaningless or false.

Answer 2

For a well ordered set, your definition is the same as normal mathematical induction, because $$\min(X \setminus \{x \leq y \}) = \text{succ}(y)$$ where succ() is the successor operator induced by the well ordering (e.g. $\text{succ}(y) = y+1$ for the naturals). So your assumption then becomes $$P(y) \Rightarrow P(\text{succ}(y))$$ as in normal induction.

Note that strong induction is equivalent to mathematical induction in that both can prove the same things, so while it is technically valid to use your definition, it's not really the strong induction principle.

Answer 3

Your definition doesn't work at limit stages. As a basic example where it fails you could show that every element of $\omega + 1$ is also an element of $\omega$. There is an equivalent definition of induction where you assume the conditions that you stated and also that whenever $X' \subseteq X$ and $(\forall n \in X')P(n)$ then $P(\sup{X'})$, then $(\forall n)P(n)$.

By the way, in the first definition that you gave (the usual one) you don't need to prove $P(x_0)$; it follows from the other condition because $\{ x | x < x_0 \}$ is empty.

Answer 4

Your phrasing is incorrect; really, you have done nothing more than restate ordinary induction, since $\min (X\backslash\{x\in X:x\leq y \})$ is simply the successor of $y$.

Consider an inductive proof of the statement that every integer greater than 1 has a prime factorization, if we already know that every number has a prime factor:

Let $P(x)$ = "x has a prime factorization".

Now, suppose $P(x)$ is true for all $x < m$. Then to show $P(m)$ is true, we consider two cases:

• If $m$ is prime, then the prime factorization of $m$ is just $m$.
• Otherwise, $m$ has a prime factor $p$. $m/p < m$ and so by the inductive hypothesis $P(m/p)$ is true., Let $F$ be a prime factorization of $m/p$. Then $m$ has a prime factorization $p \cdot F$.

Note that the necessary implication here was $P(m/p) \implies P(m)$, where $m$ is very much not the smallest natural number that is not less than or equal to $m/p$.

In other examples of strong induction, not just a single prior statement is used. Sometimes to prove $P(m)$ the argument uses several statements $P(x)$ with $x < m$; occasionally, the argument even needs to invoke the truth of all $P(x)$ with $x < m$.