Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Have you tried reading the definitions? If you do, you'll notice they're very different. –  Chris Eagle Mar 1 '13 at 17:46
1  
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$. –  Michael Hardy Mar 1 '13 at 17:53
1  
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. –  Michael Hardy Mar 1 '13 at 17:55
1  
@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$. –  Chris Eagle Mar 1 '13 at 17:59
1  
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. –  Michael Hardy Mar 1 '13 at 18:02

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
But $0$ isn't in the set $\mathbb{R}^{+}$ isn't it? –  agent154 Mar 1 '13 at 17:30
    
@agent154 : exactly. The greatest lower bound of a set need not be a member of the set. –  Michael Hardy Mar 1 '13 at 17:31
    
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. –  agent154 Mar 1 '13 at 17:34
    
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. –  Michael Hardy Mar 1 '13 at 17:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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