Induction AND well-ordering property imply strong induction

Question

My question is about exercise 1.6 in "Propositional and Predicate Calculus" by D. Goldrei: "Explain how the above variant of the method of proof by mathematical induction follows from the principle of mathematical induction. [Hint: You might wish to exploit the well-order property of $\Bbb N$.]" The "above variant" refers to strong induction, the "principle of mathematical induction" to weak induction.

Assuming my proof is correct, it only needs the well-order property to show the validity of strong induction:

Let $P$ be a subset of $\Bbb N$ with $0 \in P$ and the property that for all $n \in \Bbb N$, if $k \in P$ for all $k \leq n$, then $k \in P$ for all $k \leq n+1$. Assume there exists a non-empty set $S$ containing the natural numbers not in $P$. By the well-order property, $S$ has a least natural number $s_0$. Since $0 \in P$, $s_0 \neq 0$. Thus, there is a $t \in \Bbb N$ such that $t+1=s_0$. Notice $t \notin S$ because $t<s_0$, meaning $t \in P$. More specifically, $k \in P$ for all $k \leq t$. According to the assumption about $P$, this implies $t+1=s_0 \in P$ and, thus, $S=\emptyset$ and $P=\Bbb N$.

How would I incorporate both the weak induction and the well-order property, as hinted in the exercise, when proving strong induction?

Answer 1

Well ordering is equivalent to induction. And the principle of induction is equivalent to strong induction.
So you don't need both to prove strong induction.

Answer 2

The strong principle of induction is a modification of the weak principle of induction, which states that if a property holds for the base case (usually 0 or 1), and if the property holding for a number k implies it also holds for k+1, then the property holds for all natural numbers.

The strong principle of induction, on the other hand, asserts that if a property holds for the base case, and if the property holding for all numbers up to and including a number k implies it also holds for k+1, then the property holds for all natural numbers.

In the proof you've written, you've essentially used the strong principle of induction to prove itself, assuming the property it describes to show that it must hold for all natural numbers.

To incorporate both the weak induction and the well-ordering property, we can proceed as follows:

Let's assume we have a property P(n) such that:

1. P(0) is true. (Base case)
2. If P(i) is true for all i in {0, 1, ..., k}, then P(k+1) is true. (Inductive step)

Now, suppose there exists a set S of natural numbers for which P(n) is not true. By the well-ordering principle, S has a least element, say s. Since P(0) is true, s cannot be 0. So, s = k+1 for some k >= 0.

By our inductive step assumption, if P(i) is true for all i in {0, 1, ..., k}, then P(k+1) is true. But, since s is the least element in S for which P is not true, P(i) must be true for all i in {0, 1, ..., k}. Therefore, P(k+1) = P(s) should be true, which contradicts the assumption that s is in S.

Thus, our assumption that there exists a set S of natural numbers for which P(n) is not true must be incorrect, and P(n) is true for all natural numbers. This is the principle of strong induction.

This proof utilizes the weak principle of induction (which asserts that if P(0) is true and P(k) implies P(k+1), then P(n) is true for all n), and the well-ordering principle (which asserts that every non-empty set of natural numbers has a least element).