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.

I am studying the concept of a partially ordered set(POSET) and one author says that a

"a maximal element need not be an upper bound".

I tried browsing the net to find an example of the preceding statement, but can't find a lucky one.:D)

Can someone provide me an example of this? Thanks in advance...

share|improve this question
3  
You really should read this. –  Brian M. Scott Nov 18 '12 at 3:16

2 Answers 2

up vote 5 down vote accepted

As a more complete reference on the two terms, see the Wikipedia page on Zorn's Lemma and the links to the two terms from there.

For the specific terms, it helps to consider that maximal element and non-dominated element are used synonymously (the latter is much clearer to me). A maximal element $x$ is one such that there is no $y > x$ (no $y$ that dominates $x$). An upper bound of some set, on the other hand is some $x$ such that $x \ge y$ for all $y$. So, the maximal element need not be related to all elements, but an upper bound does.

In a partial ordering, an upper bound is a maximal element, but the reverse is not necessarily true (and finding a maximal element is often possible when finding an upper bound is not). In a total ordering, the two are equivalent.

Trivial example of the difference: let $\{x, y\}$ be a poset such that $x$ and $y$ are not related. $x$ is a maximal element (it is not the case that $y > x$) but not an upper bound (because we don't have $y \le x$ either).

share|improve this answer
    
@jun: Note, however, that maximal element is the usual term. –  Brian M. Scott Nov 18 '12 at 3:30
    
Thank you very much –  juniven Nov 18 '12 at 4:22
    
@William: I got confused of your statement that $\{x,y\}$ is a POSET such that $x$ and $y$ are not related. :D) –  juniven Nov 18 '12 at 4:39
    
So, a poset is just a set of elements, and some relation, $\prec$ between them with some properties (transitive, reflexive, antisymmetric). Let these elements be $x$ and $y$. Let $x \prec x$ and $y \prec y$ (this is needed for the reflexive part). Importantly, $x \not \prec y$ and $y \not \prec x$. It should be easy to check antisymmetry and transitivity. Finally, observe that there is no $z \neq x$ such that $x \prec z$. Therefor, $x$ is maximal. However, $x$ is not an upper bound because we do not have $y \prec x$. –  William Macrae Nov 18 '12 at 5:03
    
@William Macrae: Thanks for your help, I got it now. –  juniven Nov 18 '12 at 5:34

Let $X$ be a set of at least two elements. Define a partial order $\prec$ on $X$ by, $$ a\prec b\Leftrightarrow a=b,\text{ for all }a,b\in X. $$ Let $A\subseteq X$ be a subset containing at least two elements. Clearly each element of $A$ is a maximal element of, $A$ but $A$ does not have any upper bound. Hence, a maximal element need not be an upper bound.

share|improve this answer
    
I like it. So, the idea is if there exists an upper bound $u$ for $A$, then for every $x\in X$, it follows (by the definition of the partial order) that $x=u$. This implies that $X=\{u\}$, a contradiction since $X$ has at least two elements. Am I right? –  juniven Nov 18 '12 at 4:58
    
for every $x\in A$...... This implies that $A$ is singleton which is a contradiction. –  Saugata Nov 18 '12 at 5:02
    
Ah ok, I stand corrected, it should be $A$. Many thanks. :D) –  juniven Nov 18 '12 at 5:31

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.