0
$\begingroup$

From Appendix B.2 (relations) of Introduction to Algorithms by Cormen et al:

In a partially ordered set $A$, there may be no single "maximum" element $a$ such that $b R a$ for all $b ∈ A$. Instead, there may several maximal elements a such that for no $b ∈ A$, where $b ≠ a$, is it the case that $a R b$. For example, in a collection of different-sized boxes there may be several maximal boxes that don't fit inside any other box, yet no single "maximum" box into which any other box will fit.

I know the definition of a partial ordered set , but do not get why the author/authors say that "there may be no single "maximum" element" in a partially ordered set ?

  • 0
    Related question: [difference between maximal element and greatest element](http://math.stackexchange.com/questions/44774/difference-between-maximal-element-and-greatest-element).2012-08-04

4 Answers 4

9

Remember that we're dealing with a partial order! This is fundamentally different from a total order like $\leq$ is on numbers.

Because: For all numbers, we have either $a\leq b$ or $b\leq a$, i.e. everything is comparable.

However a partial order is partial because elements need not be comparable. Solely if elements should happen to be comparable, then the partial order imposes some laws like transitivity.

Now take as an example the proper subsets of $\{1,2,3\}$ with the partial order of $\subseteq$. E.g. $\{1\} \subseteq \{1,2\}$, but the sets $\{1,2\}$ and $\{2,3\}$ simply are not comparable because neither includes the other. However there are no "bigger" proper subsets to each of them, so both are maximal.

Now if in turn all elements were comparable, the maximum was unique (hence in total orders it is). But in partial orders, this isn't usually the case.

4

For another easy to see example, consider the set $\{1,2,3,4,6\}$ and define $a \leq b$ if $a|b$. This is a partial order, and both $4$ and $6$ are maximal elements.

3

Take a finite set. Consider the lattice of subsets; this is a partially ordered set. Now, if you consider only proper subsets, you still have a partially ordered set, but now, every subset which consists of all elements except one is a maximal element. If you draw it, you will see it right away.

  • 0
    @Geek I've put some diagrams also here: [2-element set](http://i.stack.imgur.com/ai2ph.png), [3-element set](http://i.stack.imgur.com/pc7Hr.png), [4-element set](http://i.stack.imgur.com/mju9L.png)2012-08-04
0

Suppose that our partial order is given (informally) by "box $a$ can be put into the box $b$".

If I have boxes $a$ and $b$ of the same size, I cannot put one of them into the other; this means that neither $a\le b$ nor $b\le a$ holds.

Formally, we have a partial ordering $\le=\{(a,a),(b,b)\}$ on the set $\{a,b\}$.

Hasse diagram of this poset looks like this:

Hasse

Then $a$ and $b$ are both maximal elements. I.e., maximal element is not unique.

  • 0
    @DavidWheeler The relation is reflexive if the boxes can exactly fit into themselves .2012-08-04