Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
$\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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.