Divisor Relation on Positive Integers is Partial Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

The divisor relation is a partial ordering of $\Z_{>0}$.


Proof

Checking in turn each of the criteria for an ordering:


Divisor Relation is Reflexive

From Integer Multiplication Identity is One:

$\forall n \in \Z: 1 \cdot n = n = n \cdot 1$

thus demonstrating that $n$ is a divisor of itself.

$\blacksquare$


Divisor Relation is Transitive

$\forall x, y, z \in \Z: x \divides y \land y \divides z \implies x \divides z$:
\(\ds x\) \(\divides\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds \exists q_1 \in \Z: \, \) \(\ds q_1 x\) \(=\) \(\ds y\) Definition of Divisor of Integer
\(\ds y\) \(\divides\) \(\ds z\)
\(\ds \leadsto \ \ \) \(\ds \exists q_2 \in \Z: \, \) \(\ds q_2 y\) \(=\) \(\ds z\) Definition of Divisor of Integer
\(\ds \leadsto \ \ \) \(\ds q_2 \paren {q_1 x}\) \(=\) \(\ds z\) substituting for $y$
\(\ds \leadsto \ \ \) \(\ds \paren {q_2 q_1} x\) \(=\) \(\ds z\) Integer Multiplication is Associative
\(\ds \leadsto \ \ \) \(\ds \exists q \in \Z: \, \) \(\ds q x\) \(=\) \(\ds z\) where $q = q_1 q_2$
\(\ds \leadsto \ \ \) \(\ds x\) \(\divides\) \(\ds z\) Definition of Divisor of Integer

$\blacksquare$


Divisor Relation is Antisymmetric

Let $a, b \in \Z_{> 0}$ such that $a \divides b$ and $b \divides a$.

Then:

\(\ds a \divides b\) \(\implies\) \(\ds \size a \le \size b\) Absolute Value of Integer is not less than Divisors
\(\ds b \divides a\) \(\implies\) \(\ds \size b \le \size a\) Absolute Value of Integer is not less than Divisors
\(\ds \) \(\leadsto\) \(\ds \size a = \size b\)


If we restrict ourselves to the domain of positive integers, we can see:

$\forall a, b \in \Z_{>0}: a \divides b \land b \divides a \implies a = b$

$\blacksquare$


Divisor Ordering is Partial

Let $a = 2$ and $b = 3$.

Then neither $a \divides b$ nor $b \divides a$.

Thus, while the divisor relation is an ordering, it is specifically a partial ordering

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Divisor_Relation_on_Positive_Integers_is_Partial_Ordering&oldid=566860"