Need help understanding proof of theorem

Printable View

March 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$ ?
March 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$ .
March 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$ .