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

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

1導入どうにゅう

半順序集合はんじゅんじょしゅうごう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 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 drawing is a Hasse diagramHasse図ず.

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.

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

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

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

2Terms and definitions

For a partially ordered set半順序集合はんじゅんじょしゅうごう $$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le), 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. 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\in P について $$x\text{[PARSE ERROR: Undefined("Command("le")")]}m$$x\le m を満みたす $$m$$m である。

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

4方針ほうしん

Hasse図ずHasse diagramを作つくるときは、すべての比較関係ひかくかんけいcomparison relationを線せんで描かかない。推移性すいいせいtransitivityから分わかる線せんを省略しょうりゃくし、被覆関係ひふくかんけいcover relationだけを残のこす。

この省略しょうりゃくで見みた目めの線せんの数かずは減へるが、半順序関係はんじゅんじょかんけいpartial orderとしての到達可能とうたつかのうな上下関係じょうげかんけいは保存ほぞんされる。

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

4Method

When drawing a Hasse diagramHasse図ず, do not draw every comparison relation比較関係ひかくかんけい. Omit the lines forced by transitivity推移性すいいせい and keep only the cover relations被覆関係ひふくかんけい.

This omission reduces the visible number of edges, but it preserves the reachable up-down structure of the partial order半順序関係はんじゅんじょかんけい.

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.

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

6.1問題もんだい

$$P=\left\{\right\{1\},\{2\},\{1,2\},\{1,3\left\}\right\}$$P=\{\{1\},\{2\},\{1,2\},\{1,3\}\} を包含ほうがんinclusion $$\subseteq$$\subseteq で順序じゅんじょづける。極大元きょくだいげんmaximal elementと最大元さいだいげんgreatest 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. Find the maximal elements極大元きょくだいげん and the greatest element最大元さいだいげん.

6.2解説かいせつ

$$\{1,2\}$$\{1,2\} は $$\left\{1\right\}$$\{1\} を含ふくみ、$$\{1,3\}$$\{1,3\} も $$\left\{1\right\}$$\{1\} を含ふくむ。しかし $$\{1,2\}$$\{1,2\} と $$\{1,3\}$$\{1,3\} は互たがいに相手あいてを含ふくまないため、比較ひかくできない。

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

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

6.2Explanation

The set $$\{1,2\}$$\{1,2\} contains $$\left\{1\right\}$$\{1\}, and $$\{1,3\}$$\{1,3\} also contains $$\left\{1\right\}$$\{1\}. However, $$\{1,2\}$$\{1,2\} and $$\{1,3\}$$\{1,3\} do not contain each other, so they 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.

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推移性すいいせい.

8演習えんしゅう・関連かんれんリンク

8Exercise and related links