Determine if $(\mathbb N, \Sigma)$ is a poset, look for $\min(\mathbb N, \Sigma)$ and $\max(\mathbb N, \Sigma)$

Question

Let $D(x) = \{y \in \mathbb N : y\text{ is a divisor of } x\}$ and let the relation $\Sigma$ be defined as follows:

$$\begin{aligned}x \Sigma y \Leftrightarrow D(x) \subseteq D(y) \end{aligned}$$

check $\Sigma$ is a partial order, if it is total and determine $\min(\mathbb N, \Sigma)$ and $\max(\mathbb N, \Sigma)$.

In order to prove $\Sigma$ to be a partial order I need to gain proof of its reflexivity, anti-simmetry and transitivity, so:

Reflexivity

$x \Sigma x \Leftrightarrow D(x) \subseteq D(x)$

$\{x\in \mathbb N : x \text{ is a divisor of } x\} \subseteq \{x\in \mathbb N : x \text{ is a divisor of } x\}$

Anti-symmetry

$x \Sigma y \land y\Sigma x \Rightarrow x= y$

$\{y \in \mathbb N : y \text{ is a divisor of } x\} \land \{x \in \mathbb N : x \text{ is a divisor of } y\}$

for the fundamental theorem of arithmetic $x = y$

Transitivity

$x \Sigma y \land y\Sigma z \Rightarrow x \Sigma z$

$\{y\in \mathbb N : y \text{ is a divisor of } x\} \land \{z \in \mathbb N : z \text{ is a divisor of } y\} \Rightarrow \{z \in \mathbb N : z \text{ is a divisor of } x\}$.

I should prove if $\Sigma$ is a total order, but I have no idea how I could do that, can it involve the fact that element $0 \in \mathbb N$ doesn't belong to this relation because $x\Sigma 0$ would mean $\{0 \text{ is a divisor of } x\}$ which is not possible? And my gut feeling tells me that $\max(\mathbb N, \Sigma) = 1$ and $\nexists\min(\mathbb N, \Sigma)$ but I don't know if I am right. Will you please give me a nudge in the right direction?

Answer 1

For $\Sigma$ to be a total order every two elements need to be comparable.

However $D(2)=\{1,2\}$ and $D(3)=\{1,3\}$ so neither is a subset of the other. Therefore $\lnot(2\Sigma3\lor 3\Sigma2)$ and so this is not a total order.

For $\min$ and $\max$, as you noted every number is a divisor of $0$; while no number except $1$ is a divisor of $1$, so $D(1)=\{1\}$ and $D(0)=\mathbb N$. It remains to show that $1\Sigma x$ for all $x$, but $1$ divides every number so it holds.

Answer 2

To elaborate a little more on martini's comment:

• Reflexivity: $D(x)\subseteq D(x)$ is obvious. ($A\subseteq A$ holds for any sets.)

• Anti-symmetry: $D(x)\subseteq D(y) \land D(y)\subseteq D(x)$ implies $D(y)=D(x)$. It remains to check that if $D(x)=D(y)$ implies $x=y$ (for non-negative integers).

• Transitivity: $D(x)\subseteq D(y)$ and $D(y)\subseteq D(z)$ imply $D(x)\subseteq D(z)$.