52
$\begingroup$

I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some examples etc.

I tried to explain this difference to myself using only definition, but maximal element and greatest element still seems almost the same for me.

Thank you.

$\endgroup$
1

7 Answers 7

94
$\begingroup$

You are maximal when there is nobody above you.

You are greatest when you are above everyone else.

Examples:

  • If nobody has eaten you, it doesn't follow that you have eaten everyone else.

  • If nobody is standing on your head, it doesn't follow that you are standing on everyone else's head.

  • If you live on the top floor of your apartment building, it doesn't follow that you live above everyone else in the city.

So maximal elements need not be greatest.

(Incidentally, although a greatest element is always a unique maximal element, it is a fun exercise to come up with a partial order having a unique maximal element, which is not greatest.)

$\endgroup$
13
  • 16
    $\begingroup$ Your apartment illustration is very nice! $\endgroup$ Jun 11, 2011 at 16:33
  • 4
    $\begingroup$ The world needs more answers like this. $\endgroup$ Apr 10, 2015 at 11:44
  • 2
    $\begingroup$ @ahorn No, because to be greatest, it must be above all other elements, and so those other elements cannot be maximal. $\endgroup$
    – JDH
    May 19, 2015 at 13:08
  • 3
    $\begingroup$ @JDH This is great. The first two lines made me laugh. $\endgroup$
    – 9301293
    Dec 1, 2015 at 6:28
  • 2
    $\begingroup$ @JDH I think this is an example of a partial order with a unique maximal element which is not greatest: $\mathbb{N}$ with the usual order along with a new element $x$ that is incomparable to any natural number. $x$ is the only maximal element but it is not a maximum. Is there a finite, or more natural, example? What can be said about the class of partial orders that satisfy your criterion? $\endgroup$
    – user76284
    Feb 28, 2018 at 20:26
40
$\begingroup$

The crucial issue is the difference between a partial order and a linear order.

A partial order is a set where sometimes you can say "this thing is bigger than that", but some things are just incomparable. In a linear order, you can always say "this thing is bigger than that."

For example, if you're working with the natural numbers (except $0$), $\{1,2,3,...\}$, and you say "I'm going to declare that $n \leq m$ iff $n|m$. Then, reflexivity is clear ($n|n$), antisymmetry is clear (if $n|m$ and $m|n$, then $n = m$. And transitivity is also easy to check ($n|m$ and $m|p$ implies $n|p$). So, this really is a partial order.

Now, in this notion of order, is $2\leq 3$? No, since $2$ doesn't divide evenly into 3. Well, is $3\leq 2$? Again, no, since $3$ doesn't divide evenly into $2$. The conclusion is that we simply have no way of comparing the sizes of $2$ and $3$ in this order.

Now, to answer your actual question, as Stefan has noted, in a linear order (where any two elements are comparable) the two notions coincide.

In a partial order, we can see the difference. An element is maximal if it's bigger than everything it can be compared to, but we're not claiming it can be compared to everything.
An element is greatest if it's bigger than everything it can be compared to, and we can compare it with everything.

$\endgroup$
4
  • 1
    $\begingroup$ Good answer. Along with Stefan's, the only clear ones on the page, as I see it! Once one realises that the poset concept isn't nearly so intuitive as a totally-ordered set, one can separate these concepts much more readily. $\endgroup$
    – Noldorin
    Sep 9, 2012 at 0:25
  • 1
    $\begingroup$ Best answer Ive read on the concept, especially the last paragraph. $\endgroup$
    – Abhinav
    Sep 25, 2015 at 4:51
  • 2
    $\begingroup$ Compared to the answer by @JDH, I think your answer is better! (Maybe I like to accept mathematic concepts in its own language) $\endgroup$ Aug 20, 2016 at 3:18
  • $\begingroup$ Such a nice explanation. Looking for things like this. Wish someday I will also be able to make others understand things like this. $\endgroup$
    – Manjoy Das
    Apr 9, 2021 at 8:37
26
$\begingroup$

Suppose $\langle A,R\rangle$ is a partially ordered set (i.e. $A$ is non-empty, $R$ is a partial order relation on $A$).

An element $a\in A$ is called maximal if $\forall b\in A(aRb\rightarrow b=a)$. That is, there is no one "above" $a$ (except perhaps $a$ itself).

An element $a\in A$ is called maximum or greatest if $\forall b\in A(bRa\lor b=a)$, that $a$ stands "above" everyone in $A$ in the relation $R$.

Note that both these definitions hold whether or not you require $R$ to be reflexive.

From this follows that a greatest element is by definition maximal, but not vice versa.

Consider the following case $A=\{a,b\}$ and $R$ is defined to be the identity relation, then both $a$ and $b$ are maximal, but neither is the greatest.

Another strong example with a single maximal element, but no greatest element is this: consider the set $\{a\}\cup\mathbb Z$, and the relation $R$ defined to be $<$ for integers and $aRa$ otherwise (i.e. $a$ does not stand with the integers in this relation). In this case $a$ is trivially a maximal element, no one is "above" it, however there is no maximum element, since no one stands over both $a$ and all the integers.

$\endgroup$
1
  • $\begingroup$ if i understand correctly, your example concerns the following partial order $\{a\} \bigcup \mathbb{Z}, <$. I'm not sure how you defines the the relation $R$ but $<$ is not reflexive. Can you explain your example a bit more? $\endgroup$
    – Jung
    Dec 2, 2020 at 15:54
12
$\begingroup$

Suppose you have a set of boxes. A box that does not fit into any other box is maximal. A box into which any other box fits is greatest.

$\endgroup$
0
7
$\begingroup$

In a totally ordered set those concepts are the same. So we need to consider partially ordered sets that are not totally ordered in order to find an example. The most common sets of that kind are sets of sets ordered by inclusion. Consider the set $\{\{0\},\{1\}\}$. It contains two elements, none of which is a subset of the other. Both elements are maximal, but the set has no greatest element.

$\endgroup$
1
  • $\begingroup$ Maybe I would not take the degenerate case as an example :-) $\endgroup$
    – Listing
    Jun 11, 2011 at 16:40
4
$\begingroup$

Take an ordered set $(P,\leq)$. An element $g\in P$ is called greatest if for every $p\in P$ we have $p\leq a$. An element $m\in P$ is called maximal if there exists no $q\in P$ such that $m<q$. If $P$ is totally ordered then the two notions coincide. But in partially ordered sets the two notions are different. Here's an example:

Take all humans that have ever lived on earth (including those still alive) and order them as following $A<B$ if $B$ is a descendant of $A$ (this in fact is an ordering). Observe now that every person $P$ that doesn't have children yet is a maximal element of the aforementioned order, since there doesn't exist any human that is descendant of $P$. On the other hand this order doesn't have a greatest element. Such a person would need to be a descendant of every human that has ever lived, which is impossible.

$\endgroup$
1
$\begingroup$

Consider the set ${2,3,4,6}$ under divisibility. This set has 2 maximal elements since $2|4$, $2|6$ and $3|6$ where we write $a|b$ to mean means $b$ is divisible by $a$. Since we do not have $3|4$ or $4|6$, both $4$ and $6$ act as Maximal elements, but it has no greatest element.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.