Hasse図ずHasse diagramと極大元きょくだいげんmaximal element・極小元きょくしょうげんminimal element

date2026-07-02document_iddoc_f90d2d4f5910e2cdf7f80c2be17b8c6cdescriptionHasse図を有限半順序集合の比較関係を可視化する道具として導入し、極大元・極小元・最大元・最小元の違いを整理する講義である。prerequisites半順序関係と全順序関係type講義content_typelecturestatusactive

mathdiscrete-mathhasse-diagramposetlecture

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

1導入どうにゅう

有限ゆうげんな半順序集合はんじゅんじょしゅうごうfinite partially ordered setでは、任意にんいの 2 元げんが比較ひかくできるとは限かぎらない。そのため、一列いちれつに並ならべるよりも、上下関係じょうげかんけいを図ずとして描えがくほうが構造こうぞうが見みえやすい。この講義こうぎではHasse図ずHasse diagramを有限ゆうげんな場合ばあいに限かぎって扱あつかう。

極大元きょくだいげんmaximal elementと最大元さいだいげんgreatest element、極小元きょくしょうげんminimal elementと最小元さいしょうげんleast elementは混同こんどうしやすい。Hasse図ずHasse diagramを使つかうと、この違ちがいを視覚的しかくてきに理解りかいできる。

このとき、比較不能ひかくふのうな元げんelementが残のこりうることが重要じゅうようである。Hasse図ずHasse diagramは全順序ぜんじゅんじょtotal orderのようにすべてを横よこ一列いちれつへ押おし込こむのではなく、比較ひかくできる部分ぶぶんだけを上下じょうげに見みせる。

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.

2用語ようごと定義ていぎ

半順序集合はんじゅんじょしゅうごうpartially ordered set $(P, [PARSE ERROR: Undefined("Command(\"le\")")])$ と $a, b \in P$ に対たいして、 $a < b$ とは $a [PARSE ERROR: Undefined("Command(\"le\")")] b$ かつ $a \neq b$ を意味いみする。

$a < b$ であり、かつ $a < c < b$ となる $c \in P$ が存在そんざいしないとき、 $b$ は $a$ を被覆ひふくcoverするといい、 $a ≺ b$ と書かく。Hasse図ずHasse diagramでは、この被覆関係ひふくかんけいcover relationだけを線せんで結むすび、小ちいさい元げんelementを下した、大おおきい元げんelementを上うえに置おく。

2Terms and definitions

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

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

3極大きょくだい・最大さいだい・極小きょくしょう・最小さいしょう

極大元きょくだいげんmaximal elementとは、自分じぶんより真しんに大おおきい元げんelementが存在そんざいしない元げんelementである。最大元さいだいげんgreatest elementとは、すべての $x \in P$ について $x [PARSE ERROR: Undefined("Command(\"le\")")] m$ を満みたす $m$ である。

極小元きょくしょうげんminimal elementとは、自分じぶんより真しんに小ちいさい元げんelementが存在そんざいしない元げんelementである。最小元さいしょうげんleast elementとは、すべての $x \in P$ について $m [PARSE ERROR: Undefined("Command(\"le\")")] x$ を満みたす $m$ である。

最大元さいだいげんgreatest elementと最小元さいしょうげんleast elementは、候補こうほがすべての元げんelementと比較ひかくできることまで要求ようきゅうする。これに対たいして極大元きょくだいげんmaximal elementと極小元きょくしょうげんminimal elementは、自分じぶんより上うえまたは下したへ進すすめないという局所的きょくしょてきな条件じょうけんである。

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$ such that $x [PARSE ERROR: Undefined("Command(\"le\")")] m$ for every $x \in P$ .

A minimal element極小元きょくしょうげん is an element with no strictly smaller element below it. A least element最小元さいしょうげん is an element $m$ such that $m [PARSE ERROR: Undefined("Command(\"le\")")] x$ for every $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.

4方針ほうしん

有限半順序集合ゆうげんはんじゅんじょしゅうごうfinite partially ordered setのHasse図ずHasse diagramを作つくるときは、すべての比較関係ひかくかんけいcomparison relationを線せんで描かかない。推移性すいいせいtransitivityから分わかる線せんを省略しょうりゃくし、被覆関係ひふくかんけいcover relationだけを残のこす。

この有限ゆうげんな場合ばあいには、 $x < y$ なら $x$ から $y$ まで被覆関係ひふくかんけいを有限回ゆうげんかい辿たどれる。実際じっさい、 $x [PARSE ERROR: Undefined("Command(\"le\")")] z [PARSE ERROR: Undefined("Command(\"le\")")] y$ を満みたす元げんの有限集合ゆうげんしゅうごうから、 $x$ と $y$ を結むすぶこれ以上いじょう挿入そうにゅうできない鎖くさりを選えらぶと、隣となり合あう 2 元げんの間あいだには中間元ちゅうかんげんがなく、各段階かくだんかいが被覆関係ひふくかんけいになる。したがって上向うわむきの道みちから元もとの比較ひかくを復元ふくげんできる。無限半順序集合むげんはんじゅんじょしゅうごうでは、追加条件ついかじょうけんなしに被覆関係ひふくかんけいだけから順序全体じゅんじょぜんたいを復元ふくげんできるとは限かぎらない。

