😊

束論入門

に公開
math
束論
tech

はじめに

はじめまして。記事を開いていただきありがとうございます。
これから束論の基礎的な事項について解説をしていこうと思います。

実はもともとは他の記事の執筆中に前提知識の紹介として書いていたのですが、だいぶ長くなってしまったので切り出して記事にすることにしました。
そのため、特に話のオチもなく、書こうとしていたことをつらつらと並べていきます。
（正直全くの初学者向けというよりは、定義程度は確認したことあるけど詳しくは知らないみたいな方向けかもしれないです）

また、書こうとしていた内容に必要な知識 + \alphaしか書いていないため、網羅性も特にありません。
ただし、初学時には見落としやすい細かいポイントなどは出来るだけ抑えるように心がけました。

束論のおすすめの教科書は"Introduction to Lattices and Order" (Davey & Priestley, 2002)です。
コンピュータサイエンスへの応用も視野に入っており、位相空間の話が少ないことを除いては非常に優れた教科書だと思っております。

よろしくお願いします。

記法

  • poset Pの部分集合X\subseteq Pの上限・下限をそれぞれ\vee X, \wedge Xと書く
    • \vee\{x, y\}などはx\vee yと書く
    • 有向集合のみを定義域に取る上限（有向上限と呼ぶ）を\sqcup Xと書く
  • poset Pの部分集合X\subseteq P, 元a\in Pに対し、X\le aは\forall x\in X, x\le aを意味する
  • poset Pの有向部分集合をD\subseteq_\mathrm{dir} P、有限部分集合をX\subseteq_\mathrm{fin} Pと書く
  • 集合Aの冪集合を\mathcal{P}(A)と書く
    • 特に、有限集合のみの冪集合を\mathcal{P}_\mathrm{fin}(A)\coloneqq\{X\mid X\subseteq_\mathrm{fin} A\}と書く

束論のおさらい

束論の基本をおさらいします。

束の定義

定義1: 半束、束、完備束

(P, \le)を半順序集合 (partially ordered set; poset) とします。

\begin{array}{llll} \text{1. }P\text{が半束} & \iff & \forall X\in\mathcal{P}_\mathrm{fin}(P)\setminus\{\emptyset\}, & \vee X\text{ exists}.\\ \text{2. }P\text{が束} & \iff & \forall X\in\mathcal{P}_\mathrm{fin}(P)\setminus\{\emptyset\}, & \vee X, \wedge X\text{ exist}.\\ \text{3. }P\text{が完備束} & \iff & \forall X\in\mathcal{P}(P)\setminus\{\emptyset\}, & \vee X, \wedge X\text{ exist}.\\ \end{array}

束と完備束の違いは無限集合の上限・下限を取れるかどうかにあります。

空集合も定義に入れると？

定義においてXとして空集合を許すとどうなるのでしょうか。

半束・束の場合

上限・下限の定理より、\vee\emptysetと\wedge\emptysetはそれぞれ最小元と最大元になります。
すなわち、Xとして空集合も許す定義にすると束は必ず最大元及び最小元を持つことになります。

そのような立場を取るなら空集合を許してもよいのですが、本記事では一般には束は最大元・最小元を持たない立場を取ります。
このような立場からすると、最大元及び最小元を持つ束は有界束と呼ばれます。
（非空な有限束なら最大元\vee Pと最小元\wedge Pを必ず持ちます）

完備束の場合

本記事の定義でも非空な完備束は最大元\vee Pと最小元\wedge Pを持ちます。
つまり、完備束においてXとして空集合を許すかどうかは空集合を完備束とするかの違いとなります。
完備束のみ空集合を許容しない立場が一般的に思われますが、個人の好みから本記事ではposetも束も完備束も空集合を許容する立場を取ります。
ただし、有向集合のみ空集合を許容しません（どうして？！）

また、順序と上限・下限操作の間には明らかに次のような関係が成り立ちます。

命題2: 順序と上限・下限の関係

束(L, \le)上の元x, y\in Lに対し、次が成り立つ。

  1. x\le y\iff x\vee y = y
  2. x\le y\iff x\wedge y = x

この関係を応用することで、束の代数的定義、すなわち、等式を用いた定義を得ることができます。

定理3: 束の代数的定義

