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.

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation

$$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: \end{align*}$$

I know for a poset to be a lattice, every subset in $\Bbb Z^+\times\Bbb Z^+$ has to have a LUB and GLB, but how do I determine whether this is true for all subsets?

Also, is it correct that this relation is a total order?

Much appreciated

share|improve this question
    
Small note: lattices only need lubs and glbs for finite sets. Also, if it is a total order then it definitely must be a lattice. –  Eric Stucky Oct 28 '13 at 11:22
add comment

1 Answer 1

HINT: You may find a picture helpful. For any real number $\alpha$ let $$L_\alpha=\{\langle x,y\rangle\in\Bbb R^2:x+y=\alpha\}\;;$$ this is just the graph of $x+y=\alpha$ and is a straight line of slope $-1$ through the points $\langle\alpha,0\rangle$ and $\langle 0,\alpha\rangle$. Each $\langle a,b\rangle\in\Bbb R^2$ is in exactly one of these sets $L_\alpha$, namely, $L_{a+b}$. Let $p$ and $q$ be distinct points in $\Bbb R^2$, and suppose that $p\in L_\alpha$ and $q\in L_\beta$. Then $p\,R\,q$ if and only if

  • $L_\alpha$ lies below $L_\beta$ (i.e., if $\alpha<\beta$), or
  • $L_\alpha=L_\beta$, and $p$ lies to the left of $q$ (i.e., the $x$-coordinate of $p$ is less than that of $q$).

In order for $\langle\Bbb Z^+\times\Bbb Z^+,R\rangle$ to be a lattice, it’s not necessary that every subset have a supremum and infimum: the requirement is that every pair of elements have a supremum and infimum. This is automatic if $\langle\Bbb Z^+\times\Bbb Z^+,R\rangle$ is a linear (or total) order, which in fact it is. This is very straightforward to prove directly: given $p_1=\langle x_1,y_1\rangle$ and $p_2=\langle x_2,y_2\rangle$ in $\Bbb Z^+\times\Bbb Z^+$, show that if it’s not the case that $p_1\,R\,p_2$, then $p_2\,R\,p_1$. You may find the geometric interpretation above helpful in thinking about this.

share|improve this answer
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.