2
$\begingroup$

i am studying discrete math. have a topic lattices, i really cant understand how to find greatest lower bound and lowest upper bound. any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ It’s awfully hard to help in a vacuum; it would be much better to ask about a specific problem. $\endgroup$ – Brian M. Scott Nov 4 '13 at 16:58
  • 1
    $\begingroup$ sir, please help me to find out glb and lub in a any hasse diagram @BrianM.Scott $\endgroup$ – user200942 Nov 4 '13 at 16:59
  • $\begingroup$ @BrianM.Scott: what about the glb? $\endgroup$ – user200942 Nov 5 '13 at 14:39
  • $\begingroup$ For the greatest lower bound just turn the Hasse diagram upside-down and then find the least upper bound in the inverted diagram. If you do that with $e$ and $t$, for instance, in the partial order in my answer, you’ll find that their glb is $r$.Once you’ve done this a few times, you should be able to do it without actually turning the diagram upside-down: the glb of $x$ and $y$ is the highest element $u$ such that $u\le x$ and $u\le y$. That means that if $z$ is any lower bound of $x$ and $y$, then $z\le u$. $\endgroup$ – Brian M. Scott Nov 5 '13 at 14:43
  • $\begingroup$ @BrianM.Scott i have few more doubts shall we move this to discussion room.. $\endgroup$ – user200942 Nov 5 '13 at 14:44
12
$\begingroup$

I’ll use the following Hasse diagram of a partial order (taken from this question) as an example. It isn’t the Hasse diagram of a lattice, but it’s fine for illustrating greatest lower bounds and least upper bounds.

enter image description here

If $x$ and $y$ are elements of a partial order, an upper bound for $x$ and $y$ is simply an element $u$ such that $x\le u$ and $y\le u$; $u$ is the least upper bound of $x$ and $y$ if $u$ is $\le$ all upper bounds of $x$ and $y$. Let’s look at a couple of examples.

Find the elements $n$ and $g$. What elements $x$ have the property that $n\le x$ and $g\le x$? Those are the upper bounds of $n$ and $g$. It’s not hard to see that $r$ is one of them: you can get from $n$ to $r$ by travelling upwards in the diagram, and you can also get from $g$ to $r$ by travelling upwards in the diagram. Similarly, $s,t$, and $u$ are upper bounds for $n$ and $g$. There are two more that are a little harder to spot: $d$ and $a$ are also upper bounds for $n$ and $g$, for the same reason: you can get to each of them from both $n$ and $g$ by travelling upwards in the diagram. On the other hand, $i$ is not an upper bound for $n$ and $g$: $n\le i$, but $g\not\le i$. Now look at the set of upper bounds for $n$ and $g$: it’s $\{r,s,t,u,d,a\}$. The lowest member of that set is $r$: $r\le r,r\le s,r\le t,r\le u,r\le d$, and $r\le a$. That makes $r$ the least upper bound of $n$ and $g$.

What about $j$ and $r$? The elements above $j$ are $b,c,e,m,l,a,k,d,i,t,u$, and the elements above $g$ are $r,d,a,u,s,t$; the elements that are above both $j$ and $g$ are therefore $a,d,u,t$, so these four elements are the upper bounds of $j$ and $g$. Here, howver, we do not have a least upper bound: $d\le d,d\le a$, and $d\le u$, but $d\not\le t$, and none of $a,u$, and $t$ is $\le d$.

Now look at $b$ and $s$: the elements above $b$ are $c$ and $e$, and the elements above $s$ are $t$ and $u$, so there is no element that is above both $b$ and $s$. This means that $b$ and $s$ have no upper bound in this partial order. (In a lattice that could not happen: by definition every pair of elements of a lattice has a least upper bound.)

Finally, look at $d$ and $i$: $a$ and $u$ are upper bounds for $d$ and $i$ (and the only ones), but $a\not\le u$ and $u\not\le a$, so neither of them is a least upper bound for $d$ and $i$. This shows that two elements of a partial order can have upper bounds without having a least upper bound. (Again, this cannot happen in a lattice.)

$\endgroup$
  • $\begingroup$ On the other hand, i is not an upper bound for n and g: n≤i, but g≰i i couldnt get why g</i $\endgroup$ – user200942 Nov 4 '13 at 17:45
  • $\begingroup$ @user200942: There is no path upward from $g$ to $i$. If you start at $g$ and go up, the first step can only be to $r$. From $r$ you can go to $d$ or to $s$. From $d$ you can go to $a$ or to $u$, and from $s$ you can go only to $t$. Finally, from $t$ you can go only to $u$. Thus, there’s no way to reach $i$. $\endgroup$ – Brian M. Scott Nov 4 '13 at 17:48
  • $\begingroup$ Now look at b and s: the elements above b are c and e, and the elements above s are t and u, so there is no element that is above both b and s... why @brian $\endgroup$ – user200942 Nov 4 '13 at 17:49
  • $\begingroup$ is that like something we need a transitive relation to procced further.. $\endgroup$ – user200942 Nov 4 '13 at 17:51
  • $\begingroup$ @user200942: Isn’t it obvious that if the only elements above $b$ are $c$ and $e$, and the only elements above $s$ are $t$ and $u$, then there is nothing that is above both $b$ and $s$? The sets $\{c,e\}$ and $\{t,u\}$ have no members in common. // Yes, we’re dealing only with transitive relations. Specifically, we’re dealing only with partial orders. $\endgroup$ – Brian M. Scott Nov 4 '13 at 17:53

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