# Overriding order relation while looking for lower bounds

Let $(\mathbb Z \times \mathbb Z^*, \pi)$ be a poset defined as follows:

\begin{aligned} (a,b) \pi(c,d)\Leftrightarrow (a,b) = (c,d) \text{ or } r(a,b) <r(c,d)\end{aligned}

whereas $r(x,y)$ is the reminder of the division of $x$ by $y$.

Let $X=\{(3,2),(12,5),(6,2),(11,9)\} \subset \mathbb Z \times \mathbb Z^*$ and find maximum, minimum, maximal elements, minimal elements, upper bounds, lower bounds, supremum and infimum.

I noticed that in gereral $\nexists(a,b)\in \mathbb Z \times \mathbb Z^* : r(a,b) <0$ and the only elements that have $0$ as reminder are in $S=\{(na,a)\in \mathbb Z \times \mathbb Z^* : n\in \mathbb Z\}$.

Generally speaking, let $P$ be a (partially) ordered set, and let $A$ be a subset of $P$ then we say $y\in P$ is a lower bound for $A$ if and only if $y\leq a$ for all $a\in A$.

As I come to find all the lower bounds for my specific poset, do I need to look for $(x,y)\in \mathbb Z \times \mathbb Z^*$ so that $(x,y)\leq (a,b)$ for all $(a,b)\in X$, meaning looking for $(x,y)\in\mathbb Z \times \mathbb Z^* : r(x,y) \leq r(a,b)$ or shall I substitute $\pi$ for $\leq$ used in the general definition and therefore look for $(x,y)\in \mathbb Z \times \mathbb Z^*$ so that $(x,y) \pi (a,b)$?

If the former is true then all lower bounds are in $S$, otherwise if the latter is true then there are no lower bounds because by very definition of $\pi$, if $(a,b)\neq(x,y)$ and $r(a,b)=r(x,y)$ then $(a,b)$ and $(x,y)$ are not comparable. Is that correct?

-

The relation $\,\pi\,$ determines a partial order on your set, in such a way that to say that $\,(a,b)\,$ "is less", or is dominated", by $\,(c,d)\,$ means precisely $\,(a,b)\pi(c,d)\,$ .

So yes: you can try to take lower/upper bounds for $\,X\,$ either from within or out $\,X\,$ . Sometimes you'll be able to find some of these bounds within $\,X\,$ (for example, when $\,X\,$ is finite we have only a finite number of checks to do) , and sometimes you won't. It usually isn't important unless some other specifications are given.

As you said, since we always have $\,r(a,b)\geq 0\,$ , if there's an element $\,(a,b)\,$ s.t. $\,r(a,b)=0\,$ we have then hit on a minimal element.

For example, since $\,6=2\cdot 3\Longrightarrow r(6,2)=0\Longrightarrow (6,2)\,$ is a minimal element in $\,\Bbb Z\times\Bbb Z\,$ and thus in any subset. Thus, this element is the minimum of $\,X\,$ as there's no other element less than it in $\,X\,$ . If, say, we also had $\,(6,3)\in X\,\,,\,\,or\,\,(30,5)\in X\,$ , then we'd have two minimal elements and the set wouldn't have minimum...Now you try to continue with this.

-
$\min(X)=(6,2)$, $\nexists \max(X)$, upper bounds are in $T = \{(x,y) \in \mathbb Z \times \mathbb Z^* : (12,5) \pi (x,y) \vee (11,9) \pi (x,y)\}$, lower bound is $(6,2)$, $\nexists \sup(X)$, $\inf(X) = (6,2)$, minimal element $(6,2)$, maximal elements $(12,5)$ and $(11,9)$. Correct? –  haunted85 Aug 30 '12 at 9:42
Well, $\,r(11,9)=2\Longrightarrow (a,b)\pi (11,9)\,\,\,\forall (a,b)\in X\,$ , and thus there is a maximum, which of course is also a maximal element. –  DonAntonio Aug 30 '12 at 10:35
Yes but also $r(12,5)=2$, if exists, isn't the maximum unique? (I'm so sorry there was a typo in my question, the element isn't $(15,2)$ but actually $(12,5)$). –  haunted85 Aug 30 '12 at 10:41
But $\,(12,5)\notin X\,$ ! So this is not a maximum but an upper bound... –  DonAntonio Aug 30 '12 at 10:43