# Divisor Relation on Positive Integers is Partial Ordering

## 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

$\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$