difference between maximal element and greatest element

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.

-

1
You have asked several questions, all of them received several answers. If there is an answer which satisfies you please accept it by using the half-transparent check mark nearby the voting, if there is no satisfactory answer please edit the question to reflect what is missing from the current answers. (Note, you can accept only one answer per question) – Asaf Karagila Jun 19 '11 at 14:37
@Asaf Karagil: To be honest, I didn't know, that it's necessary to mark one answer. I mean - I had several answers which helped me and I didn't want to mark only one answer and I decided to be neutral, not marking any post. – exTyn Jun 20 '11 at 18:52

7 Answers

You are maximal when there is nobody above you.

You are greatest when you are above everyone else.

• 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 orde having a unique maximal element, which is not greatest.)

-
I gave an example in my answer for such partial order. – Asaf Karagila Jun 11 '11 at 15:01
Ah, yes indeed you did. – JDH Jun 11 '11 at 15:22

2
Your apartment illustration is very nice! – wildildildlife Jun 11 '11 at 16:33

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.

-

2
I think your last "maximal" should be "greatest", if I'm understanding correctly. – Jason DeVito Jun 11 '11 at 15:56
@Jason: Oh, right. Sorry :-) – Asaf Karagila Jun 11 '11 at 16:49

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.

-

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. – Noldorin Sep 9 '12 at 0:25

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.

-

Maybe I would not take the degenerate case as an example :-) – Listing Jun 11 '11 at 16:40

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.

-

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.

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 68, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9553921818733215, "perplexity_flag": "head"}