I have a question from my textbook and wanted to make sure that I understood it. I have marked in a green box the question that I have.
4 Answers
$\begingroup$To answer the first statement:
Now how could we conclude that therefore $s-1$ is not an element of $S$.
Since we've applied the Well-Ordering Principle to the set $S$, it follows that there must be a least element. We've defined this least element as $s$. And if we subtract $1$ from $s$, we have a new natural number $s-1 < s$, so we can't have $s-1$ in the set $S$.
To answer the statement:
I understand that if $s=2$, then $s-1$ would not be an element of $S$ since $P(1)$ is true.
If $s=2$, then that means that we've explicitly stated that $2$ is the least element of the set $S$. Then $s-1$ is not an element of the set $S$ because $s$ is the least element of $S$, and so as stated above in this answer, $s-1<s$ and so it can't be in $S$. In this case, the statement "(1) $P(1)$ is true" establishes that $s\ge 2$. We use "(2) the implication, if $P(k)$ is true, then $P(k+1)$ is true for every positive integer $k$" to arrive at a contradiction. So that when we prove the theorem (Principle of Mathematical Induction), "$P(1)$ is true" is there to act as our base case, so that $P(1)$ is true implies $P(2)$ is true. Then $P(2)$ implies that $P(3)$ is true and so on for every natural number.
To answer the last statement:
However what if $s$ is larger than $2$ how could I be sure that $s-1$ would not be an element of $S$.
If $s$ is larger than $2$, then $s$ is still our least element. I think that most of the confusion is coming from thinking that "(1) $P(1)$ is true" is very important in the proof. If, for example, the element $37$ was the least element of $S$, then $36$ wouldn't be in our set $S$.
$\endgroup$ $\begingroup$Because $s$ is the least element (least counter example) in the set $S$. Or if $s-1$ were also in $S$, then $s$ is not the least element, hence another contradiction.
$\endgroup$ $\begingroup$You objection is correct. A proof of induction requires no only well ordering, it requires that a predecessor function exists for nonzero values, and that the ordering is preserved under predecessor and successor. It is the reason why induction doesn't hold for $\mathbb N[x]$ despite the structure being well ordered.
$\endgroup$ 6 $\begingroup$If s was larger than 2 you would not be checking the whole set of positive integers, so you have to start from the least counter example. Since you have the implication "2" you do not need to apply the body of proof over and over again.
$\endgroup$
