6
$\begingroup$

Consider the following Hasse diagrams.

enter image description here

enter image description here

and given here ,

enter image description here

Counter example on wiki :

enter image description here

Says " Non-lattice poset: b and c have common upper bounds d, e, and f, but none of them are the least upper bound."

But my question is : f is least upper bound, right?

Similarly,

enter image description here

Says"Non-lattice poset: a and b have common lower bounds 0, d, g, h, and i, but none of them are the greatest lower bound."

But my question is : 0 is greatest lower bound, right?


Can you explain lattice such that I can identify above lattices in hasse diagrams?

$\endgroup$

1 Answer 1

5
$\begingroup$

For your first question, $f$ is not the least upper bound of $b$ and $c$: $b\le d$ and $c\le d$, so $d$ is an upper bound of $b$ and $c$, and $d<f$, so $f$ cannot be the least upper bound of $b$ and $c$. There is no upper bound of $b$ and $c$ that is smaller than $d$, but $d$ is still not the least upper bound, because we also have $b\le e$ and $c\le e$: $e$ is another upper bound of $b$ and $c$, and $d\not\le e$. Similarly, $e\not\le d$, so $e$ isn’t the least upper bound of $b$ and $c$, either. Thus, none of the three upper bounds ($d,e,f$) of $b$ and $c$ is the least upper bound, and therefor $b$ and $c$ have no least upper bound. This of course means that the partial order is not a lattice.

Similarly reasoning applies to your second question. The lower bounds of $a$ and $b$ are $0,d,g,h$, and $i$, but none of them is the greatest lower bound of $a$ and $b$. $0$ is not the greatest lower bound of $a$ and $b$, because $0<g$, so $g$ is a lower bound of $a$ and $b$ that is larger than $0$. Similarly, $g<d$, and $d$ is a lower bound of $a$ and $b$, so $g$ is not the greatest lower bound of $a$ and $b$. We also have $h<d$, so $h$ cannot be the greatest lower bound of $a$ and $b$. The only candidates remaining are $d$ and $i$. There is no lower bound of $a$ and $b$ that is larger than $d$, and there is no lower bound of $a$ and $b$ that is larger than $i$, but neither is the greatest lower bound of $a$ and $b$, because neither is larger than the other: $d\not\le i$, and $i\not\le d$.

In the first set of four Hasse diagrams, only (i) and (iv) are lattices. We just saw that (iii) is not, and (ii) fails for similar reasons. Here it is again, with the nodes labelled:

                     a  
                    / \  
                   b   c  
                   |\ /|  
                   | d |  
                   |   |  
                    \ /  
                     e

Can you see why $b$ and $c$ have no greatest lower bound, and why $d$ and $e$ have no least upper bound? List all lower bounds of $b$ and $c$; is one of them larger than all of the others? Similarly, list all upper bounds of $d$ and $e$; is one of them smaller than all of the others?

This also takes care of two of the three non-lattices in the second picture. The third one is the second Hasse diagram in the picture, with $f$ and $g$ at the top: $f$ and $g$ have no upper bound at all, let alone a least upper bound!

$\endgroup$
5
  • 1
    $\begingroup$ I'd missed the definition of Lattic : a lattice is a partially ordered set in which every two elements have a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet). An example is given by the natural numbers, partially ordered by divisibility, for which the unique supremum is the least common multiple and the unique infimum is the greatest common divisor. $\endgroup$ Nov 26, 2015 at 10:15
  • $\begingroup$ GCD and LCM is always unique, rt ? $\endgroup$ Nov 26, 2015 at 10:17
  • 1
    $\begingroup$ @Mithlesh: Yes: one can prove that every divisor of $m$ and $n$ divides $\gcd(m,n)$, so if $d$ and $d'$ are both greatest common divisors of $m$ and $n$, then $d$ and $d'$ are positive integers that divide each other, so they must be equal. The situation with the least common multiple is similar. $\endgroup$ Nov 26, 2015 at 21:08
  • 1
    $\begingroup$ Thanks for nice explanation. I got it. $\endgroup$ Nov 27, 2015 at 8:47
  • 1
    $\begingroup$ @Mithlesh: You're welcome; glad it helped. $\endgroup$ Nov 27, 2015 at 9:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .