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

$\endgroup$
1
  • 3
    $\begingroup$ You really should read this. $\endgroup$ Nov 18, 2012 at 3:16

2 Answers 2

13
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ @jun: Note, however, that maximal element is the usual term. $\endgroup$ Nov 18, 2012 at 3:30
  • $\begingroup$ @William: I got confused of your statement that $\{x,y\}$ is a POSET such that $x$ and $y$ are not related. :D) $\endgroup$ Nov 18, 2012 at 4:39
  • $\begingroup$ 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$. $\endgroup$ Nov 18, 2012 at 5:03
  • $\begingroup$ @William Macrae: Thanks for your help, I got it now. $\endgroup$ Nov 18, 2012 at 5:34
  • 1
    $\begingroup$ It was my understanding that a maximal element must be in the set. So given a set $Q \subset P$ an element $x \in P$ can be an upper bound for $Q$ but not a maximal element. $\endgroup$
    – bthmas
    Jan 19, 2019 at 15:43
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 18, 2012 at 4:58
  • 1
    $\begingroup$ for every $x\in A$...... This implies that $A$ is singleton which is a contradiction. $\endgroup$
    – Tatin
    Nov 18, 2012 at 5:02
  • $\begingroup$ Ah ok, I stand corrected, it should be $A$. Many thanks. :D) $\endgroup$ Nov 18, 2012 at 5:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .