2
$\begingroup$

I am studying the concept of a Partially Ordered Set, abbreviated as 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.

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

  • 3
    You really should read [this](http://meta.math.stackexchange.com/questions/3399/why-should-we-accept-answers).2012-11-18

2 Answers 2

8

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

  • 1
    @jun: Note, however, that *maximal element* is the usual term.2012-11-18
  • 0
    @William: I got confused of your statement that $\{x,y\}$ is a POSET such that $x$ and $y$ are not related. :D)2012-11-18
  • 0
    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$.2012-11-18
  • 0
    @William Macrae: Thanks for your help, I got it now.2012-11-18
3

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.

  • 1
    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?2012-11-18
  • 1
    for every $x\in A$...... This implies that $A$ is singleton which is a contradiction.2012-11-18
  • 0
    Ah ok, I stand corrected, it should be $A$. Many thanks. :D)2012-11-18