被覆関係ひふくかんけいcover relationとは、 $x < y$ で、 $x < z < y$ となる中間ちゅうかんの元げんelementがない関係かんけいである。図ずではこの線せんだけを描えがき、上向うわむきの道みちをたどることで省略しょうりゃくした比較ひかくを復元ふくげんする。

data/lecture/math/discrete-math/partial-and-total-orders.lecture.n.md

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$ , a finite chain of cover relations leads from $x$ to $y$ . Indeed, in the finite interval of elements $z$ satisfying $x [PARSE ERROR: Undefined("Command(\"le\")")] z [PARSE ERROR: Undefined("Command(\"le\")")] y$ , choose a chain from $x$ to $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$ with no intermediate element $z$ satisfying $x < z < y$ . Drawing only these edges and following upward paths recovers the finite order.

data/lecture/math/discrete-math/partial-and-total-orders.lecture.n.md

5直感的ちょっかんてきな説明せつめい

最大元さいだいげんgreatest elementは全員ぜんいんの上うえにいる 1 つの元げんelementである。一方いっぽう、極大元きょくだいげんmaximal elementは、自分じぶんより上うえに行いけない元げんelementである。したがって、極大元きょくだいげんmaximal elementは複数ふくすう存在そんざいしうるが、最大元さいだいげんgreatest elementが存在そんざいするなら一意いちいである。

下側したがわも同様どうようである。最小元さいしょうげんleast elementは全員ぜんいんの下したにいる 1 つの元げんelementであり、極小元きょくしょうげんminimal elementは自分じぶんより下したに行いけない元げんelementである。

最大元さいだいげんgreatest elementが存在そんざいすれば一意いちいだが、極大元きょくだいげんmaximal elementは複数ふくすうあってよい。さらに、上うえへ行いけない元げんelementがあっても、比較不能ひかくふのうな別べつの元げんelementがあるなら、それは全員ぜんいんの上うえにいるとは言いえない。

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.

6例題れいだい：極大元きょくだいげんmaximal elementと最大元さいだいげんgreatest element

6.1問題もんだい

$P = {{1}, {2}, {1, 2}, {1, 3}}$ を包含ほうがんinclusion $\subseteq$ で順序じゅんじょづける。被覆関係ひふくかんけいを列挙れっきょしてHasse図ずHasse diagramの層そうを示しめし、極大元きょくだいげんmaximal element・最大元さいだいげんgreatest element・極小元きょくしょうげんminimal element・最小元さいしょうげんleast elementを求もとめよ。

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

6.1Problem

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

6.2解説かいせつ

被覆関係ひふくかんけいは

{1} ≺ {1, 2}, {1} ≺ {1, 3}, {2} ≺ {1, 2}

の 3 本ぼんである。したがってHasse図ずHasse diagramでは下したの層そうに ${1}, {2}$ 、上うえの層そうに ${1, 2}, {1, 3}$ を置おき、この 3 組くみだけを線せんで結むすぶ。 ${1, 2}$ と ${1, 3}$ は互たがいに相手あいてを含ふくまないため、比較ひかくできない。

${1, 2}$ より真しんに大おおきい元げんelementは $P$ の中なかに存在そんざいしない。同様どうように ${1, 3}$ より真しんに大おおきい元げんelementも存在そんざいしない。したがって極大元きょくだいげんmaximal elementは ${1, 2}$ と ${1, 3}$ である。

最大元さいだいげんgreatest elementは全すべての元げんelementを含ふくむ元げんelementでなければならない。 ${1, 2}$ は ${1, 3}$ を含ふくまず、 ${1, 3}$ は ${1, 2}$ を含ふくまない。したがって最大元さいだいげんgreatest elementは存在そんざいしない。

下したの層そうにある ${1}$ と ${2}$ より真しんに小ちいさい元げんはないので、これらが極小元きょくしょうげんminimal elementである。2 つは比較不能ひかくふのうなので、すべての元げんの下したにある最小元さいしょうげんleast elementは存在そんざいしない。

6.2Explanation

The cover relations are

{1} ≺ {1, 2}, {1} ≺ {1, 3}, {2} ≺ {1, 2} .

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

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

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

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

7見分みわけ方かた

最大元さいだいげんgreatest elementは、すべての元げんelementと比較ひかくして上うえにある必要ひつようがある。
極大元きょくだいげんmaximal elementは、自分じぶんより上うえが存在そんざいしないだけでよい。
最小元さいしょうげんleast elementは、すべての元げんelementと比較ひかくして下したにある必要ひつようがある。
極小元きょくしょうげんminimal elementは、自分じぶんより下したが存在そんざいしないだけでよい。
Hasse図ずHasse diagramでは、推移性すいいせいtransitivityで分わかる線せんは省略しょうりゃくする。

判定はんていでは、まず候補こうほを 1 つ選えらび、その候補こうほがすべての元げんelementと必要ひつような向むきで比較ひかくできるかを調しらべる。比較不能ひかくふのうな元げんelementが 1 つでもあれば、最大元さいだいげんgreatest elementや最小元さいしょうげんleast elementではない。

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.