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