集合L及び二つの二項演算子\vee, \wedge\subseteq L\times Lの組(L, \vee, \wedge)が次の条件及び\veeと\wedgeを入れ替えた条件を満たすとする。

（可換律）\forall x, y\in L, x\vee y = y\vee x
（結合律）\forall x, y, z\in L, (x\vee y)\vee z = x\vee (y\vee z)
（吸収律）\forall x, y\in L, x\vee (x\wedge y) = x

そのとき、束(L, \le)について次が言える。

  1. 束Lの上限・下限は三条件を満たす
  2. 三条件を満たす(L, \vee, \wedge)に対し、x\le y\iff x\vee y = yと定義した(L, \le)は束となり、上限・下限は\veeと\wedgeに一致する。
べき等律について

束の代数的な定義において次のべき等律を含めた四条件を定義とすることもあります。

\forall x\in L, x\vee x = x

しかし、べき等律は吸収律から導出できるため実は不要な条件です。（最後の等式はy=x\vee xとして再び吸収律を用いた）

x\vee x = x\vee (x\wedge (x\vee x)) = x

ただし、可換律、結合律、べき等律を満たす(L, \vee)は半束と等価になります。
束とは吸収律を満たす半束であるという捉え方においては、べき等律を定義に含めることは非常に自然な考え方ですが、本記事では無駄のないの定義を取りました。

つまり、束は等式を用いて代数的な定義ができるということになります。
ちなみに、完備束は代数的な定義を持ちません。[1]

定義4: 部分束

束(L, \le)のL'\subseteq Lへの制限のposet (L', \le)は次を満たすときLの部分束と呼ぶ。

  1. (L', \le')は束である
  2. L'での上限・下限はLでの上限・下限に一致する

例：条件1を満たすが部分束にならない束
以下の束LにおいてL'=\{a, b, c, e\}\subseteq Lは束となります。
しかし、b, cのL'上の下限はeですが、L上の下限はdです。

ところで完備束の定義として\vee X, \wedge X両方が存在することを要請しましたが、実は（空集合を許せば）片側だけで十分です。

命題5: 完備束の同値な定義

束(L, \le)が次の条件を満たすとき、Lは完備束である。（X\in\mathcal{P}(L)\setminus\{\emptyset\}でないことに注意）

L=\emptyset\text{ or }\forall X\in\mathcal{P}(L), \vee X \text{ exists}
証明（考え方が大事）

L=\emptysetならLは完備。L\not=\emptysetとして、任意のX\in\mathcal{P}(L)\setminus\{\emptyset\}が下限を持つことを示せばよい。

そこで、\mathrm{Lb}(X)=\{y\in L\mid y\le X\}とすると、\vee\mathrm{Lb}(X)がXの下限（=最大下界）になることを示す。

  1. 下界性（\vee\mathrm{Lb}(X)\le X）
    \forall x\in X, \vee\mathrm{Lb}(X)\le xを示せばよい。
    xは\mathrm{Lb}(X)の定義より\mathrm{Lb}(X)の上界になるが、\vee\mathrm{Lb}(X)は\mathrm{Lb}(X)の最小上界であるため、\vee\mathrm{Lb}(X)\le xとなる。

  2. 最大性（\forall y\in\mathrm{Lb}(X), y\le \vee\mathrm{Lb}(X)）
    上限の定義より明らか。

\square

もちろん任意の下限が存在する場合でも同様に任意の上限が存在することを示せます。

命題5の罠

位相空間Xの開集合\mathcal{O}(X)は包含関係により束となります。
実際、開集合O_1, O_2\in\mathcal{O}(X)に対し、O_1\cup O_2, O_1\cap O_2はともに開集合なので上限・下限が存在します。

ところで、開集合の無限和も開集合でした。すると、定理3より\mathcal{O}(X)は完備束ゆえ、任意個の開集合の下限が存在します。

しかし、位相空間の定義より無限個の開集合の共通部分は開集合とは限らなかったはずです。なにが問題だったのでしょうか？

