束そくlatticeの基本きほん

Basics of lattices束そく

1導入どうにゅう

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

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

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

1Introduction

The central idea of a lattice束そく is that, in a partially ordered set半順序集合はんじゅんじょしゅうごう, any two elements元げん have a best common upper element and a best common lower element. These are called the join結むすび and the meet交まじわり.

In a total order全順序関係ぜんじゅんじょかんけい, the larger and smaller of two objects are determined immediately. In a partial order半順序関係はんじゅんじょかんけい, two objects may be incomparable. Even then, if there is a best candidate above both and a best candidate below both, a lattice束そく structure is present.

For a lattice束そく, every pair of elements must have both a join結むすび and a meet交まじわり. A partially ordered set is not automatically a lattice; one must check whether the best upper and lower bounds exist.

The words "larger" and "smaller" do not always mean ordinary numerical size. In an inclusion order包含順序ほうがんじゅんじょ they mean being a larger or smaller set, and in a divisibility order整除順序せいじょじゅんじょ they mean divisibility. Therefore the join and meet must always be read from the order being used.

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、または結むすびjoinとは、上界じょうかいupper boundの内うち最小さいしょうのものであり、$$a\vee b$$a\vee b と書かく。下限かげんgreatest lower bound、または交まじわり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を区別くべつする。候補こうほが複数ふくすうあるとき、その中なかで順序じゅんじょに関かんして最良さいりょうのものが結むすびや交まじわりである。

2Terms and definitions

Let $$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le) be a partially ordered set半順序集合はんじゅんじょしゅうごう. An upper bound上界じょうかい of $$a,b\in P$$a,b\in P is an element $$u\in P$$u\in P such that

A least upper bound最小上界さいしょうじょうかい of $$a$$a and $$b$$b is the smallest element among their upper bounds. It is called the join結むすび and is written

A lower bound下界かかい of $$a,b\in P$$a,b\in P is an element $$l\in P$$l\in P such that

A greatest lower bound最大下界さいだいかかい of $$a$$a and $$b$$b is the largest element among their lower bounds. It is called the meet交まじわり and is written

A partially ordered set is a lattice束そく if every pair of elements has both a join and a meet.

Distinguish an upper bound上界じょうかい from a least upper bound最小上界さいしょうじょうかい, and a lower bound下界かかい from a greatest lower bound最大下界さいだいかかい. When there are several candidates, the join or meet is the best one with respect to the order.

3方針ほうしん

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

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

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

3Strategy

To check whether a partially ordered set is a lattice束そく, do not look only for ordinary maximum and minimum. For every pair $$a,b$$a,b, check the set of common upper bounds and the set of common lower bounds. If the upper bounds have a least element and the lower bounds have a greatest element for every pair, the poset is a lattice.

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の内うち最大さいだいだからである。

Hasse図ずHasse diagramでは、結むすびjoinは 2 元げんの共通きょうつうの上側うえがわにあるもののうち最もっとも低ひくい元げんelementであり、交まじわりmeetは共通きょうつうの下側したがわにあるもののうち最もっとも高たかい元げんelementである。最良さいりょうの候補こうほが一意いちいに決きまらなければ、束そくの条件じょうけんは失敗しっぱいする。

4Intuitive explanation

The join結むすび $$a\vee b$$a\vee b is the smallest element that is still above both $$a$$a and $$b$$b. The meet交まじわり $$a\wedge b$$a\wedge b is the largest element that is still below both $$a$$a and $$b$$b.

For sets集合しゅうごう ordered by inclusion, "above" means "contains." Therefore the smallest set containing both sets is their union和集合わしゅうごう, and the largest set contained in both is their intersection共通部分きょうつうぶぶん. For positive integers整数せいすう ordered by divisibility, "above" means "is a multiple of," so join becomes least common multiple and meet becomes greatest common divisor.

5代表例だいひょうれい

5Examples

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.11. Powersets ordered by inclusion

For a set $$A$$A, the power set[べき集合] $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) is ordered by inclusion $$\subseteq$$\subseteq. For $$B,C\subseteq A$$B,C\subseteq A,

