束そくlatticeの基本きほん

date2026-07-14document_iddoc_428cd25d922c840eb6fde4f98fbe394ddescription束を、任意の二元に最小上界（結び）と最大下界（交わり）が存在する半順序集合として導入し、包含順序と整除順序で説明する講義である。prerequisites半順序関係と全順序関係 / Hasse図と極大元・極小元 / 順序同型と整列順序 / 集合演算と包含関係 / べき集合の基本type講義content_typelecturestatusactive

mathdiscrete-mathlatticelecture

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, [PARSE ERROR: Undefined("Command(\"le\")")])$ に対たいして、 $a, b \in P$ の上界じょうかいupper boundとは、 $a [PARSE ERROR: Undefined("Command(\"le\")")] u$ かつ $b [PARSE ERROR: Undefined("Command(\"le\")")] u$ を満みたす $u \in P$ である。下界かかいlower boundとは、 $ℓ [PARSE ERROR: Undefined("Command(\"le\")")] a$ かつ $ℓ [PARSE ERROR: Undefined("Command(\"le\")")] b$ を満みたす $ℓ \in P$ である。

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

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

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

2Terms and definitions

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

a [PARSE ERROR: Undefined("Command(\"le\")")] u, b [PARSE ERROR: Undefined("Command(\"le\")")] u .

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

a \lor b .

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

l [PARSE ERROR: Undefined("Command(\"le\")")] a, l [PARSE ERROR: Undefined("Command(\"le\")")] b .

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

a \land b .

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を集あつめる。次つぎに、その集合しゅうごうの中なかで順序じゅんじょに関かんして最小さいしょうまたは最大さいだいのものを選えらぶ。

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

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$ , 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.

The existence of several upper bounds is not enough: their set may have no least element, in which case the join does not exist. In a calculation, first collect all common upper or lower bounds, and then look for the least or greatest element within that set.

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

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

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

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

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

4Intuitive explanation

The join結むすび $a \lor b$ is the smallest element that is still above both $a$ and $b$ . The meet交まじわり $a \land b$ is the largest element that is still below both $a$ and $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.

In a Hasse diagramHasse図ず of a finite partially ordered set有限半順序集合ゆうげんはんじゅんじょしゅうごう, the join is the least element among the common upper bounds—the lowest common element above the pair—and the meet is the greatest element among the common lower bounds—the highest common element below it. If either element is missing for even one pair, the poset is not a lattice.

5代表例だいひょうれい

5Examples

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

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

B \lor C = B \cup C, B \land C = B \cap C

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

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

data/lecture/math/discrete-math/power-set-basics.lecture.n.md

5.11. Powersets ordered by inclusion

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

B \lor C = B \cup C, B \land C = B \cap C .

Thus $([PARSE ERROR: Undefined("Command(\"mathcal\")")] P (A), \subseteq)$ is a lattice束そく. Moreover, $[PARSE ERROR: Undefined("Command(\"varnothing\")")]$ is the least element最小元さいしょうげん and $A$ is the greatest element最大元さいだいげん. This is a basic example of a Boolean lattice[ブール束].

data/lecture/math/discrete-math/power-set-basics.lecture.n.md

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

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

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

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

5.22. Positive integers ordered by divisibility

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

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

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

6Worked example: finding join and meet in inclusion order

6.1問題もんだい

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

6.1Problem

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

6.2解説かいせつ

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

B \lor C = B \cup C = {1, 2, 3}

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

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

B \land C = B \cap C = {2}

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

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

6.2Explanation

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

B \lor C = B \cup C = {1, 2, 3} .

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

The meet交まじわり is intersection. Therefore

B \land C = B \cap C = {2} .

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

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

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

視点してん	変かわるもの	保存ほぞんされるもの
半順序集合はんじゅんじょしゅうごうpartially ordered set を見みる	比較ひかくできない組くみを許ゆるす	反射性はんしゃせいreflexivity 、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivity
束そくlattice を見みる	任意にんいの 2 元げんに結むすびjoinと交まじわりmeetを要求ようきゅうする	半順序関係はんじゅんじょかんけいpartial order
ブール束そくBoolean latticeを見みる	補集合ほしゅうごうcomplement まで扱あつかう	和集合わしゅうごうunion と共通部分きょうつうぶぶんintersectionによる束そくlattice

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

7What changes and what is preserved

Viewpoint	What changes	What is preserved
Looking at a partially ordered set半順序集合はんじゅんじょしゅうごう	incomparable pairs are allowed	reflexivity反射性はんしゃせい, antisymmetry反対称性はんたいしょうせい, transitivity推移性すいいせい
Looking at a lattice束そく	every pair is required to have a join and a meet	the partial order半順序関係はんじゅんじょかんけい
Looking at a Boolean lattice[ブール束]	complements補集合ほしゅうごう are also considered	the lattice structure given by union and intersection

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$ 、交まじわりmeetは $\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$ and meet is $\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 [PARSE ERROR: Undefined("Command(\"le\")")] b$ なら

a \land c [PARSE ERROR: Undefined("Command(\"le\")")] b \land c, a \lor c [PARSE ERROR: Undefined("Command(\"le\")")] b \lor c

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

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

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

9Proof supplement: monotonicity of meet and join

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

a \land c [PARSE ERROR: Undefined("Command(\"le\")")] b \land c, a \lor c [PARSE ERROR: Undefined("Command(\"le\")")] b \lor c .

This means that meet and join preserve order.

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

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