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 ?

  • 1
    Some counterexamples can be found at [ProofWiki](http://www.proofwiki.org/wiki/Maximal_Element_Not_Necessarily_Greatest_Element) and [Wikipedia](http://en.wikipedia.org/wiki/Maximal_element#Existence_and_uniqueness).2012-08-04
  • 0
    @MartinSleziak to understand the counter example I have to understand this one first.2012-08-04
  • 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

8

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
    @M Turgeon What is "lattice of subsets?" Can you put a drawing in your answer somehow ?2012-08-04
  • 1
    @Geek he is talking about the power set, minus the set we're taking the power set of (boy, that's a mouthful). The partial order is given by inclusion. For example, if $S = \{a,b,c\}$ then the set he is talking about is $\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}$. All 3 2-element subsets of $S$ are maximal elements on $2^S-S,\subseteq$.2012-08-04
  • 0
    @Geek ProofWiki: [Subset Relation on Power Set is Partial Ordering](http://www.proofwiki.org/wiki/Subset_Relation_on_Power_Set_is_Partial_Ordering). You can see some Hasse diagrams as examples in Wikipedia articles on [posets](http://en.wikipedia.org/wiki/Partially_ordered_set) and [Hasse diagrams](http://en.wikipedia.org/wiki/Hasse_diagram) or [here](http://demonstrations.wolfram.com/HasseDiagramOfPowerSets/). (And in many other places.)2012-08-04
  • 0
    @Geek Unfortunately, I have no idea how to put pictures in my answer, but the Hasse diagrams Martin put in his comment is exactly what I meant.2012-08-04
  • 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
    "if I have boxes a and b of the same size; this means that neither a≤b nor b≤a holds." .If they are of the same size(a==b) both the inequalities hold.Why are you saying neither holds ?2012-08-04
  • 0
    My relation $\le$ is defined by "a box can be put into other box"; not by comparing size. If the boxes are thick enough, I cannot put one of them into the box of the same size.2012-08-04
  • 0
    Then your relation is not reflexive, and therefore, not a partial order.2012-08-04
  • 0
    @David The relation $\{(a,a),(b,b)\}$ is reflexive. But the informal description of the example with boxes would correspond better to a [strict partial order](http://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders). (I used the boxes because I wanted to follow the example posted by OP - the one which he is asking about.)2012-08-04
  • 2
    @MartinSleziak I understand your motivation. My comment is intended to highlight the ambiguity of the example *in the original post*. Your formal definition of (a) partial order is indeed one. The example given is not a good one. My response is to give a *better* one.2012-08-04
  • 0
    @DavidWheeler The relation is reflexive if the boxes can exactly fit into themselves .2012-08-04