How is GLB and LUB different than the maximum and minimum of a poset?

6.5k Views Asked by At

As the subject asks, how is the greatest lower bound different than the minimum element in a poset, and subsequently, how is the least upper bound different than the minimum? How does a set having no maximum but multiple maximal elements affect the existence of a LUB?


Edit:

Here's an assignment question I have on the topic...

enter image description here

Consider the subset $A=\{4,5,7\}$ of $W$. Does $\sup(A)$ exist? What about $\inf(A)$?

I'm guessing that Sup is Suprema (or LUB), and inf is Infimum (GLB)... but I have no idea because I missed that day in class.

All I can guess is that the subset $A$ is ordered such that $7\preceq 5$, but $4$ and $5$ are incomparable. I don't know what to do with it.

2

There are 2 best solutions below

0
On BEST ANSWER

It's important to be precise in your context, here. If you are discussing a poset $P$, and wondering if $P$ has a least upper bound in the poset $P$, then you are wondering precisely if $P$ has a maximum element.

However, if you were discussing a subset of $P$, say $A$, and wondering if $A$ has a least upper bound in the poset $P$, then that's a different matter. If $A$ has a maximum element, then it will readily be the least upper bound of $A$. However, if $A$ has no maximum element, but only maximal elements--such as $A=\{a,b\}$ with $a,b$ incomparable--then the least upper bound of $A$ (if it exists) will necessarily be a member of $P$ that is not in $A$.


In your particular example with $A=\{4,5,7\}$, note that $4$ is incomparable with both $5$ and $7$, and that $5$ is greater than $7$. Hence, any upper bound of $A$ need only be an upper bound of $4$ and $5$, and any lower bound of $A$ need only be a lower bound of $4$ and $7$. The set of all upper bounds of $A$ is $\{1,2,3\}$ and this set has a least element, namely $3$, so $\sup A=3$. The only lower bound of $A$ is $8$, so $\inf A=8$.

Note that in general, $\sup A$ (if it exists) is the minimum element of the set of upper bounds of $A$, and $\inf A$ (if it exists) is the maximum element of the set of lower bounds of $A$. If $A$ has no upper (lower) bounds, then $\sup A$ ($\inf A$) doesn't exist. For example, if we didn't have the node $8$ in your example $W$, then $\inf A$ wouldn't exist. If the set of upper (lower) bounds of $A$ is non-empty, but has no minimum (maximum) element, then $\sup A$ ($\inf A$) doesn't exist. For example, suppose we were to add another node, $9$, to your example, on the same level as $8$, with $9\prec 6$, $9\prec 7$, and with $8$ and $9$ incomparable. In that case, the set of lower bounds of $A$ would be $\{8,9\}$, but since $8$ and $9$ are incomparable, that set has no maximum element, meaning $\inf A$ wouldn't exist.

4
On

The greatest lower bound of the set of all positive numbers is $0$, but there is no minimum of the set of all positive numbers.

If a set is partially ordered but not linearly ordered then there may be two incomparable elements, and one immediatley below both that is the greatest lower bound of that set of two, but again there is no minimum of the set containing just those two.

For sets that do have a minimum, the greatest lower bound is the minimum.

Later edit in response to comments: Consider this partially ordered set: $$ \begin{align} a & < b,\\ a & < c,\\ b,\ c& \text{ are incomparable}. \end{align} $$ Then the set $\{b,c\}$ has no least element, but it has a greatest lower bound, which is $a$.