Strong Induction proofs done with Weak Induction

Solution 1:

The idea is that if something is proved with "strong" induction, i.e. by assuming all preceding cases, then you can use "weak" induction on the hypothesis "all preceding cases hold". Let me explain with mathematical notation, perhaps it'll be a little clearer.

Suppose you want to prove a proposition for all $n \ge 1$, i.e you want to show that for all $n \ge 1$, $P(n)$ is true, where $P(n)$ is some proposition. Define the proposition $Q(n)$ by "$P(k)$ is true for all $k$ with $1 \le k \le n$". Then showing that $P(n)$ is true using "strong" induction is equivalent to showing that $Q(n)$ is true using "weak" induction. But $P(n)$ is true for all $n$ if and only if $Q(n)$ is true for all $n$, hence the proof techniques are completely equivalent (in the sense that using one technique or the other has the same veracity ; it doesn't mean that one is more or less complicated to use than the other).

At some point in the study of mathematics you stop making the distinction between "strong" and "weak". You just say that you're using "induction". I wouldn't be sure that you stop distinguishing this if you study logic though, but let's just leave those kind of problems to logicians, shall we.

Hope that helps,

Solution 2:

Statements that say that two propositions are equivalent have to be done carefully, because the background theory is important.

Specifically, you are talking about two statements about the natural numbers:

1. Induction (or "weak" induction): Let $S\subseteq \mathbb{N}$ be such that:

   • $0\in S$; and
   • For all $n\in\mathbb{N}$, if $n\in S$ then $s(n)\in S$.

   Then $S=\mathbb{N}$.

2. Strong induction: Let $S\subseteq \mathbb{N}$ be such that:

   • For all $n\in\mathbb{N}$, if $\{k\in\mathbb{N}\mid k\lt n\}\subseteq S$ then $n\in S$.

   Then $S=\mathbb{N}$.

Above, $s(n)$ is the successor function.

The main difficulty is to establish exactly what our "background" is. The induction Schema makes sense in the context of Peano's postulates; Strong induction requires a defined property of $\lt$.

Moreover, it is not the case that induction and strong induction are equivalent axioms! That is, if we take the other four Peano axioms,

1. $0\in\mathbb{N}$.
2. If $n\in\mathbb{N}$, then $s(n)\in\mathbb{N}$.
3. For all $n\in\mathbb{N}$, $0\neq s(n)$.
4. If $s(n)=s(m)$ then $n=m$.

then it is not true that Axioms 1-4 + Induction yields a theory equivalent to Axioms 1-4 + Strong induction, even if you throw in an order so that you can state Strong induction!

To see this, consider a disjoint union of two copies of the natural numbers; let's call one copy the "green" natural numbers, and the other copy the "purple" natural numbers (I usually use blue and red, but let's avoid politics this year...). We interpret the primitives as follows: $\mathbb{N}$ is the set that contains all green and all purple natural numbers. $0$ corresponds to the green $0$. If $n$ is green, then $s(n)$ is the green $n+1$; if $n$ is purple, then $s(n)$ is the purple $n+1$. The order is defined as follows: if $n$ is green and $m$ is purple, then $n\lt m$. If both $n$ and $m$ are of the same color, then $n\lt m$ if and only if $n$ is smaller than $m$ in the usual order.

This model satisfies Peano's axioms 1 through 4; it also satisifies the strong induction postulate.

However, in this model, the set $S$ of all green natural numbers satisfies the hypothesis of "Induction" but is not all of $\mathbb{N}$: green $0$ is in $S$, and if $n$ is a green natural number, then so is $s(n)$. This means that this set is not a model for Peano arithmetic. So it is false that weak and strong induction can be swapped with one another and yield equivalent theories with the other four Peano postulates.

However, if we add a further property, namely

For every $n\in\mathbb{N}$, either $n=0$ or else there exists $m\in\mathbb{N}$ such that $n=s(m)$;

then the first four axioms, plus this property, plus strong induction does imply weak induction.

I guess the moral is that the statement "weak induction is equivalent to strong induction" has to be made precise before it is true; one has to specify a "background theory" or a set of "background properties" which we may take for granted before the equivalence is established. But in the presence of those "background properties", then Patrick Da Silva's argument is the standard one: any proof (over a suitable theory for $\mathbb{N}$) that uses induction can be reshaped (in a straightforward way) to become a proof that uses strong induction instead; and any proof that uses strong induction can be reshaped (in a more-or-less algorithmic manner) into a proof that uses weak induction.