Explaining why proof by induction works

Question

I am learning math proofs for the first time. So I cannot discern the reason for all the details in a proof. Here's the statement of mathematical induction:

For every positive integer $n$, let $P(n)$ be a statement. If:

(1). $P(1)$ is true and

(2). If $P(k)$, then $P(k+1)$ is true for every positive integer $k$ then $P(n)$ is true for every positive integer $n$.

Here's the proof the author gave.

Assume that the theorem is false. Then conditions (1) and (2) are satisfied, but there exist some positive integers $n$ for which $P(n)$ is a false statement. Let $$S=\{n\in {\rm N}~{\rm :}P\left(n\right)~is~false\}$$Since $S$ is a non-empty subset of ${\rm N}$, it follows by the well-ordering principle that $S$ contains a least element $s$. Since $P(1)$ is true, $1\notin S$. Thus $s\ge 2$ and $s-1\in {\rm N}$. Therefore, $s-1\notin S$ and so $P(s-1)$ is a true statement. By condition (2), $P(s)$ is also true and so $s\notin S$. This however contradicts our assumption that $s\in S$.

My questions are:

1. Where did $s-1\in {\rm N}$ and $s-1\notin S$ pop from ?

2. Why is the well-ordering principle important for this proof ?

Answer 1

I assume you want the proof explained in a little more detail.

Here's what the proof says in English. Lets assume that conditions 1 and 2 hold. We use a proof by contradiction that it must be true for all n>=1.

As with all proofs by contradiction, we assume the statement is false and then show it leads to a contradiction. So we assume there is some s for which P(s) is false. Lets pick the smallest s where P(s) is false. (We know that there must be a smallest number s where it is false, because any non-empty set of natural numbers must contain a smallest value). But we know that P(s-1) is true (because s is the smallest value where P(s) is false, and s-1 is less than s). But if P(s-1) is true, then P(s-1+1) = P(s) is true, contradicting our assumption that P(s) is false. Therefore there cannot be any s where P(s) is false.

The s-1 finds the number immediately before the rule supposedly breaks down. But we know that if P(s-1) is true then P(s) must also be true, because of condition 2. This contradicts our assumption that the rule doesn't hold for P(s).

Well-ordering appears explicitly when we use the fact that any non-empty collection of natural numbers (in this case the collection of natural numbers x where P(x) is false) must have a lowest number.

More generally, the well-ordering principle states that if you consider 1,2,3 ... then this list will contain all natural numbers; there are no natural numbers that cannot be reached by starting at 1 and adding 1 repeatedly. If there were any missing numbers (ie if the set cannot be well ordered) then proof by induction would not work.

Answer 2

The well ordering principle in this case is just the assertion that if you have a collection of integers with a particular number represented at most once then one of them is the smallest. As for s - 1 $\in$ N, it must be, because he just established that s is at minimum 2 and 2 - 1 = 1, which is in N. However, s - 1 $\in$ N is a more general statement and since P(n) is true if n $\in$ N (according to (2)) then P(s - 1) is true. It follows that s - 1 $\notin$ S because if it were P(s - 1) would be false, by definition. But if s - 1 $\notin$ S then neither is s because s = s - 1 + 1 which generates a true statement as well by (2). So there is no s in S and S must contain an s to be non-empty, so S must be empty.