束そくlatticeの基本きほん

1導入どうにゅう

束そくlatticeで理解りかいすべき中心ちゅうしんの問といは、「2 つの対象たいしょうobjectを比くらべたとき、両方りょうほうを上うえから押おさえる最小さいしょうの対象たいしょうobjectと、両方りょうほうの下したにある最大さいだいの対象たいしょうobjectが存在そんざいするか」である。

全順序関係ぜんじゅんじょかんけいtotal orderでは、2 つの対象たいしょうobjectの大おおきい方ほうと小ちいさい方ほうがすぐに決きまる。しかし半順序関係はんじゅんじょかんけいpartial orderでは、2 つが比較ひかくできないことがある。それでも、両方りょうほうの上うえにある最良さいりょうの候補こうほと、両方りょうほうの下したにある最良さいりょうの候補こうほが存在そんざいするなら、そこに束そくlatticeの構造こうぞうがある。

束そくlatticeでは、任意にんいの 2 元げんについて結むすびjoinと交まじわりmeetが存在そんざいすることが必要ひつようである。半順序集合はんじゅんじょしゅうごうなら必かならず束そくになるわけではなく、最良さいりょうの上界じょうかいと下界かかいが見みつかるかを調しらべる。

ここで「大おおきい」「小ちいさい」は数値すうちの大小だいしょうとは限かぎらず、使つかっている順序じゅんじょで決きまる。包含順序ほうがんじゅんじょでは集合しゅうごうの包含ほうがん、整除順序せいじょじゅんじょでは割わり切きれる向むきとして読よむ。

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

半順序集合はんじゅんじょしゅうごうpartially ordered set $$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le) に対たいして、$$a,b\in P$$a,b\in P の上界じょうかいupper boundとは、$$a\text{[PARSE ERROR: Undefined("Command("le")")]}u$$a\le u かつ $$b\text{[PARSE ERROR: Undefined("Command("le")")]}u$$b\le u を満みたす $$u\in P$$u\in P である。下界かかいlower boundとは、$$\ell \text{[PARSE ERROR: Undefined("Command("le")")]}a$$\ell\le a かつ $$\ell \text{[PARSE ERROR: Undefined("Command("le")")]}b$$\ell\le b を満みたす $$\ell \in P$$\ell\in P である。

最小上界さいしょうじょうかいleast upper bound（上限じょうげんsupremum）、または結むすびjoinとは、上界じょうかいupper boundの内うち最小さいしょうのものであり、$$a\vee b$$a\vee b と書かく。最大下界さいだいかかいgreatest lower bound（下限かげんinfimum）、または交まじわりmeetとは、下界かかいlower boundの内うち最大さいだいのものであり、$$a\wedge b$$a\wedge b と書かく。

任意にんいの $$a,b\in P$$a,b\in P について $$a\vee b$$a\vee b と $$a\wedge b$$a\wedge b が存在そんざいするとき、$$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le) を束そくlatticeという。

上界じょうかいupper boundと最小上界さいしょうじょうかいleast upper bound、下界かかいlower boundと最大下界さいだいかかいgreatest lower boundを区別くべつする。候補こうほが複数ふくすうあるとき、その中なかで順序じゅんじょに関かんして最良さいりょうのものが結むすびや交まじわりである。

3方針ほうしん

束そくlatticeを判定はんていするときは、単たんに上界じょうかいupper boundや下界かかいlower boundが存在そんざいするかだけを見みない。必要ひつようなのは、上界じょうかいupper boundの中なかの最小元さいしょうげんleast elementと、下界かかいlower boundの中なかの最大元さいだいげんgreatest elementである。

この違ちがいは重要じゅうようである。上界じょうかいupper boundが複数ふくすう存在そんざいしても、その中なかで最小さいしょうのものが存在そんざいしない場合ばあいがある。その場合ばあい、結むすびjoinは存在そんざいしない。

計算けいさんでは、まず共通きょうつうの上うえにある元げんelement、または共通きょうつうの下したにある元げんelementを集あつめる。次つぎに、その集合しゅうごうの中なかで順序じゅんじょに関かんして最小さいしょうまたは最大さいだいのものを選えらぶ。

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

束そくlatticeは、「合流ごうりゅう」と「共通部分きょうつうぶぶん」が常つねに取とれる半順序集合はんじゅんじょしゅうごうpartially ordered setである。包含順序ほうがんじゅんじょinclusion orderで考かんがえると、2 つの集合しゅうごうset $$B,C$$B,C の結むすびjoinは $$B\cup C$$B\cup C であり、交まじわりmeetは $$B\cap C$$B\cap C である。

なぜなら、$$B\cup C$$B\cup C は $$B$$B と $$C$$C の両方りょうほうを含ふくむ集合しゅうごうsetの内うち最小さいしょうであり、$$B\cap C$$B\cap C は $$B$$B と $$C$$C の両方りょうほうに含ふくまれる集合しゅうごうsetの内うち最大さいだいだからである。

有限半順序集合ゆうげんはんじゅんじょしゅうごうfinite partially ordered setのHasse図ずHasse diagramでは、結むすびjoinは 2 元げんの共通上界きょうつうじょうかいの内うち最小さいしょうの元げんであり、図ずでは順序じゅんじょに関かんして共通きょうつうの上側うえがわにあるもののうち最もっとも低ひくい元げんelementである。交まじわりmeetは共通下界きょうつうかかいの内うち最大さいだいの元げんであり、図ずでは順序じゅんじょに関かんして共通きょうつうの下側したがわにあるもののうち最もっとも高たかい元げんである。共通上界きょうつうじょうかいの集合しゅうごうに最小元さいしょうげんがないか、共通下界きょうつうかかいの集合しゅうごうに最大元さいだいげんがなければ、その組くみの結むすびまたは交まじわりは存在そんざいしない。

5代表例だいひょうれい

5.11. べき集合しゅうごうpower setは束そくlatticeである

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) を包含ほうがんinclusion $$\subseteq$$\subseteq で順序じゅんじょづける。このとき、任意にんいの $$B,C\subseteq A$$B,C\subseteq A について

である。したがって $$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A),\subseteq )$$(\mathcal P(A),\subseteq) は束そくlatticeである。

さらに $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing は最小元さいしょうげんleast element、$$A$$A は最大元さいだいげんgreatest elementである。この束そくlatticeはブール束そくBoolean latticeの基本例きほんれいである。

5.22. 正せいの整数せいすうintegerの整除順序せいじょじゅんじょdivisibility order

正せいの整数せいすうintegerで $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b を「$$a$$a が $$b$$b を割わり切きる」と定義ていぎする。この順序じゅんじょでは、$$a\vee b$$a\vee b は最小公倍数さいしょうこうばいすうleast common multiple、$$a\wedge b$$a\wedge b は最大公約数さいだいこうやくすうgreatest common divisorである。

たとえば $$6$$6 と $$10$$10 について、上界じょうかいupper boundは 6 と 10 の公倍数こうばいすうであり、その最小さいしょうは $$30$$30 である。したがって $$6\vee 10=30$$6\vee10=30 である。下界かかいlower boundは 6 と 10 の公約数こうやくすうであり、その最大さいだいは $$2$$2 である。したがって $$6\wedge 10=2$$6\wedge10=2 である。

整除順序せいじょじゅんじょdivisibility orderでは、上うえにあるとは「倍数ばいすうである」ことを意味いみする。したがって結むすびjoinは最小公倍数さいしょうこうばいすうleast common multiple、交まじわりmeetは最大公約数さいだいこうやくすうgreatest common divisorになり、通常つうじょうの大小だいしょうとは別べつの判断はんだんになる。

6例題れいだい：包含順序ほうがんじゅんじょinclusion orderで結むすびjoinと交まじわりmeetを求もとめる

6.1問題もんだい

