1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you tried reading the definitions? If you do, you'll notice they're very different. $\endgroup$ – Chris Eagle Mar 1 '13 at 17:46
  • 1
    $\begingroup$ In your example, $\sup A=3$ and $\inf A=8$. There are three upper bounds of $A$, namely $3,1,2$. There is a smallest one of those and that is $3$. $\endgroup$ – Michael Hardy Mar 1 '13 at 17:53
  • 1
    $\begingroup$ No: $7$ is not the minimum of $A$, because $7$ is not less than or equal to $4$. The two elements $7$ and $4$ are incomparable. $\endgroup$ – Michael Hardy Mar 1 '13 at 17:55
  • 1
    $\begingroup$ @agent154: In which case "the minimum" is an error, since there could be several. In this case, both $4$ and $7$ are minimal in $A$. $\endgroup$ – Chris Eagle Mar 1 '13 at 17:59
  • 1
    $\begingroup$ A "minimal element" is one that has nothing less than it. A "minimum element" is one that all others are less than. There can be more than one minimal element in a poset, but only one minimum element. $\endgroup$ – Michael Hardy Mar 1 '13 at 18:02
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But $0$ isn't in the set $\mathbb{R}^{+}$ isn't it? $\endgroup$ – agent154 Mar 1 '13 at 17:30
  • $\begingroup$ @agent154 : exactly. The greatest lower bound of a set need not be a member of the set. $\endgroup$ – Michael Hardy Mar 1 '13 at 17:31
  • $\begingroup$ How can a GLB be something that is less than two minimal elements in a set when those two minimal elements are the lowest there is in the relation? The relation defines the ordering... so if an element is not in the set, I don't see how it can be related at all to the minimal elements. $\endgroup$ – agent154 Mar 1 '13 at 17:34
  • $\begingroup$ If they are the lowest elements in a partially ordered set, then there is nothing less than both of them, and the set of those two does not have a greatest lower bound. In other words, if they are minimal elements of the poset, then the set containing only the two of them has no greatest lower bound. $\endgroup$ – Michael Hardy Mar 1 '13 at 17:38
0
$\begingroup$

The supremum coincides with maximum in the finite case. That said, a great deal of basic example are not finite, so supremum is a different operation in general. The most notorious thing here is that supremum is an element not necesarilly in the original set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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