# 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)}$