一言で言えば、（代数的定義を持たないものの）完備束を(L, \bigvee, \bigwedge)という構造付き集合として見た際の\mathcal{O}(X)の下限操作は共通部分を取る操作ではないからです。
具体的には、\wedge\mathcal{O}\coloneqq\mathrm{int}(\bigcap\mathcal O)（\bigcap\mathcal Oの内部）が下限操作になります。
（もちろん下限操作の定義域を有限集合に限れば共通部分を取る操作に一致します）

言い方を変えれば、ただの束としての\mathcal{O}(X)と完備束としての\mathcal{O}(X)はposetとして（あるいは束として）は全く一致していますが、(L, \bigvee, \bigwedge)なる構造付き集合としては全く異なるものです。
（このような事情から、本記事では完備束の定義には任意の上限のみならず任意の下限操作も明示して定義することを好みました）

このように束はposetとして捉えるだけでは不十分なこともあり、逆に代数として捉えるだけでも完備束を定義できないなど、束の性質を考える時は順序的・代数的な双方の視点を持つ事が非常に重要です。
（ただし、私は束を代数だと思ったことは人生で一度もありません。）

また、完備束は不動点による面白い特徴づけを持ちます。
poset P上の関数f\colon P\to Pに対し、f(a)=aなる元a\in Pをfの不動点といい、f(a)\le aとなる元a\in Pをfの前不動点といいます。

命題6: Knaster-Tarskiの不動点定理とその逆

非空な束Lに対し、L上の単調写像の集合を[L\overset{m}{\to}L]とすると、

L\text{ is complete}\iff \forall f\in[L\overset{m}{\to}L], f\text{ has a least fixed point}

（どちらも自力で思いつくのは困難な非常にトリッキーな証明でとても面白いです）

完備ならば不動点を持つ

L\not=\emptysetより（空集合含め）任意の上限・下限が存在する。
そこで、「\wedge\{x\in L\mid f(x)\le x\}はfの最小前不動点であり、かつfの不動点となる（ゆえに最小不動点である）」という命題を示す。
（これはKnaster-Tarskiの不動点定理と呼ばれる非常に有名な定理）

fの前不動点の集合を\mathrm{Pre}(f)とすると、

\forall x\in\mathrm{Pre}(f), \wedge\mathrm{Pre}(f)\le x

fの単調性及びxが前不動点より、

\forall x\in\mathrm{Pre}(f), f(\wedge\mathrm{Pre}(f))\le f(x)\le x

故に、f(\wedge\mathrm{Pre}(f))\le \wedge\mathrm{Pre}(f)となり、確かに\wedge\mathrm{Pre}(f)はfの前不動点であり、\wedgeの定義より最小前不動点となる。

また、逆側の不等式も示して\wedge\mathrm{Pre}(f)が不動点となることも証明する。
fの単調性より、

f(f(\wedge\mathrm{Pre}(f)))\le f(\wedge\mathrm{Pre}(f))

よって、f(\wedge\mathrm{Pre}(f))は前不動点であり、\wedge\mathrm{Pre}(f)は最小前不動点だったので、

\wedge\mathrm{Pre}(f)\le f(\wedge\mathrm{Pre}(f))
不動点を持つならば完備（ACあるよ）

こちらは証明のスケッチのみ書きます。
詳細は"Chain-complete posets and directed sets with applications" (Markowsky, 1976)を参照してください。

まず、poset Pがchain-complete（任意の非空なchainが上限を持つ）であり、かつ有界結び半束（任意の有限集合が上限を持つ）ならPは（非空な）完備束となります。（COROLLARY 1.2）

今、恒等写像\mathrm{id}(x)=x\colon L\to Lも単調写像ゆえ仮定より最小不動点を持つため、Lは最小元を持ちます。
ゆえに、Lは有界結び半束であるため、あとはPがchain-completeであることを示せばよいです。（THEOREM 11の(b)\implies(a)）

非空なchain C\subseteq Lは常にwell-orderedなcofinal subset C'\subseteq Cを持つ（超限帰納法で構成可）ため、Cが上限を持つことを示すにあたってはCを常にwell-orderedだと仮定してよいです。\mathrm{Ub}(C)をCの上界集合とし、f\colon L\to Lを次のように定義します。
（ただし、\{y\in C\mid y\not\le x\}\not=\emptysetゆえCのwell-orderednessより最小元を持ちます）

