Need help understanding proof of theorem

**novice** · March 8th 2010, 07:14 AM

(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$ ?

**Plato** · March 8th 2010, 08:00 AM

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

**novice** · March 8th 2010, 08:41 AM

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

Thread: Need help understanding proof of theorem

LinkBack

Thread Tools

Display

Need help understanding proof of theorem

Similar Math Help Forum Discussions

Help understanding what this theorem means

Problem understanding the theorem

Help understanding this theorem/proof

Need help understanding the Chinese Remainder Theorem

Need help understanding the Chinese Remainder Theorem

Search Tags