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

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のようにすべてを横よこ一列いちれつへ押おし込こむのではなく、比較ひかくできる部分ぶぶんだけを上下じょうげに見みせる。

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

半順序集合はんじゅんじょしゅうごうpartially ordered set $$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le) と $$a,b\in P$$a,b\in P に対たいして、$$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するといい、$$a\prec b$$a\prec b と書かく。Hasse図ずHasse diagramでは、この被覆関係ひふくかんけいcover relationだけを線せんで結むすび、小ちいさい元げんelementを下した、大おおきい元げんelementを上うえに置おく。

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は、自分じぶんより上うえまたは下したへ進すすめないという局所的きょくしょてきな条件じょうけんである。

4方針ほうしん

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

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

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

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があるなら、それは全員ぜんいんの上うえにいるとは言いえない。

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 で順序じゅんじょづける。被覆関係ひふくかんけいを列挙れっきょしてHasse図ずHasse diagramの層そうを示しめし、極大元きょくだいげんmaximal element・最大元さいだいげんgreatest element・極小元きょくしょうげんminimal element・最小元さいしょうげんleast elementを求もとめよ。

6.2解説かいせつ

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

の 3 本ぼんである。したがってHasse図ずHasse diagramでは下したの層そうに $$\left\{1\right\},\left\{2\right\}$$\{1\},\{2\}、上うえの層そうに $$\{1,2\},\{1,3\}$$\{1,2\},\{1,3\} を置おき、この 3 組くみだけを線せんで結むすぶ。$$\{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は存在そんざいしない。

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

7見分みわけ方かた

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

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

8関連かんれんリンク

9演習えんしゅうリンク