Divisor Relation on Positive Integers is Well-Founded Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

The divisor relation on $\Z_{>0}$ is a well-founded ordering.


Proof

Let $\struct {\Z_{>0}, \divides}$ denote the relational structure formed from the strictly positive integers $\Z_{>0}$ under the divisor relation $\divides$.

From Divisor Relation on Positive Integers is Partial Ordering, $\struct {\Z_{>0}, \divides}$ is a partially ordered set.

It remains to be shown that $\divides$ is well-founded.

By definition, we need to show:

For any non-empty set $T \subseteq \Z_{>0}$, there is an element $z \in T$ such that for all $y \in T \setminus \set z$, $y \nmid z$.

We choose $z = \min T$ as per the usual ordering on $\Z_{>0}$.

Then for any $y \in T \setminus \set z$, we have $y > z$.

By the contrapositive of Corollary to Absolute Value of Integer is not less than Divisors, we have $y \nmid z$.

Hence the result.

$\blacksquare$


Sources