Thus $$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A),\subseteq )$$(\mathcal P(A),\subseteq) is a lattice束そく. Moreover, $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing is the least element最小元さいしょうげん and $$A$$A is the greatest element最大元さいだいげん. This is a basic example of a 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になり、通常つうじょうの大小だいしょうとは別べつの判断はんだんになる。

5.22. Positive integers ordered by divisibility

For positive integers, define $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b to mean that $$a$$a divides $$b$$b. In this order, $$a\vee b$$a\vee b is the least common multiple最小公倍数さいしょうこうばいすう, and $$a\wedge b$$a\wedge b is the greatest common divisor最大公約数さいだいこうやくすう.

For example, for $$6$$6 and $$10$$10, the upper bounds are common multiples of 6 and 10, and the least one is $$30$$30. Hence $$6\vee 10=30$$6\vee10=30. The lower bounds are common divisors of 6 and 10, and the greatest one is $$2$$2. Hence $$6\wedge 10=2$$6\wedge10=2.

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

6Worked example: finding join and meet in inclusion order

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.1Problem

Let $$A=\{1,2,3\}$$A=\{1,2,3\}, $$B=\{1,2\}$$B=\{1,2\}, and $$C=\{2,3\}$$C=\{2,3\}. Find $$B\vee C$$B\vee C and $$B\wedge C$$B\wedge C in $$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A),\subseteq )$$(\mathcal P(A),\subseteq).

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 に対応たいおうすることを確認かくにんしている。

6.2Explanation

In the inclusion order包含順序ほうがんじゅんじょ, the join結むすび is union. Therefore

This is the smallest set containing both $$B$$B and $$C$$C.

The meet交まじわり is intersection. Therefore

This is the largest set contained in both $$B$$B and $$C$$C.

This example confirms that the abstract definition of a lattice束そく corresponds to the set operations $$\cup$$\cup and $$\cap$$\cap in the powerset ordered by inclusion.

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

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

7What changes and what is preserved

An order isomorphism順序同型じゅんじょどうけい preserves comparison, so if a join結むすび or meet交まじわり exists, its corresponding element has the same role on the other side. What is preserved is not a numerical value, but the optimality determined by the order.

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が存在そんざいしなければ、その半順序集合はんじゅんじょしゅうごうは束そくではない。

8Recognition criteria

• If every pair has a least upper bound最小上界さいしょうじょうかい and a greatest lower bound最大下界さいだいかかい, the poset is a lattice束そく.
• In the inclusion order包含順序ほうがんじゅんじょ, join is $$\cup$$\cup and meet is $$\cap$$\cap.
• In the divisibility order整除順序せいじょじゅんじょ, join is least common multiple and meet is greatest common divisor.
• In a total order全順序関係ぜんじゅんじょかんけい, the larger of two elements is their join and the smaller is their meet.

To decide whether a poset is a lattice束そく, check arbitrary pairs, not only representative examples. If even one pair lacks a join結むすび or a meet交まじわり, that partially ordered set is not a lattice.

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 である。

9Proof supplement: monotonicity of meet and join

In a lattice束そく, if $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b, then

This means that meet and join preserve order.

First prove the statement for meet. The element $$a\wedge c$$a\wedge c is a lower bound of $$a$$a and $$c$$c, so $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}a$$a\wedge c\le a and $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}c$$a\wedge c\le c. Since $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b, we also have $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\wedge c\le b. Hence $$a\wedge c$$a\wedge c is a lower bound of $$b$$b and $$c$$c. Because $$b\wedge c$$b\wedge c is the greatest lower bound of $$b$$b and $$c$$c, it follows that $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b\wedge c$$a\wedge c\le b\wedge c.

The join statement is proved dually双対的そうついてき. The element $$b\vee c$$b\vee c is an upper bound of $$b$$b and $$c$$c. Since $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$a\le b\le b\vee c and $$c\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$c\le b\vee c, it is also an upper bound of $$a$$a and $$c$$c. Because $$a\vee c$$a\vee c is the least upper bound of $$a$$a and $$c$$c, we get $$a\vee c\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$a\vee c\le b\vee c.

10演習えんしゅうリンク

10Exercise links

11関連かんれんリンク

11Related links