f(x)=\left\{\begin{array}{ll}x & \text{ if }x\in\mathrm{Ub}(C) \\ \min\{y\in C\mid y\not\le x\} & \text{ if }x\not\in\mathrm{Ub}(C)\end{array}\right.

このとき、fは単調写像となります。
（x\le yについてx, y\not\in\mathrm{Ub}(C)のケースなら（一般に）\forall z\in C, z\not\le y\implies z\not\le xゆえ\{z\in C\mid z\not\le y\}\subseteq\{z\in C\mid z\not\le x\}となり、f(x)\le f(y)が成り立ちます。他のケース（x, y\in\mathrm{Ub}(C)とx\not\in\mathrm{Ub}(C), y\in\mathrm{Ub}(C)）は明らかです）

今、\mathrm{Fix}(f)\coloneqq\{x\in L\mid f(x)=x\}とします。
このとき、簡単な観察から\forall x\in L, x\in\mathrm{Fix}(f)\iff x\in\mathrm{Ub}(C)となり、仮定よりfは最小不動点を持つため、

\min\mathrm{Fix}(f)=\min\mathrm{Ub}(C)=\vee C

\square

分配束

掛け算と足し算の分配律x\cdot (y+z) = x\cdot y + x\cdot zのような性質をもつ束を分配束といいます。

定義7: 分配束

次の分配律を満たす束(L, \le)を分配束と呼ぶ。

\forall x, y, z\in L, x\wedge (y\vee z) = (x\wedge y)\vee (x\wedge z)

実は逆側の分配律も成り立ちます。

命題8: 逆側の分配律

分配束(L, \le)は次の逆側の分配律も満たす。（もちろんこっちを定義にしても良い）

\forall x, y, z\in L, x\vee (y\wedge z) = (x\vee y)\wedge (x\vee z)
証明
\begin{array}{lll} & (x\vee y)\wedge(x\vee z) & \\ = & ((x\vee y)\wedge x)\vee((x\vee y)\wedge z) & (\because\text{分配律})\\ = & x\vee((z\wedge x)\vee(y\wedge z)) & (\because\text{吸収律・分配律})\\ = & (x\vee(z\wedge x))\vee(y\wedge z) & (\because\text{結合律})\\ = & x\vee(y\wedge z) & (\because\text{吸収律})\\ \end{array}

\square

無限の場合の補足

無限の場合は事情が少し複雑になります。まず、素直に分配律を無限に拡張したものを考えます。

次を満たす非空な完備束を完全分配束 (completely distributive lattice)[2]と呼びます。

\forall I\text{: set}, \forall J\colon I\to\mathcal{P}(L), \forall x\colon\coprod_{i\in I}J(i)\to L,

\bigvee_{i\in I}\bigwedge_{j\in J(i)}x(i, j)=\bigwedge_{f\in\prod_{i\in I}J(i)}\bigvee_{i\in I}x(i, f(i))

（f\in\prod_{i\in I}J(i)はいわゆる選択公理により存在が保証される選択関数です）
完全分配律は分配律と同様に自己双対的です。すなわち、\bigveeと\bigwedgeを入れ替えたものも成り立ちます。

また、次を満たす非空な完備束を無限分配束 (infinitely distributive lattice)と呼びます。

\forall x\in L, \forall Y\subseteq L, x\vee(\bigwedge Y)=\bigwedge\{x\vee y\mid y\in Y\}

こちらは定義もシンプルで直感的に理解しやすいかもしれません。
しかし、無限分配性は自己双対的ではありません。すなわち、無限分配律から次の余無限分配律は導けません。

\forall x\in L, \forall Y\subseteq L, x\wedge(\bigvee Y)=\bigvee\{x\wedge y\mid y\in Y\}

しかし、完全分配束は「無限分配律と余無限分配律どちらも満たす束」と同値になります。
\impliesは明らかで、\impliedbyはざっくり言えば「全体のsup = (有限部分集合のsup全体)のsup」と変形することにより片方のみ無限の分配性に帰着でき、無限分配律を適用することができます。つまり、

\bigwedge_{i\in I}\bigvee_{j\in J(i)}x(i, j)\le\bigwedge_{i\in F}\bigvee_{j\in J(i)}x(i, j)\text{ for all }F\subseteq_\mathrm{fin}I

ゆえに

\begin{array}{ll} & \bigwedge_{i\in I}\bigvee_{j\in J(i)}x(i, j)\\ \le & \bigvee_{F\subseteq_\mathrm{fin}I}\bigwedge_{i\in F}\bigvee_{j\in J(i)}x(i, j) \\ = & \bigvee_{F\subseteq_\mathrm{fin}I}\bigvee_{f\in\prod_{i\in F}J(i)}\bigwedge_{i\in F}x(i, f(j)) \\ = & \bigvee_{f\in\prod_{i\in I}J(i)}\bigwedge_{i\in I}x(i, f(i))\end{array}

（逆も同様だがもう少し複雑）

分配束はあまりに重要すぎる束であり、紹介すべき性質が非常に多いです。
pointless topologyにおけるStone双対の話や、離散数学におけるBirkhoffの表現定理など、分配束は非常に多くの分野で重要な役割を果たします。

本記事では分配束と既約元のとある関係について焦点を当て紹介をするとします。

まず、分配束の非常に重要な特徴づけ[3]を紹介します。

定理9: 分配束の特徴づけ

次の二つの束をそれぞれ\mathrm{M}_3と\mathrm{N}_5とする。（それぞれdiamond lattice, pentagon latticeと呼ばれる）
束Lが分配束であることと、Lが\mathrm{M}_3, \mathrm{N}_5（と同型な束）のどちらも部分束として含まないことは同値である。

図1. 束\mathit{M}_3

図2. 束\mathit{N}_5

それでは分配束クイズをしましょう。
\mathrm{M}_3か\mathrm{N}_5を部分束として含む束は分配束ではないことを利用して、分配束であるかどうかを判定してください。

  • 片方でも含む\implies分配束ではない
  • 両方含まない\implies分配束

例：\mathrm{M}_3, \mathrm{N}_5を探せ！分配束クイズ！（全５問）

  1. 次の束は分配束か？
答え

A. 分配束ではないです
どう見ても\mathrm{M}_3を含んでいますね。

  1. 次の束は分配束か？
答え

A. 分配束ではないです
\mathrm{N}_5を見落としてしまった方は半順序の推移性から頂点dとaの間にもつながりがあることを見落としているかもしれません。
L=\{a, b, d, e, f\}は\mathrm{N}_5に同型な部分束となります。

  1. 次の束は分配束か？
答え

A. 分配束です
この束自体が\mathrm{N}_5と同じ形では？と思った方もいるかもしれませんが、\mathrm{N}_5では頂点bとcの間に繋がりはないため、この束は\mathrm{N}_5とそもそも同型ではありません。
つまり、抜き出したときに（推移性による辺も含めて）余分な辺が入っていたら同型にはなりません。

  1. 次の束は分配束か？
答え

A. 分配束です
今度こそL=\{a, d, e, f, i\}が\mathrm{M}_3と同型だから分配束ではないと思った方もいるかもしれません。
確かに、そのLは\mathrm{M}_3と同型な束です。しかし、実は定理7は\mathrm{M}_3や\mathrm{N}_5を部分束として含まないことを主張していることを忘れてはいけません。

頂点d, eのLにおける上限はaですが、問題の束における上限はbとなり上限が一致しません。

  1. （最終問題）次の束は分配束か？（正解すれば分配束鑑定士の資格を与えます）
答え

A. 分配束ではないです
初見で気づけた人は普通にすごいと思います。
先程と同様に、確かにL=\{a, d, e, f, g\}は\mathrm{M}_3と同型ですが部分束として含んではいません。

しかし、よく見たらL'=\{a, b, d, f, g\}が普通に\mathrm{N}_5と同型な部分束です。
（ちなみにこの束は\mathrm{S}_7という名前がついている有名な束で、セミモジュラーだがモジュラーではない束の代表例です）

分配束と既約元表現

では、皆さん分配束鑑定士になったところで、続いて既約元・素元の言葉を用いた分配束のもう一つの特徴づけを紹介します。

定義10: 既約元、素元

束Lの元 x\in Lについて、

  1. xが既約元\iff\forall Y\in\mathcal{P}_\mathrm{fin}(L), x=\vee Y\implies\exists y\in Y, x= y
  2. xが素元　\iff\forall Y\in\mathcal{P}_\mathrm{fin}(L), x\le\vee Y\implies\exists y\in Y, x\le y

（1の結論部はx\in Yと同値）

そこで、Lの既約元の集合をL^\mathrm{ir}、素元の集合をL^\mathrm{pr}とします。

例：整除関係による束
自然数の集合\mathbb{N}に整除関係による半順序（x\le y\iff xはyを割り切る）を入れたとき、上限・下限はそれぞれ最大公約数・最小公倍数で与えられ束となります。（ちなみに1を最小元、0を最大元と考えます）
その時、素数の累乗が（0でない）素元に対応します。

ちなみに、有限束では既約元は分かりやすい特徴づけが存在します。[4]

命題11: 有限束における既約元

poset (P, \le)上の元a, b\in Pに対し、被覆関係\mathord{<:}\subseteq P\times Pを次で定義する。このときaはbの直下の元、bはaの直上の元と呼び、また、bはaを被覆するとも呼ぶ。

a<:b\iff a<b\text{ and }\{c\in P\mid a<c<b\}=\emptyset

そのとき、有限束（=台集合が有限集合である束）Lの元x\in Lについて、xが既約元であることと、xの直下の元が一意に存在することは同値である。
（証明は省略しますが高さに関する帰納法で証明します。本当はもう少し緩い条件 i. e. 任意の区間が無限鎖を持たないかつ高さ有限の束でもこの事実は示せます）

ところで、素元は常に既約元になります。
（x=\vee Yとすれば、\exists y\in Y, (y\le \vee Y=)x\le yゆえ、x=y\in Y）

ただし、既約元は必ずしも素元とは限りません。
しかし、驚くことに既約元と素元が一致することとLが分配束になることは同値となります。

定理12: 既約元・素元による分配束の特徴づけ

束Lが分配束であることと、既約元と素元が一致することは同値である。

証明

  1. 分配束ならば素元=既約元
    任意の既約元x\in Lについて、xが素元であることを示す。
    Y\subseteq_\mathrm{fin}Lに対し、x\le\vee Yとする。
    その時、分配性よりx=x\wedge\vee Y=\vee\{x\wedge y\mid y\in Y\}となる（Y=\emptysetでも成り立つことに注意）が、xの既約性よりx\in\{x\wedge y\mid y\in Y\}となる。

    ゆえに、あるy\in Yでx=x\wedge y(\iff x\le y)となり、xは素元である。

  2. 既約元=素元ならば分配束
    待遇を示す。つまり、分配束でないならば既約元だが素元でない元が存在することを示す。
    分配束でない束は必ず\mathrm{M}_3か\mathrm{N}_5を部分束として含むため、それぞれで既約だが素元でない元があることを示せばよい。

    ◯\mathrm{M}_3の場合
    b\le\vee\{c, d\}だがb\le cでもb\le dでもないためbは素元ではない。（bは直下の元がeのみのため既約）

    ◯\mathrm{N}_5の場合
    c\le\vee\{b, d\}だがc\le bでもc\le dでもないためcは素元ではない。（cは直下の元がdのみのため既約）

\square

図1. 束\mathit{M}_3

図2. 束\mathit{N}_5

定理12により、分配束の純粋にjoinのみを用いた特徴づけが得られました。

さらに、分配束はある種の一意分解性を持ちます。すなわち、（非常長な）有限個の既約元の上限として表現される場合、その表現は一意となります。

定理13: 分配束の一意分解性

分配束 Lに対し、\vee S=\vee Tとなる既約元集合 L^\mathrm{ir}の任意の有限反鎖 S, Tを取る。そのとき、S=Tである。

証明

\vee S=\vee Tとなる既約元集合L^\mathrm{ir}上の任意の有限反鎖S, Tを取る。

任意のt\in Tに対し、t\le\vee T=\vee Sゆえ、tは素元より\exists s\in S, t\le sである。同様に、\forall s\in S, \exists t\in T, s\le tとなる。

ゆえに、\forall s\in S, \exists t\in T, \exists s'\in S, s\le t\le s'となるが、Sは反鎖よりs=s'となり、s=t\in Tとなる。
すなわち、S\subseteq Tが言え、同様にT\subseteq Sゆえに、S=Tとなる。

（S, Tが空集合でもこの議論は成り立つことに注意）
\square

定理13の逆について

定理13は逆も成り立ちます。すなわち、一意な既約元表現を持つ束は必ず分配束となります。

証明も簡単で、待遇を考えれば \mathrm{M}_3と\mathrm{N}_5が複数通りの既約元表現を持つ元を持つことを示せばよいですが、これは明らかです。

このように既約元表現が存在すれば一意であることは言えましたが、常に有限な既約元表現が存在するとは限りません。

しかし、Lがある種の有限性（=分解が無限に続かないこと）を満たせば、Lの任意の元x\in Lは有限個の既約元の上限として表現されることが言えます。

定理14: 有限表現を持つ束

束Lが条件(DCC)をみたすとき、任意の元x\in Lは有限個の既約元の上限として表現される。ただし、(DCC)とは「Lは無限下降列を持たない」という条件である。

証明

今、束が条件(DCC)を満たすことより<は整礎関係ゆえ、整礎帰納法を用いて示す。（整礎帰納法を知らない方は普通の帰納法だと思って読んでください）

x\in Lが既約ならx=\vee\{x\}となりOKゆえ、xが既約でないとする。
すると、x=\vee Yかつすべてy<xとなる有限集合 Y\subseteq_\mathrm{fin}Lが存在する。
そのとき、帰納法の仮定よりy\in Yはすべて有限個の既約元の上限として表現できる。

ゆえに、xも有限個の既約元として表現できる。
\square

これら事実の応用として、自然数の素因数分解の一意性を証明することができます。

例：素因数分解の一意性
自然数上の整除関係による束Lは実は(DCC)を満たす分配束になり、よって常に有限個の素数の累乗（=素元=既約元）の積（=最小公倍数=上限）で表現される。（つまり素因数分解が存在するということ）
そのとき定理11より、素因数分解は一意である。

結局分配束とは何なのか？

⚠️注意：この補足は私の個人的な思想が多分に含まれていますので、あまり真に受けずに流し読み程度にしてください。

多くの文献で「分配束とは分配律を満たす束である」と定義されるものの、実際に分配律そのものが活躍することは多くはありません。
むしろ、分配束は表現の一意性に着目されることが多いような気がします。

では、「分配束とは一意な表現を持つことが本質」と言ってもよいでしょうか？
個人的には、そうは思いません。なぜなら、別に分配束でなくても素元による表現は常に一意となるからです。（証明略）

つまり、分配束の本質は「既約元と素元が一致すること」であり、既約元表現の一意性はその副産物にすぎないと考えています。

束論という物語の主人公はあくまで素元であり、純粋な束論には既約元は存在しません。
しかし、その主人公を素元から既約元に置き換えた二次創作的な理論こそが（束論ではなく）分配束論であり、私は分配束とは束のパラレルワールド的存在なのだと思っています。

また、このような観点からは分配束はjoinのみで定義することができ、私は(分配)束論にはmeetは不要であると考えています。
（つまり、半束論こそが束論の真の姿なのではないかと考えています）

実際、半束とは（非空な）有限集合について完備な半順序集合、すなわち、有限完備半順序集合 (fcpo)ということが出来ます。

dcpoの理論である領域理論が非常に豊かな理論であることを考えれば、fcpoの理論である半束論もまた非常に豊かな理論になるのではないかと妄想しております。

（イデアルの対応について。領域理論では有向集合 Dが生成する下方集合 \mathord\downarrow Dをイデアルと呼びますが、半束論では有限集合 Fが生成する下方集合 \mathord\downarrow Fをイデアルします。\mathord\downarrow F自体は有限集合ではありませんが、fcpoにおいて\mathord\downarrow Fは上限を持つことには注意してください。）

誰かdcpoで言えることがどの程度fcpoでも言えるのか考えてみてほしいです（最後は丸投げ）

連続束と代数的束

最後に、コンピュータサイエンス等で重要となる束である、連続束と代数的束を紹介します。
まず、"Introduction to Lattices and Order" (Davey & Priestley, 2002)の用語を採用して、完備束上の元のコンパクト性と有限性を定義します。

定義15: コンパクト、有限

Lを完備束とする。

  1. x\in L\text{ is finite}\iff\forall D\subseteq_\mathrm{dir}L, x\le \sqcup{D}\implies\exists d\in D, x\le d
  2. x\in L\text{ is compact}\iff\forall S\subseteq L, x\le\vee S\implies\exists T\subseteq_\mathrm{fin}S, x\le\vee T

つまり、コンパクトの定義は位相空間論におけるコンパクト性の定義と全く同じです。
また、有限の定義は領域理論において一般的な有限性の定義と一致しています。

しかし、結局は完備束においては有限性とコンパクト性は同値になります。

命題16: コンパクト性と有限性の同値性

完備束Lにおいて、コンパクト性と有限性は同値である。

証明
コンパクトならば有限

有向集合D\subseteq_\mathrm{dir}Lに対し、x\le\sqcup Dとする。
コンパクト性より、x\le\vee Tなる有限集合T\subseteq Dが存在する。
Dの有向性より、Tの上界d\in Dが存在し、x\le\vee T\le dとなる。

有限ならばコンパクト

S\subseteq Lに対し、x\le\vee Sとする。
すると、D=\{\vee T\mid T\subseteq_\mathrm{fin}S\}は有向集合であり、\sqcup D=\vee Sが容易に分かる。
故に、x\le\vee S\le\sqcup Dとなり、xの有限性より\exists T\subseteq_\mathrm{fin}D, x\le\vee Tとなる。
\square

開集合の束は完備束として見ても上限演算は和集合で得られるため、コンパクト開集合は普通に有限な元と定義しても問題ありません。

また、完備束Lについて、way-below関係 \llを次のように定義します。[5]

x\ll y\iff\forall D\subseteq_\mathrm{dir}L, y\le\sqcup D\implies\exists d\in D, x\le d

すると、有限性はx\ll xを満たす元とも定義できます。
そこで、これらの概念を用いて連続束 (continuous lattice)と代数的束 (algebraic lattice)[6]を定義します。
（領域理論を知っていれば、それぞれ完備束である連続dcpoと代数的dcpoと定義もできます）

定義17: 連続束、代数的束

完備束Lに対し、次の定義をする。

  • L\text{ is continuous}\iff\forall x\in L, x=\bigvee\{y\in L\mid y\ll x\}
  • L\text{ is algebraic}\iff\forall x\in L, x=\bigvee\{y\in L\mid y\ll y\le x\}

代数的束は常に連続束になります。（way-below関係の性質としてx\ll y\le z\implies x\ll zが成り立つ）

おわりに

お疲れ様でした。ここまで読んでいただきありがとうございました。

順序や位相空間論は非常に面白い分野ですね！こういうのが好きだったら領域理論も絶対好きだと思います。領域理論という広い分野において、意味論の話はごく一部の話にしかすぎず、純粋に順序理論として非常におもしろい分野だと思います。
みなさんも興味があればぜひ束論や領域理論、点なし位相空間論などいろいろ学んでみてください。

改めて、本当にありがとうございました。

脚注

  1. 部分束に閉じないことを言えば十分ですが、例えば完備束(\mathcal{P}(\mathbb{N}), \subseteq)の有限集合のみ取り出した部分束(\mathcal{P}_\mathrm{fin}(\mathbb{N}), \subseteq)は明らかに完備ではありません。 ↩︎

  2. 完備束Lが完全分配的であることと、LとL^\text{op}がともにcontinuous posetであることが同値ってwikiに書いてありました（知らんけど） ↩︎

  3. 他にも多数決関数による特徴づけなども有名です。 ↩︎

  4. 無限だと直下の元が一意でも既約じゃない場合があります。（0<x_1<x_2<...<1かつ0<x<1のとき、1は直下の元がxのみですが既約元じゃありません） ↩︎

  5. 「なんだこの定義？」と思った方はぜひ私の領域理論の記事を読んでください！ ↩︎

  6. 完全分配的代数的束はprime algebraic latticeと呼ばれる、全ての元がcomplete primeの上限と書ける完備束と等価になります。(c. f. "Prime Algebraicity" by Glynn Winskel)無限の場合でも素元による表現性と分配性に深い関わりがあることを示唆しており、分配性についての洞察が深まります。 ↩︎

Discussion