# Thread: Need help understanding proof of theorem

1. ## Need help understanding proof of theorem

(The Principle of Mathematical Induction) For each positive integer $\displaystyle n$, let $\displaystyle P(n)$ be a statement. If

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

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

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

Proof:

Assume, to the contrary, that the theorem is false. Then conditions (1) and (2) are satisfied but there exist some positive integers $\displaystyle n$ for which $\displaystyle P(n)$ is a false statement. Let

$\displaystyle S = \{n \in \mathbb{N}: P(n)$ is false $\displaystyle \}$

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

Question: What is $\displaystyle s-1$?

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

Proof:Assume, to the contrary, that the theorem is false. Then conditions (1) and (2) are satisfied but there exist some positive integers $\displaystyle n$ for which $\displaystyle P(n)$ is a false statement. Let
$\displaystyle S = \{n \in \mathbb{N}: P(n)$ is false $\displaystyle \}$
Since $\displaystyle S$ is a nonempty subset of $\displaystyle \mathbb{N}$ , it follows by the Well-Ordering Principle that $\displaystyle S$ contains $\displaystyle s$. Since $\displaystyle P(1)$ is true, $\displaystyle 1 \in S$.
Here I am lost:
Thus $\displaystyle s \geq 2$ and $\displaystyle s-1 \in \mathbb{N}$. Therefore, $\displaystyle s-1 \in S$ and so $\displaystyle P(s-1)$ is a true statement. By condition (2), $\displaystyle P(s)$ is also true
and so $\displaystyle s \not \in S$. This however, contradicts our assumption that $\displaystyle s \in S$.
Question: What is $\displaystyle s-1$?

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

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

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

And $\displaystyle s-1$ is the first integer less than $\displaystyle s$.
Thank you for the explanation. Now I understand.

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

#### Search Tags

proof, theorem, understanding 