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

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?

-
There are some errors in your arguing above: Reflexivity: $D(x)$ equals (by definition) $\{y \in \mathbb N : y \mid x\}$ (where $|$ means "is a divisor of") and not $\{x \in \mathbb N : x \mid x\} (= \mathbb N)$. Anti-Symmetry: What do you mean with a conjuction of sets? I'm sure you wanted to write $\{z \in \mathbb N : z \mid x\} = \{z \in \mathbb N : z \mid y\}$ (and so $x = y$ by the FTA). Transitivity: Again: What is a conjuction of sets? What does it mean that a set is implied by others? – martini Jul 12 '12 at 9:03
@martini yes, I should have written $D(x)=\{y \in \mathbb N : y \mid x\}$! In regard to the misuse of $\land$ I thought it would connect two propositions so what I meant (paraphrasing from the ani-symmetry section) is "if $y \in \mathbb N$ are divisors of $x$ and $x \in \mathbb N$ are divisors of $y$ then...". My teacher has used this kind of notation in class so maybe I've wrongly assumed it is correct. – haunted85 Jul 12 '12 at 9:48
BTW $x\Sigma y$ is equivalent to $x\mid y$, which is very frequently given as an example of a partial ordering, see e.g. Divides is Partial Ordering on Positive Integers at ProofWiki. – Martin Sleziak Jul 12 '12 at 9:48

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.

-

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)$.

-