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$:
\(\displaystyle x\) \(\divides\) \(\displaystyle y\)
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \exists q_1 \in \Z: \, \) \(\displaystyle q_1 x\) \(=\) \(\displaystyle y\) Definition of Divisor of Integer
\(\displaystyle y\) \(\divides\) \(\displaystyle z\)
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \exists q_2 \in \Z: \, \) \(\displaystyle q_2 y\) \(=\) \(\displaystyle z\) Definition of Divisor of Integer
\(\displaystyle \leadsto \ \ \) \(\displaystyle q_2 \paren {q_1 x}\) \(=\) \(\displaystyle z\) substituting for $y$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {q_2 q_1} x\) \(=\) \(\displaystyle z\) Integer Multiplication is Associative
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \exists q \in \Z: \, \) \(\displaystyle q x\) \(=\) \(\displaystyle z\) where $q = q_1 q_2$
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\divides\) \(\displaystyle 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:

\(\displaystyle a \divides b\) \(\implies\) \(\displaystyle \size a \le \size b\) Absolute Value of Integer is not less than Divisors
\(\displaystyle b \divides a\) \(\implies\) \(\displaystyle \size b \le \size a\) Absolute Value of Integer is not less than Divisors
\(\displaystyle \) \(\leadsto\) \(\displaystyle \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