# Need help understanding proof of theorem

• Mar 8th 2010, 07:14 AM
novice
Need help understanding proof of theorem
(The Principle of Mathematical Induction) For each positive integer $n$, let $P(n)$ be a statement. If

(1) $P(1)$ is true and
(2) the implication

If $P(k)$, then $P(k+1)$

is true for ever positive integer $k$, then $P(n)$ is true for every positive integer $n$.

Proof:

Assume, to the contrary, 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 \mathbb{N}: P(n)$ is false $\}$

Since $S$ is a nonempty subset of $\mathbb{N}$ , it follows by the Well-Ordering Principle that $S$ contains $s$. Since $P(1)$ is true, $1 \in S$.
Here I am lost:
Thus $s \geq 2$ and $s-1 \in \mathbb{N}$. Therefore, $s-1 \in S$ and so $P(s-1)$ is a true statement. By condition (2), $P(s)$ is also true
and so $s \not \in S$. This however, contradicts our assumption that $s \in S$.

Question: What is $s-1$?
• Mar 8th 2010, 08:00 AM
Plato
Quote:

Originally Posted by novice
(The Principle of Mathematical Induction) For each positive integer $n$, let $P(n)$ be a statement. If
(1) $P(1)$ is true and
(2) the implication If $P(k)$, then $P(k+1)$
is true for ever positive integer $k$, then $P(n)$ is true for every positive integer $n$.

Proof:Assume, to the contrary, 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 \mathbb{N}: P(n)$ is false $\}$
Since $S$ is a nonempty subset of $\mathbb{N}$ , it follows by the Well-Ordering Principle that $S$ contains $s$. Since $P(1)$ is true, $1 \in S$.
Here I am lost:
Thus $s \geq 2$ and $s-1 \in \mathbb{N}$. Therefore, $s-1 \in S$ and so $P(s-1)$ is a true statement. By condition (2), $P(s)$ is also true
and so $s \not \in S$. This however, contradicts our assumption that $s \in S$.
Question: What is $s-1$?

Above you must mean $1 {\color{blue}\notin} S$

And $s-1$ is the first integer less than $s$.
• Mar 8th 2010, 08:41 AM
novice
Quote:

Originally Posted by Plato
[/b]
Above you must mean $1 {\color{blue}\notin} S$

And $s-1$ is the first integer less than $s$.

Thank you for the explanation. Now I understand.

Yes, it's supposed to be $1\not \in S$.