Hasse diagramsHasse図ず, maximal elements極大元きょくだいげん, and minimal elements極小元きょくしょうげん

1Introduction

In a finite partially ordered set有限半順序集合ゆうげんはんじゅんじょしゅうごう, not every two elements元げん have to be comparable. Therefore the structure is often easier to see by drawing vertical order information instead of forcing all elements into one line. This lecture treats Hasse diagramsHasse図ず only in the finite case.

The terms maximal element極大元きょくだいげん and greatest element最大元さいだいげん, and likewise minimal element極小元きょくしょうげん and least element最小元さいしょうげん, are easy to confuse. A Hasse diagram makes the difference visible.

Incomparable elements may remain. A Hasse diagram does not force every element into a total order; it displays only the comparisons that actually hold.

2Terms and definitions

For a partially ordered set半順序集合はんじゅんじょしゅうごう $$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le) and $$a,b\in P$$a,b\in P, the notation $$a<b$$a<b means $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b and $$a\ne b$$a\ne b.

If $$a<b$$a<b and there is no $$c\in P$$c\in P such that $$a<c<b$$a<c<b, then $$b$$b covers被覆ひふく $$a$$a, written $$a\prec b$$a\prec b. In a Hasse diagramHasse図ず, only this cover relation被覆関係ひふくかんけい is drawn, smaller elements元げん are placed lower, and larger elements are placed higher.

3Maximal, greatest, minimal, and least

A maximal element極大元きょくだいげん is an element元げん with no strictly larger element above it. A greatest element最大元さいだいげん is an element $$m$$m such that $$x\text{[PARSE ERROR: Undefined("Command("le")")]}m$$x\le m for every $$x\in P$$x\in P.

A minimal element極小元きょくしょうげん is an element with no strictly smaller element below it. A least element最小元さいしょうげん is an element $$m$$m such that $$m\text{[PARSE ERROR: Undefined("Command("le")")]}x$$m\le x for every $$x\in P$$x\in P.

A greatest or least element must be comparable with every element. Maximality and minimality are local conditions: they only say that one cannot move strictly upward or downward from the given element.

4Method

When drawing a Hasse diagramHasse図ず of a finite partially ordered set有限半順序集合ゆうげんはんじゅんじょしゅうごう, do not draw every comparison relation比較関係ひかくかんけい. Omit the lines forced by transitivity推移性すいいせい and keep only the cover relations被覆関係ひふくかんけい.

In the finite case, if $$x<y$$x<y, a finite chain of cover relations leads from $$x$$x to $$y$$y. Indeed, in the finite interval of elements $$z$$z satisfying $$x\text{[PARSE ERROR: Undefined("Command("le")")]}z\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le z\le y, choose a chain from $$x$$x to $$y$$y into which no further element can be inserted. Consecutive elements have no intermediate element, so each step is a cover. Thus upward paths recover every omitted comparison. For an infinite partially ordered set, cover edges need not determine the whole order without additional hypotheses.

A cover relation has $$x<y$$x<y with no intermediate element $$z$$z satisfying $$x<z<y$$x<z<y. Drawing only these edges and following upward paths recovers the finite order.

5Intuitive explanation

A greatest element最大元さいだいげん is one element元げん above every element. A maximal element極大元きょくだいげん is an element from which you cannot move upward. Thus there may be several maximal elements, but if a greatest element exists, it is unique.

The lower side is analogous. A least element最小元さいしょうげん is one element below every element, while a minimal element極小元きょくしょうげん is an element from which you cannot move downward.

A maximal element need not be greatest: if it is incomparable with another element, it is not above every element.

6Worked example: maximal elements極大元きょくだいげん and greatest elements最大元さいだいげん

6.1Problem

Order $$P=\left\{\right\{1\},\{2\},\{1,2\},\{1,3\left\}\right\}$$P=\{\{1\},\{2\},\{1,2\},\{1,3\}\} by inclusion包含ほうがん $$\subseteq$$\subseteq. List the cover relations, describe the layers of its Hasse diagramHasse図ず, and find its maximal, greatest, minimal, and least elements.

6.2Explanation

The cover relations are

Thus the lower layer of the Hasse diagram contains $$\left\{1\right\},\left\{2\right\}$$\{1\},\{2\}, the upper layer contains $$\{1,2\},\{1,3\}$$\{1,2\},\{1,3\}, and only these three pairs are joined. The two upper elements are incomparable.

There is no element元げん of $$P$$P strictly larger than $$\{1,2\}$$\{1,2\}, and likewise none strictly larger than $$\{1,3\}$$\{1,3\}. Therefore the maximal elements極大元きょくだいげん are $$\{1,2\}$$\{1,2\} and $$\{1,3\}$$\{1,3\}.

A greatest element最大元さいだいげん would have to contain every element of $$P$$P. Since $$\{1,2\}$$\{1,2\} does not contain $$\{1,3\}$$\{1,3\} and $$\{1,3\}$$\{1,3\} does not contain $$\{1,2\}$$\{1,2\}, no greatest element exists.

The lower elements $$\left\{1\right\}$$\{1\} and $$\left\{2\right\}$$\{2\} have no strictly smaller elements, so they are the minimal elements. Since they are incomparable, no least element exists.

7How to tell them apart

• A greatest element最大元さいだいげん must be above every element元げん.
• A maximal element極大元きょくだいげん only has to have no strictly larger element above it.
• A least element最小元さいしょうげん must be below every element.
• A minimal element極小元きょくしょうげん only has to have no strictly smaller element below it.
• A Hasse diagramHasse図ず omits edges implied by transitivity推移性すいいせい.

To test a candidate for greatest or least, compare it in the required direction with every element. One incomparable element is enough to rule it out.

8Related links

9Exercise links