# Why there may be no single “maximum” element in a partially ordered set?

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 ?

-
Some counterexamples can be found at ProofWiki and Wikipedia. – Martin Sleziak Aug 4 '12 at 12:42
@MartinSleziak to understand the counter example I have to understand this one first. – Geek Aug 4 '12 at 12:43
Related question: difference between maximal element and greatest element. – Martin Sleziak Aug 4 '12 at 12:51

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.

-

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.

-

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.

-
@M Turgeon What is "lattice of subsets?" Can you put a drawing in your answer somehow ? – Geek Aug 4 '12 at 12:59
@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$. – David Wheeler Aug 4 '12 at 13:27
@Geek ProofWiki: Subset Relation on Power Set is Partial Ordering. You can see some Hasse diagrams as examples in Wikipedia articles on posets and Hasse diagrams or here. (And in many other places.) – Martin Sleziak Aug 4 '12 at 13:36
@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. – M Turgeon Aug 4 '12 at 17:22
@Geek I've put some diagrams also here: 2-element set, 3-element set, 4-element set – Martin Sleziak Aug 4 '12 at 18:03

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:

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

-
"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 ? – Geek Aug 4 '12 at 12:52
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. – Martin Sleziak Aug 4 '12 at 12:53
Then your relation is not reflexive, and therefore, not a partial order. – David Wheeler Aug 4 '12 at 13:02
@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. (I used the boxes because I wanted to follow the example posted by OP - the one which he is asking about.) – Martin Sleziak Aug 4 '12 at 13:06
@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. – David Wheeler Aug 4 '12 at 13:11