Set of Integers is not Well-Ordered by Usual Ordering

From ProofWiki
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