$$A=\{1,2,3\}$$A=\{1,2,3\}、$$B=\{1,2\}$$B=\{1,2\}、$$C=\{2,3\}$$C=\{2,3\} とする。$$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A),\subseteq )$$(\mathcal P(A),\subseteq) における $$B\vee C$$B\vee C と $$B\wedge C$$B\wedge C を求もとめよ。

6.2解説かいせつ

包含順序ほうがんじゅんじょinclusion orderでは、結むすびjoinは和集合わしゅうごうunionである。したがって

である。これは $$B$$B と $$C$$C の両方りょうほうを含ふくむ集合しゅうごうsetの内うち最小さいしょうである。

また、交まじわりmeetは共通部分きょうつうぶぶんintersectionである。したがって

である。これは $$B$$B と $$C$$C の両方りょうほうに含ふくまれる集合しゅうごうsetの内うち最大さいだいである。

この例れいは、束そくlatticeの抽象的ちゅうしょうてきabstractな定義ていぎが、集合演算しゅうごうえんざんset operationの $$\cup$$\cup と $$\cap$$\cap に対応たいおうすることを確認かくにんしている。

7変かわるものと保存ほぞんされるもの

順序同型じゅんじょどうけいorder isomorphismは比較ひかくを保たもつため、結むすびjoinや交まじわりmeetが存在そんざいするなら、その対応先たいおうさきも同おなじ役割やくわりを持もつ。保存ほぞんされるのは数値すうちではなく、順序じゅんじょで定さだまる最良性さいりょうせいである。

8見分みわけ方かた

• 任意にんいの 2 元げんに最小上界さいしょうじょうかいleast upper boundと最大下界さいだいかかいgreatest lower boundがあるなら、束そくlatticeである。
• 包含順序ほうがんじゅんじょinclusion order では、結むすびjoinは $$\cup$$\cup、交まじわりmeetは $$\cap$$\cap である。
• 整除順序せいじょじゅんじょdivisibility order では、結むすびjoinは最小公倍数さいしょうこうばいすうleast common multiple、交まじわりmeetは最大公約数さいだいこうやくすうgreatest common divisorである。
• 全順序関係ぜんじゅんじょかんけいtotal order では、2 元げんの大おおきい方ほうが結むすびjoin、小ちいさい方ほうが交まじわりmeetになる。

束そくかどうかは、代表例だいひょうれいだけでなく任意にんいの 2 元げんについて確認かくにんする。一組ひとくみでも結むすびjoinまたは交まじわりmeetが存在そんざいしなければ、その半順序集合はんじゅんじょしゅうごうは束そくではない。

9証明しょうめい補足ほそく：meet と join の単調性たんちょうせい

束そくlattice では、$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b なら

が成立せいりつする。これは meet と join が順序じゅんじょを保存ほぞんするという意味いみである。

まず meet を証明しょうめいする。$$a\wedge c$$a\wedge c は $$a$$a と $$c$$c の下界かかいである。したがって $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}a$$a\wedge c\le a かつ $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}c$$a\wedge c\le c である。$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b なので $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\wedge c\le b も従したがう。よって $$a\wedge c$$a\wedge c は $$b$$b と $$c$$c の下界かかいである。$$b\wedge c$$b\wedge c は $$b$$b と $$c$$c の最大下界さいだいかかいなので、$$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b\wedge c$$a\wedge c\le b\wedge c である。

join も双対そうついに証明しょうめいできる。$$b\vee c$$b\vee c は $$b$$b と $$c$$c の上界じょうかいであり、$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$a\le b\le b\vee c、$$c\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$c\le b\vee c だから、$$b\vee c$$b\vee c は $$a$$a と $$c$$c の上界じょうかいである。$$a\vee c$$a\vee c は $$a$$a と $$c$$c の最小上界さいしょうじょうかいなので、$$a\vee c\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$a\vee c\le b\vee c である。

10演習えんしゅうリンク

11関連かんれんリンク