Set of Integers is not Well-Ordered by Usual Ordering
Jump to navigation
Jump to search
Theorem
The set of integers $\Z$ is not well-ordered under the usual ordering $\le$.
Proof
Aiming for a contradiction, suppose $\Z$ is a well-ordered set.
Then by definition, all subsets of $\Z$ has a smallest element.
But take $\Z$ itself.
Suppose $x \in \Z$ is a smallest element.
Then $x - 1 \in \Z$.
But $x - 1 < x$, which contradicts the supposition that $x \in \Z$ is a smallest element.
Hence there can be no such smallest element.
So by Proof by Contradiction, $\Z$ is not well-ordered by $\le$.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction: Exercise $15 \ \text{(a)}$