# Check if a relation is a partial or total order and find minimum, maximum, minimal and maximal elements

Given $\mathbb Z^-=\{x\in \mathbb Z:x<0\}$ and $T = \mathbb Z^-\times \mathbb N$, let the binary relation $\odot$ be defined as follows:

\begin{aligned} (a,b) \odot (c,d) \Longleftrightarrow a \leq c \land b \mid d \end{aligned}

Check if the operation $\odot$ sets order, in particular total order and also find minimum, maximum, maximal and minimal elements in $(T, \odot)$ if they exists.

In order for $\odot$ to be a partial order, its reflexivity, antisymmetry and transitivity has to be proved.

Reflexivity

It can be easily shown that $\forall (a,b) \in T$

\begin{aligned}(a,b) \odot (a,b) \Longleftrightarrow a \leq a \land b \mid b\end{aligned}

so this relation is reflexive.

Antisymmetry

In order for this property to be true the following condition must be valid $\forall (a,b),(c,d) \in T$:

\begin{aligned} (a,b) \odot (c,d) \land (c,d) \odot (a,b) \Rightarrow (a,b) = (c,d) \end{aligned}

The antisymmetry doesn't apply to this relation because while the following is always true:

\begin{aligned} a \leq c \land c \leq a \Rightarrow a = c \end{aligned}

we cannot state the same for the following:

\begin{aligned} b \mid d \land d \mid b \Rightarrow b = d\end{aligned}

because as $b \neq 0 \land d = 0$ (or similarly $b = 0 \land d \neq 0)$ then

\begin{aligned}\exists \alpha \in \mathbb Z : \alpha b = d \end{aligned} \begin{aligned}\exists \beta \in \mathbb Z : \beta d = b \end{aligned}

whereas $\alpha = 0$ but $\nexists \beta \in \mathbb Z : \beta 0 = d$. Hence this relation isn't antisymmetric.

Transitivity

We need to prove \begin{aligned} (a,b) \odot (c,d) \land (c,d) \odot (e,f) \Rightarrow (a,b) \odot (e,f) \end{aligned}

it's valid the following: \begin{aligned} a \leq c \land c \leq e \Rightarrow a \leq e \end{aligned}

the following is valid as well

\begin{aligned} a \mid c \land c \mid f \Rightarrow a \mid f \end{aligned}

as $\exists x \in \mathbb Z : ax = c$ and $\exists y \in \mathbb Z : yc = f$

it's safe to say $yxa=f$.

Conclusion: this relation isn't partial order, so in particular isn't a total order.

Is everything ok with my exercise or did I do anything wrong? When it comes to look for maximum, minimum and minimal or maximal elements I feel lost. So I think there's no maximum or minimum because both $\mathbb Z^-$ and $\mathbb N$ are inifinite. Apparently I don't have a clue on how to spot minimal or maximal elements for $T$. Will you please help me out with that?

-

Actually, it is a partial order. Given natural numbers $a,b$, we can conclude from $a\vert b\wedge b\vert a$ that $a=b.$ Your counterexample doesn't work, because, while everything divides $0$, $0$ only divides itself.

A maximum element would be some $(a,b)\in T$ such that for all $(c,d)\in T$, $c\leq a\wedge d\vert b$. This would require that $a$ be the greatest element of $\Bbb Z^-$ and that $b$ be a natural number that all natural numbers divide. Can you think of what that would be? Note that if there is a maximum element, then it is the only maximal element.

A minimum element would be some $(a,b)\in T$ such that for all $(c,d)\in T$, $c\geq a\wedge b\vert d$. Then $a$ would have to be the least element of $\Bbb Z^-$, which is not possible.

Given any $(a,b)$, we have that $(a-1,b)\odot(a,b)$, so there is always a different element preceding it. Thus, there are no minimal elements, either.

To determine whether or not $\odot$ totally orders $T$, we must determine whether for distinct $(a,b),(c,d)\in T$ we need have $(a,b)\odot(c,d)$ or $(c,d)\odot(a,b)$. It shouldn't be difficult to see that this need not hold (I leave it to you to find an example), so that $\odot$ does not totally order $T$, after all.

Edit: Well done in showing that it isn't a total order, and in finding the maximum element. It is in fact maximum (not just maximal) since for each $(c,d)\in T$ we have $c\leq-1$ and $d\vert 0$. Partial orders may or may not have a maximum or a minimum element, and may or may not have maximal or minimal elements. For an example of a partial order with a maximum element, take any set $A$, any $b\notin A$ and define a partial order $\precsim$ on $A\cup\{b\}$ by $c\precsim c$ for all $c$, and $a\precsim b$ for all $a\in A$. Then $b$ is the maximum element, and each $a\in A$ is incomparable to the others, so minimal, but not minimum if $A$ has multiple elements.

To elaborate on the antisymmetry of your example, let's suppose that $m,n\in\Bbb N$ such that $m\vert n\wedge n\vert m$. Hence, $$m=nv\wedge n=mw$$ for some $v,w\in\Bbb N$. If $m=0$, then so is $n$. If $m\neq 0$, then since $m=nv=mvw$, then $vw=1$, which is only possible for $v=w=1$ since $v,w\in\Bbb N$. Thus, again, $m=n$. Does that clear things up?

-
It's not a total order because if we consider $(-2,0)$ and $(-1,7)$ we can't compare them because $0 \nmid 7$ and $-1 \nleq -2$. The maximal element you're refering to should be $(-1, 0)$. There can only be a maximal element and not a maximum because the order is only partial? What I still don't get though is your note on my counterexample, will you please break it down for me? – haunted85 Jul 7 '12 at 17:22
Good work! I will add to my answer. – Cameron Buie Jul 7 '12 at 17:34
thank you for the counterexample explanation, it definitely cleared things up! What I still don't get is how do I correctly distinguish between maximum/maximal and minimum/minimal? – haunted85 Jul 8 '12 at 8:04
Maximal means there is nothing greater. Maximum means everything is less than or equal to it--equivalently, nothing is greater and everything is comparable. From this (and antisymmetry), we see that there can be at most one maximum, and if there is a maximum, then it is the only maximal element. If there is a maximal element with any element incomparable to it, then there is no maximum. – Cameron Buie Jul 8 '12 at 15:18
The same ideas apply to minimal vs. minimum. One thing, though. The maximum element, if it exists, will be the unique maximal element. However, unique maximal elements need not be maximum elements! Let $a\notin\Bbb Z$ and let $S=\{a\}\cup\Bbb Z$. Define $\precsim$ on $S$ by $a\precsim a$ and, for all $m,n\in\Bbb Z$, say $m\precsim n$ if and only if $m\leq n$. Then $a$ is the unique maximal and minimal element, but there is neither a maximum or a minimum! – Cameron Buie Jul 8 '12 at 15:42