Question

Show that strong induction is a valid method of proof by showing that it follows from the well-ordering property.

Short answer

Strong induction follows from the well ordering property which is a valid method of proof.

Step-by-step solution

Significance of the strong induction

The strong induction is illustrated as a technique which is used for proving a particular theorem or statement. The importance of the strong induction is that it is beneficial for proving a particular theorem or statement in lesser time.

Proving the point that strong induction is a valid method

Assuming that the property holds which is well ordering. Taking an example that$P\left(1\right)$ holds true and the statement$\left[P\left(1{)}^{\wedge }P\right(2{)}^{\wedge }{\dots }^{\wedge }P\left(n\right)\right]\to P(n+1)$ also holds true for . Let the set of the positive integers which isn beS because of which$P\left(n\right)$ does not hold true. With the help of contradiction, it is needed to be proved thatS is an empty set.

Assuming thatS is not an empty set which implies$m\in S$ wherem is described as the least integer. But it has been identified that$m\ne 1$ with the assumption of$P\left(1\right)$ holds true. As$n=m$is described as the least possible integer in which$P\left(n\right)$ does not hold true but$P\left(1\right),P\left(2\right),...,P(m-1)$ mainly holds true. As$\left[P\left(1{)}^{\wedge }{\dots }^{\wedge }P\right(m-1)\right]\to P\left(m\right)$ holds true, then$P\left(m\right)$ holds true which certainly a contradiction. Hence, the setS is empty.

Thus, strong induction follows from the well ordering property which is a valid method of proof.