# Explaining why proof by induction works [duplicate]

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 ?

## marked as duplicate by Daniel W. Farlow, Aaron Maroja, user26857, egreg, Zev ChonolesApr 20 '15 at 0:20

• The Well-Ordering Principle guarantees that the proof by contradiction works by exhibiting a least element of $S$. If some $n \in \mathbb{N}$ makes the predicate $P$ false, then there is a least such $n$. As $s \geq 2$, the natural number before $s$, namely $s - 1$, must make $P$ true. – Berrick Caleb Fillmore Apr 19 '15 at 7:10
• But why is $s-1\notin S$ true ? – John Apr 19 '15 at 7:14
• As $s$ is the smallest natural number making $P$ false, any natural number before $s$ makes $P$ true. Otherwise, $s$ cannot claim to be the smallest natural number making $P$ false. – Berrick Caleb Fillmore Apr 19 '15 at 7:16
• Imagine belonging to a class of 30 students, where each student is assigned a unique number from 1 to 30. Let $s$ be the smallest of all numbers $n$ with the property that $n$ corresponds to a girl. Then any number smaller than $s$ must correspond to a boy. – Berrick Caleb Fillmore Apr 19 '15 at 7:25

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.

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.