understanding upper bound and lower bound in lattice

Question

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.

Answer 1

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.

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.)