I am trying to work through an example in my book and it just seems nonsensical
Why is mathematical induction a valid proof technique? The reason comes from the well ordering property, listed in Appendix 1, as an axiom for the set of positive integers, which
states that "every nonempty subset of the set of positive integers has a least element". So, suppose
we know that $P(1)$ is true and that the proposition $P(k)\to P(k + 1)$ is true for all positive
integers $k$. To show that $P(n)$ must be true for all positive integers $n$, assume that there is at
least one positive integer for which $P(n)$ is false. Then the set $S$ of positive integers for which
$P(n)$ is false is nonempty. Thus, by the well-ordering property, $S$ has a least element, which
will be denoted by m.We know that $m$ cannot be $1$, because $P(1)$ is true. Because $m$ is positive
and greater than $1$, $m − 1$ is a positive integer. Furthermore, because $m − 1$ is less than $m$, it is
not in $S$, so $P(m− 1)$ must be true. Because the conditional statement $P(m− 1)\to P(m)$ is
also true, it must be the case that $P(m)$ is true. This contradicts the choice of $m$. Hence, $P(n)$
must be true for every positive integer $n$."
I am getting confused at a lot of parts of this. So assuming that $P(1)$ is true and assuming that $P(k)$ implies $P(k+1)$ for all positive integers, why do I have to show that one positive integer is false to show that it must be true? I don't understand that.
Anyways now my set S of $P(n)$ false inputs is now not empty. So that element is now $m$, and $m$ must be positive so then they claim $P(m-1)$ must be true because it is less than $m$. Why is this true? For example why can't I have $5$ and $4$ both being false where $m$ is $5$? Why does $P(m -1)$ imply $P(m)$? There doesn't seem to be proven anywhere. They then claim that $P(m)$ must now be true even though they previously claimed that it was false, so how can that be? It seems like the contradiction works to disprove the original assessment that $P(n)$ must be true.
Best Answer
You don't have to show that one positive integer is false in order to show that the proposition is false.
Notice that the quoted proof says:
That's something of a clue already. In mathematics, you can't prove something by first assuming that it's true. Instead, this is an example of a proof by contradiction. We start out by assuming that what we are trying to prove is false, and then derive a contradiction. Since we assume that the axioms of mathematics are sound, this means that our original assumption must be false, and hence that what we are trying to prove is true.
In this case, we want to prove that $P(n)$ is true for all $n$. The negation of that statement is that $P(n)$ is false for some $n$. We now work with this assumption and try to derive a contradiction.
We now let $m$ be the smallest number such that $P(m)$ is false. It's very important that $m$ is the smallest such example, which is why we need the well-ordering principle. In order to make the dependence on the well-ordering principle explicit, we say:
But you don't have to think that way. Intuitively, if there is one counterexample among the natural numbers, there must be a smallest one. (Note that the same is not true if we restrict attention to the integers, which do not satisfy the well-ordering principle. For example, $\{-1, -2, -3, \dots\}$ hasn't got a least element.
Now consider $P(m-1)$. Since $m$ is the smallest number with $P(m)$ false, and $m-1$ is smaller than $m$, $P(m-1)$ must be true.
The reason you can't have both $P(4)$ and $P(5)$ false when $m$ is $5$ is that $m$ has to be the smallest counterexample, and it clearly isn't in this case, as $4$ is a smaller counterexample. In this case $m=4$ (or some smaller number).
$P(m-1)$ implies $P(m)$ by assumption. We are trying to show that $P(n)$ is true for all $n$ when we are given these pieces of information:
We obviously need some information about $P$ to prove that $P(n)$ is true for all $n$, and this is the information we are given. Now, setting $k=m-1$, and noting that $P(m-1)$ is true, we must have that $P(k+1)=P((m-1)+1)=P(m)$ is true.
We have now arrived at a contradiction. This serves to disprove our initial assertion that $P(n)$ is not true for some $n$. It does not disprove the theorem that we are trying to prove - that $P(n)$ is true for all $n$. Indeed, since it disproves the negation of that theorem, it proves the theorem and we win.