Theorem 1: Well-Ordering Princple
Every non-empty set of non-negative integers contains a least element
Proof:
(1) Assume that there exists a non-empty set $S$ of positive integers that does not contain a least element.
(2) Let $P(n)$ be true if $n$ is an element of $S$
(3) $P(0)$ is false. If true, then $0$ would be the least element for $S$
(4) Assume that for all $i \le n, P(i)$ is false.
(5) It follows that $P(n+1)$ is false. If not, then $n+1$ would be the least element for $S$.
(6) But, then by the Principle of Mathematical Induction, there is no positive integer in $S$
(7) This contradicts our assumption in (1) that $S$ is non-empty. Therefore, we can reject our assumption in step (1).
Note: This is an example of a proof by contradiction.
No comments:
Post a Comment