Divisibility is a partial order

Statement

For $a,b \in \mathbb{N}$ we say $a \mid b$ (a divides b) if there is $k \in \mathbb{N}$ with $b = ak$. Prove that $(\mathbb{N}, \mid)$ is a partially ordered set, but not a totally ordered one.

Solution

We check the three properties of a partial order.

• Reflexive: $a = a \cdot 1$, so $a \mid a$.
• Antisymmetric: if $a \mid b$ and $b \mid a$ with $a,b \in \mathbb{N}$, then $b = ak$ and $a = bh$, so $a = akh$. If $a \ne 0$ then $kh = 1$, i.e. $k = h = 1$ and $a = b$; if $a = 0$ then $b = 0$. In every case $a = b$.
• Transitive: if $a \mid b$ and $b \mid c$, then $b = ak$ and $c = bh = a(kh)$, so $a \mid c$.

Hence $(\mathbb{N},\mid)$ is a partial order. It is not total: for instance $2$ and $3$ are incomparable, since $2 \nmid 3$ and $3 \nmid 2$. $\blacksquare$