分配束

同義語:distributive lattice

概要

分配束(distributive lattice)とは、すべての元で分配律 $x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)$ を満たす束であり、この条件は双対の $x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z)$ と同値である。集合の束、鎖、正の整数の整除関係、Heyting 代数や Boole 代数が例であり、2 次元以上のベクトル空間の部分空間の束は菱形 $M_3$ を含むので分配的でない。束が分配束であることは、菱形 $M_3$ とも五角形 $N_5$ とも同型な部分束をもたないことと同値であり(Birkhoff)、消去律が成り立つこととも同値である。空でない有限分配束は結合既約元のなす半順序集合の下方集合の束と同型になり、空でない有限分配束と有限半順序集合はこの対応で一対一に対応する。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 束, 半順序集合

集合の和集合と共通部分は、$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ のように、数の掛け算と足し算と同じ形で展開できる。整数の最大公約数と最小公倍数、命題の「かつ」と「または」、実数の最小値と最大値でも同じ展開が成り立つ。一方、ベクトル空間の部分空間の束では、平面の三本の異なる直線 $\ell_1,\ell_2,\ell_3$ について $\ell_1\cap(\ell_2+\ell_3)=\ell_1$ だが $(\ell_1\cap\ell_2)+(\ell_1\cap\ell_3)=0$ となり、展開できない。結びと交わりがこの展開を許す束が分配束である。分配束は、空でない有限の場合には有限の半順序集合と一対一に対応し、一般には集合の束として実現される。

定義

分配束

束 $(L,\vee,\wedge)$ が、すべての $x,y,z\in L$ について分配律
$$ x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)\qquad\text{(D1)} $$
を満たすとき、$L$ を分配束(distributive lattice)という。

この定義は BS12 I §3 Definition 3.1(p. 10)にあり、束 の定義「分配束・完備束・有界束・部分束」と同じものである。(D1)の双対、すなわち結びと交わりを入れ替えた式
$$ x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z)\qquad\text{(D2)} $$
を使っても同じ概念が得られる。

二つの分配律の同値性

束 $L$ について、すべての元で(D1)が成り立つことと、すべての元で(D2)が成り立つことは同値である。

(D1)を仮定する。任意の $x,y,z$ について、まず(D1)を $x\vee y$ と $x,z$ に当てはめ、次に吸収律 $(x\vee y)\wedge x=x$ を使うと
$$ (x\vee y)\wedge(x\vee z)=\bigl((x\vee y)\wedge x\bigr)\vee\bigl((x\vee y)\wedge z\bigr)=x\vee\bigl(z\wedge(x\vee y)\bigr) $$
となる。さらに(D1)を $z$ と $x,y$ に当てはめると $z\wedge(x\vee y)=(z\wedge x)\vee(z\wedge y)$ なので、結合律と吸収律 $x\vee(z\wedge x)=x$ により
$$ x\vee(z\wedge x)\vee(z\wedge y)=x\vee(y\wedge z) $$
である。よって(D2)が成り立つ。束の公理は $\vee$ と $\wedge$ を入れ替えても変わらないので、同じ計算で $\vee$ と $\wedge$ を入れ替えれば(D2)から(D1)が従う。$\square$

BS12 I §3 Theorem 3.2(p. 10)も同じ計算である。どの束でも $(x\wedge y)\vee(x\wedge z)\le x\wedge(y\vee z)$ が成り立つので(束 の命題「一般の束で成り立つ分配不等式」)、分配束であることを確かめるには逆向きの不等式 $x\wedge(y\vee z)\le(x\wedge y)\vee(x\wedge z)$ を示せば足りる。

束準同型

束 $L,M$ の間の写像 $f\colon L\to M$ が $f(x\vee y)=f(x)\vee f(y)$、$f(x\wedge y)=f(x)\wedge f(y)$ を満たすとき、$f$ を束準同型という。全単射な束準同型を束同型という。

分配律は恒等式なので、分配束の部分束(演算で閉じた部分集合)、分配束の族の直積(成分ごとの演算)、分配束の全射準同型の像は、いずれも分配束である(代数構造 の命題「準同型は項の計算と可換」)。

直感

分配束では、結びと交わりからなる式を、和集合と共通部分の式と同じように展開して整理できる。展開できるということは、元が「その下にある基本的な部品の集まり」で決まることを意味する。冪集合では部品は一点集合であり、整数の整除では素数冪である。有限の分配束では、この部品が結合既約元であり、束全体は部品の半順序集合から復元される。これが本記事の後半の表現定理である。
反対に、分配律が破れる束には、必ず菱形 $M_3$ か五角形 $N_5$ という五元の束が部分束として現れる。分配性は「この二つの形を含まないこと」として、形の言葉で特徴づけられる。

例と反例

集合の束

集合 $X$ の冪集合 $\mathcal P(X)$ は、和集合と共通部分について分配束である。より一般に、$\mathcal P(X)$ の部分集合族で有限個の和集合と共通部分について閉じたもの(集合の束、ring of sets。測度論でいう集合環とは別の概念)は $\mathcal P(X)$ の部分束なので分配束である。たとえば位相空間の開集合全体、有限部分集合全体、余有限部分集合全体はいずれも分配束である。半順序集合 $P$ の下方集合($d\in D$、$p\le d$ なら $p\in D$ を満たす部分集合 $D$)の全体 $\mathcal O(P)$ も和集合と共通部分で閉じるので分配束である。

全順序の分配性

全順序集合(鎖)は、$x\vee y=\max\{x,y\}$、$x\wedge y=\min\{x,y\}$ により分配束である。実際 $y\le z$ としてよく、このとき左辺は $x\wedge(y\vee z)=\min\{x,z\}$ であり、$\min\{x,y\}\le\min\{x,z\}$ なので右辺も $\max\{\min\{x,y\},\min\{x,z\}\}=\min\{x,z\}$ である。

正の整数の整除の束

正の整数に整除関係を入れた束(結びは最小公倍数、交わりは最大公約数)は分配束である。整除関係 の記事では、素因数分解の指数をとる写像が、この束を有限個を除いて $0$ である非負整数の列の集合に成分ごとの順序を入れたものと同型にすることを示している。後者は鎖 $\mathbb N$ の直積の部分束なので、分配束である。とくに
$$ \gcd(a,\operatorname{lcm}(b,c))=\operatorname{lcm}(\gcd(a,b),\gcd(a,c)) $$
がすべての正の整数で成り立つ。

Heyting代数は分配束

Heyting代数 は分配束である。とくに Boole代数 は分配束である。

$H$ を Heyting 代数とし、$a,b,c\in H$ について $d:=(a\wedge b)\vee(a\wedge c)$ とおく。$b\wedge a\le d$ なので、含意の条件から $b\le(a\Rightarrow d)$ であり、同様に $c\le(a\Rightarrow d)$ である。よって $b\vee c\le(a\Rightarrow d)$ であり、ふたたび含意の条件から $(b\vee c)\wedge a\le d$ を得る。逆向きの不等式はどの束でも成り立つので、$a\wedge(b\vee c)=d$ である。Boole 代数は、定義により補元をもつ分配束である(Boole代数)。$\square$

反例:菱形と五角形

菱形 $M_3$ は、最小元 $0$ と最大元 $1$ の間に互いに比較できない三元 $a,b,c$ をもつ五元の束であり、五角形 $N_5$ は、鎖 $0< a< b< 1$ に、$a,b$ のどちらとも比較できない元 $c$($0< c< 1$)を加えた五元の束である。束 の注意「非分配束」で計算されているとおり、どちらも分配束でない。$M_3$ では $a\wedge(b\vee c)=a\ne0=(a\wedge b)\vee(a\wedge c)$ である。

部分空間と部分群の束

体 $K$ 上の $2$ 次元ベクトル空間 $K^2$ の部分空間全体の束(結びは和、交わりは共通部分)は、$K$ が何であっても、異なる三本の直線 $\ell_1,\ell_2,\ell_3$ と $0$、$K^2$ からなる $M_3$ と同型な部分束を含むので、分配束でない。同様に、Klein の四元群 $V=\{e,x,y,xy\}$ の部分群の束は $\{e\}$、$\langle x\rangle$、$\langle y\rangle$、$\langle xy\rangle$、$V$ の五元からなり、$M_3$ と同型である(Kleinの四元群)。$V$ は可換なのでこれは正規部分群の束でもあり、モジュラー束 の例「群の正規部分群の束」によりモジュラー束だが、分配束ではない。

消去律と補元の一意性

分配束の消去律

分配束 $L$ の元 $x,y,z$ が $x\wedge y=x\wedge z$ かつ $x\vee y=x\vee z$ を満たせば、$y=z$ である。

吸収律、仮定、(D1)を順に使うと
$$ y=y\wedge(x\vee y)=y\wedge(x\vee z)=(y\wedge x)\vee(y\wedge z)=(x\wedge z)\vee(y\wedge z) $$
である。最後の式は(D1)を逆に読むと $z\wedge(x\vee y)=z\wedge(x\vee z)=z$ に等しい。$\square$

最小元 $0$ と最大元 $1$ をもつ束で、$x\wedge x'=0$、$x\vee x'=1$ を満たす $x'$ を $x$ の補元という。消去律を $y,z$ を二つの補元として当てはめると、分配束では補元はあっても一つしかないことがわかる。$M_3$ では $a$ の補元が $b$ と $c$ の二つあり、$N_5$ では $c$ の補元が $a$ と $b$ の二つある($c\wedge a=c\wedge b=0$、$c\vee a=c\vee b=1$)。どちらの束でも消去律が破れている。次の節の定理から、逆に消去律を満たす束は分配束であることも従う。

菱形と五角形による特徴づけ

分配律が破れる束には、必ず $M_3$ か $N_5$ が部分束として入っている。証明ではモジュラー束を経由する。束 $L$ がモジュラー束であるとは、$x\le z$ ならば $x\vee(y\wedge z)=(x\vee y)\wedge z$ が成り立つことをいう(モジュラー束 の定義「モジュラー律」)。どの束でも $x\le z$ なら $x\vee(y\wedge z)\le(x\vee y)\wedge z$ であり(モジュラー束 の命題「モジュラー不等式(任意の束で成立)」)、分配束はモジュラー束である(同記事の命題「分配束はモジュラー束である」)。モジュラー律は $\vee$ と $\wedge$ を入れ替えて $x$ と $z$ の名前を入れ替えると同じ条件に戻るので、モジュラー束で成り立つ等式は、双対をとってもモジュラー束で成り立つ。

モジュラーでない束の中の五角形

束 $L$ の元 $x,y,z$ が $x\le z$ かつ $p:=x\vee(y\wedge z)$、$q:=(x\vee y)\wedge z$ について $p\ne q$ を満たすとする。$o:=y\wedge z$、$i:=x\vee y$ とおくと、五つの元 $o,p,q,i,y$ は相異なり、$o< p< q< i$、$o< y< i$、$y$ は $p,q$ と比較できず、
$$ y\wedge p=y\wedge q=o,\qquad y\vee p=y\vee q=i $$
が成り立つ。とくに $\{o,p,q,y,i\}$ は $N_5$ と同型な部分束である。

要点:$y\wedge q=y\wedge z$ と $y\vee p=x\vee y$ をまず計算し、$y$ が $p,q$ と比較できるとするといずれも $p< q$ に反することを確かめる。

詳しい証明を開く

モジュラー不等式から $p\le q$ であり、仮定から $p< q$ である。$o\le x\vee o=p$ かつ $q\le x\vee y=i$ である。

$y\le i$ なので $y\wedge q=y\wedge(x\vee y)\wedge z=y\wedge z=o$ である。$o\le p\le q$ から $o=y\wedge o\le y\wedge p\le y\wedge q=o$ となり、$y\wedge p=o$ である。双対に、$o\le y$ なので $y\vee p=y\vee x\vee(y\wedge z)=x\vee y=i$ であり、$p\le q\le i$ から $i=y\vee p\le y\vee q\le y\vee i=i$ となって $y\vee q=i$ である。

次に比較できないことを示す。$y\le q$ なら $y=y\wedge q=o\le z$ なので、$p=x\vee(y\wedge z)=x\vee y$ となり、$q\le x\vee y=p$ と $p< q$ に反する。よって $y\not\le q$ であり、$p\le q$ から $y\not\le p$ である。$p\le y$ なら $i=y\vee p=y$ なので $x\le y$ であり、$q=(x\vee y)\wedge z=y\wedge z=o\le p$ となって矛盾する。よって $p\not\le y$ であり、$p\le q$ から $q\not\le y$ である。

以上から $y\ne p,q$ であり、$y=o$ なら $y\le q$、$y=i$ なら $p\le y$ となるので $y\ne o,i$ である。$o=p$ なら $p\le y$、$q=i$ なら $y\le q$ となるので、$o< p$ かつ $q< i$ である。こうして五元は相異なり、$o$ は五元すべて以下、$i$ は五元すべて以上である。五元のどの二元の結びと交わりも、上の等式と $o,i$ の性質と鎖 $o< p< q< i$ から五元の中にある。よって部分束であり、$o\mapsto0$、$p\mapsto a$、$q\mapsto b$、$y\mapsto c$、$i\mapsto1$ が $N_5$ との同型を与える。$\square$

モジュラーで分配的でない束の中の菱形

$L$ をモジュラー束とし、$a,b,c\in L$ が $(a\wedge b)\vee(a\wedge c)\ne a\wedge(b\vee c)$ を満たすとする。
$$ d:=(a\wedge b)\vee(a\wedge c)\vee(b\wedge c),\qquad e:=(a\vee b)\wedge(a\vee c)\wedge(b\vee c), $$
$$ a_1:=(a\wedge e)\vee d,\qquad b_1:=(b\wedge e)\vee d,\qquad c_1:=(c\wedge e)\vee d $$
とおくと、$\{d,a_1,b_1,c_1,e\}$ は $M_3$ と同型な部分束であり、$d$ が最小元、$e$ が最大元である。

要点:$d\le a_1,b_1,c_1\le e$ であり、モジュラー律を何度か当てはめると、三元のどの二つの交わりも $d$、結びも $e$ になる。仮定は $d\ne e$ を保証するために使う。

詳しい証明を開く

$d$ の各項は $e$ の各項以下なので(たとえば $a\wedge b\le a\le a\vee c$、$a\wedge b\le b\le b\vee c$)、$d\le e$ である。よって $d\le a_1,b_1,c_1\le e$ である。$d$ と $e$ は $a,b,c$ について対称なので、以下の計算は $a,b,c$ を入れ替えても成り立つ。

$d< e$ であること。 $a\le a\vee b$、$a\le a\vee c$ なので $a\wedge e=a\wedge(b\vee c)$ である。一方、$(a\wedge b)\vee(a\wedge c)\le a$ にモジュラー律を当てはめると

$$a\wedge d=\bigl((a\wedge b)\vee(a\wedge c)\bigr)\vee(b\wedge c\wedge a)=(a\wedge b)\vee(a\wedge c)$$

である。仮定からこれは $a\wedge(b\vee c)=a\wedge e$ と異なるので、$d\ne e$ である。

$a_1\wedge b_1=d$ であること。 $d\le b_1$ にモジュラー律を当てはめると $a_1\wedge b_1=\bigl(d\vee(a\wedge e)\bigr)\wedge b_1=d\vee(a\wedge e\wedge b_1)$ である。$d\le e$ にモジュラー律を当てはめると $b_1=d\vee(b\wedge e)=(d\vee b)\wedge e$ であり、$d\vee b=b\vee(a\wedge c)$ である。よって $a\wedge e\wedge b_1=a\wedge(b\vee c)\wedge\bigl(b\vee(a\wedge c)\bigr)$ となる。$b\le b\vee c$ にモジュラー律を当てはめると、$a\wedge c\le b\vee c$ より

$$\bigl(b\vee(a\wedge c)\bigr)\wedge(b\vee c)=b\vee\bigl((a\wedge c)\wedge(b\vee c)\bigr)=b\vee(a\wedge c)$$

なので、$a\wedge e\wedge b_1=a\wedge\bigl(b\vee(a\wedge c)\bigr)$ である。最後に $a\wedge c\le a$ にモジュラー律を当てはめると、これは $(a\wedge c)\vee(b\wedge a)$ に等しく、$d$ 以下である。したがって $a_1\wedge b_1=d$ である。対称性から $a_1\wedge c_1=b_1\wedge c_1=d$ である。

結びが $e$ であること。 $d\le e$ にモジュラー律を当てはめると $a_1=(a\vee d)\wedge e$ であり、$b_1,c_1$ も同様である。この形は $a_1$ の定義の双対であり、$d$ と $e$ の定義も互いに双対である。交わりの計算はモジュラー律と $d,e$ の定義だけを使い、仮定 $d\ne e$ を使っていないので、モジュラー束での上の計算の双対をとれば、$a_1\vee b_1=a_1\vee c_1=b_1\vee c_1=e$ を得る。

五元が相異なること。 $a_1=b_1$ なら $a_1=a_1\wedge b_1=d$ かつ $a_1=a_1\vee b_1=e$ となって $d< e$ に反する。他の組も同様である。$a_1=d$ なら $c_1=a_1\vee c_1=e$、$b_1=a_1\vee b_1=e$ となり、$b_1\wedge c_1=e\ne d$ に反する。双対に $a_1\ne e$ であり、$b_1,c_1$ も同様である。よって五元は相異なり、どの二元の結びと交わりも五元の中にあるので、$M_3$ と同型な部分束である。$\square$

菱形と五角形による分配束の特徴づけ

束 $L$ について次が成り立つ。

  1. $L$ がモジュラー束であることと、$L$ が $N_5$ と同型な部分束をもたないことは同値である(Dedekind)。
  2. $L$ が分配束であることと、$L$ が $M_3$ とも $N_5$ とも同型な部分束をもたないことは同値である(Birkhoff)。

部分束の結びと交わりは $L$ のものと同じなので、$L$ で成り立つ恒等式や $x\le z$ を仮定とする等式は部分束でも成り立つ。

  1. $L$ がモジュラー束なら、その部分束もモジュラー束であり、$N_5$ はモジュラーでない($a\le b$ だが $a\vee(c\wedge b)=a\ne b=(a\vee c)\wedge b$)ので、$N_5$ と同型な部分束はない。逆に $L$ がモジュラー束でなければ、$x\le z$ で $x\vee(y\wedge z)\ne(x\vee y)\wedge z$ となる元があり、lem-dl-n5 により $N_5$ と同型な部分束がある。
  2. $L$ が分配束なら、その部分束も分配束であり、$M_3$ と $N_5$ は分配束でないので(rem-dl-m3-n5)、どちらとも同型な部分束はない。逆に $L$ が分配束でないとする。$L$ がモジュラー束でなければ 1 により $N_5$ と同型な部分束がある。$L$ がモジュラー束なら、(D1)を破る $a,b,c$ があり、lem-dl-m3 により $M_3$ と同型な部分束がある。$\square$

1 は BS12 I §3 Theorem 3.5(p. 11)、2 は同 Theorem 3.6(pp. 12–13)にある。モジュラー束 の定理「Dedekindの特徴づけ」の、$N_5$ を含まない束がモジュラーであるという向きは、lem-dl-n5 で示したことになる。

消去律による特徴づけ

束 $L$ が分配束であることと、$x\wedge y=x\wedge z$ かつ $x\vee y=x\vee z$ ならば $y=z$ となることは同値である。

分配束なら prop-dl-cancellation により成り立つ。分配束でなければ、thm-dl-m3-n5 により $M_3$ か $N_5$ と同型な部分束がある。前の節で見たとおり、その中の三元($M_3$ なら $a,b,c$、$N_5$ なら $c,a,b$)が消去律を破り、部分束の演算は $L$ の演算と同じなので、$L$ でも消去律が破れる。$\square$

有限分配束の表現定理

有限の分配束は、下方集合の束 $\mathcal O(P)$ の形にかならず書ける。部品にあたるのが次の元である。

結合既約元

最小元 $0$ をもつ束 $L$ の元 $j$ が結合既約(join-irreducible)であるとは、$j\ne0$ であり、$j=x\vee y$ ならば $j=x$ または $j=y$ となることをいう。結合既約元の全体に $L$ の順序を制限した半順序集合を $J(L)$ と書く。

帰納法により、結合既約元 $j$ が空でない有限個の元の結び $x_1\vee\cdots\vee x_n$ に等しければ、ある $k$ で $j=x_k$ である。空でない有限束は最小元をもつ(束 の命題「空でない有限束は完備束」)。半順序集合 $P$ の元 $p$ に対し、$\mathord{\downarrow}p:=\{q\in P\mid q\le p\}$ は下方集合であり、これを $p$ の主下方集合という。

結合既約元による分離

$L$ を空でない有限束とする。

  1. $a,b\in L$ で $a\not\le b$ なら、$j\le a$ かつ $j\not\le b$ を満たす結合既約元 $j$ がある。
  2. 各 $a\in L$ は、$a$ 以下の結合既約元全体の結びに等しい(空の結びは $0$ とする)。
  3. $L$ が分配束なら、結合既約元 $j$ と空でない有限個の元について、$j\le x_1\vee\cdots\vee x_n$ ならばある $k$ で $j\le x_k$ である。
  1. $T:=\{x\in L\mid x\le a,\ x\not\le b\}$ は $a$ を含むので空でなく、有限なので極小元 $j$ をもつ。$0\le b$ なので $j\ne0$ である。$j=x\vee y$ で $x\ne j$、$y\ne j$ とすると、$x,y< j\le a$ であり、$j$ の極小性から $x,y\notin T$、つまり $x,y\le b$ である。すると $j=x\vee y\le b$ となって $j\in T$ に反する。よって $j$ は結合既約である。
  2. $a$ 以下の結合既約元全体の結びを $s$ とすると $s\le a$ である。$a\not\le s$ なら、1 により $j\le a$、$j\not\le s$ となる結合既約元 $j$ があるが、$j$ は $s$ を作る結びに含まれるので $j\le s$ であり、矛盾する。よって $a=s$ である。
  3. (D1)を繰り返し使うと $j=j\wedge(x_1\vee\cdots\vee x_n)=(j\wedge x_1)\vee\cdots\vee(j\wedge x_n)$ であり、$j$ は結合既約なので、ある $k$ で $j=j\wedge x_k$、すなわち $j\le x_k$ である。$\square$
有限分配束の表現定理(Birkhoff)
  1. $L$ を空でない有限分配束とすると、写像
    $$ \varphi\colon L\to\mathcal O(J(L)),\qquad \varphi(a):=\{j\in J(L)\mid j\le a\} $$
    は束同型である。
  2. 有限半順序集合 $P$ に対し、$\mathcal O(P)$ の結合既約元はちょうど主下方集合 $\mathord{\downarrow}p$($p\in P$)であり、$p\mapsto\mathord{\downarrow}p$ は $P$ から $J(\mathcal O(P))$ への順序同型である。
    したがって、空でない有限分配束の同型類と、有限半順序集合の同型類は、$L\mapsto J(L)$ と $P\mapsto\mathcal O(P)$ によって一対一に対応する。
  1. $\varphi(a)$ は下方集合である。$j\le a\wedge b$ は $j\le a$ かつ $j\le b$ と同値なので $\varphi(a\wedge b)=\varphi(a)\cap\varphi(b)$ である。$\varphi(a)\cup\varphi(b)\subseteq\varphi(a\vee b)$ は明らかで、逆の包含は lem-dl-separation の 3 による。よって $\varphi$ は束準同型である。lem-dl-separation の 2 により $a$ は $\varphi(a)$ の結びとして復元されるので、$\varphi$ は単射である。全射を示す。$D\in\mathcal O(J(L))$ をとり、$a:=\bigvee D$($D=\emptyset$ なら $a=0$)とおく。$D\subseteq\varphi(a)$ は明らかである。逆に $j\in\varphi(a)$ なら、$j\ne0$ なので $D\ne\emptyset$ であり、lem-dl-separation の 3 によりある $d\in D$ で $j\le d$ となる。$D$ は下方集合なので $j\in D$ である。よって $\varphi(a)=D$ である。全単射な束準同型なので束同型である。
  2. $\mathcal O(P)$ の結びは和集合、最小元は $\emptyset$ である。$\mathord{\downarrow}p\ne\emptyset$ であり、$\mathord{\downarrow}p=D_1\cup D_2$ なら $p$ はどちらか、たとえば $D_1$ に属し、$D_1$ は下方集合なので $\mathord{\downarrow}p\subseteq D_1\subseteq\mathord{\downarrow}p$ となる。よって $\mathord{\downarrow}p$ は結合既約である。逆に $D$ が結合既約なら、$D\ne\emptyset$ であり、$D=\bigcup_{p\in D}\mathord{\downarrow}p$ は空でない有限個の和集合なので、ある $p\in D$ で $D=\mathord{\downarrow}p$ である。$p\le q$ と $\mathord{\downarrow}p\subseteq\mathord{\downarrow}q$ は同値なので、$p\mapsto\mathord{\downarrow}p$ は順序同型である。
    最後の主張は、1 により $L\cong\mathcal O(J(L))$、2 により $P\cong J(\mathcal O(P))$ となることと、$\mathcal O(P)$ が分配束であること(ex-dl-sets)による。$\square$

この定理は GvG Lemma 1.20・Proposition 1.21(p. 25)、Proposition 1.22(p. 26)、Theorem 1.25(p. 27)にあり、BS12 I §3 Exercise 4(p. 14)では空でない下方集合を使う形で述べられている。

12 の約数の束

$12$ の正の約数 $\{1,2,3,4,6,12\}$ に整除関係を入れた分配束を $L$ とする。結合既約元は、二つの真の約数の最小公倍数で書けない $1$ 以外の元、すなわち素数冪 $2,4,3$ であり、$J(L)$ は $2< 4$ と、それらと比較できない $3$ からなる半順序集合である。その下方集合は
$$ \emptyset,\ \{2\},\ \{3\},\ \{2,3\},\ \{2,4\},\ \{2,3,4\} $$
の六つで、順に $1,2,3,6,4,12$ に対応する。一般に正の整数 $n$ の約数の束では、$J$ は $n$ を割る素数冪全体であり、素数ごとの鎖を並べた半順序集合になる。

有限 Boole 代数

有限集合 $S$ の冪集合 $\mathcal P(S)$ の結合既約元は一点集合であり、$J(\mathcal P(S))$ は互いに比較できない $\#S$ 個の元からなる。逆に、有限 Boole 代数の結合既約元は原子(最小元の直上の元)であり、$J$ の順序は自明になる(GvG Proposition 1.26、p. 28)。表現定理と合わせると、有限 Boole 代数は冪集合と同型であり、元の個数は $2$ の冪である。三元の鎖 $0< 1< 2$ は分配束だが、元の個数が $2$ の冪でないので Boole 代数でない。実際 $1$ は補元をもたない。

表現定理から、空でない有限分配束 $L$ は、$J(L)$ の冪集合の部分束に埋め込まれる。下方集合の数え上げに帰着するので、たとえば $J(L)$ が $k$ 元の鎖なら $L$ は $k+1$ 元の鎖であり、$k$ 元の反鎖なら $L$ は $2^k$ 元の Boole 代数である。

無限の分配束

無限の分配束では、結合既約元が足りないことがある。

反例:結合既約元をもたない分配束

$\mathbb N$ の余有限部分集合(補集合が有限な部分集合)全体に空集合を加えた族 $L$ を考える(GvG Exercise 1.2.6 c、p. 22 と同じ束)。二つの余有限集合の和集合と共通部分は余有限であり、$\emptyset$ との和集合・共通部分も $L$ に属するので、$L$ は $\mathcal P(\mathbb N)$ の部分束であり、最小元 $\emptyset$ をもつ分配束である。$\emptyset$ は最小元なので結合既約でない。余有限な $U$ は無限集合なので異なる二元 $x,y\in U$ を選べて、$U=(U\setminus\{x\})\cup(U\setminus\{y\})$ となる。右辺の二つは余有限なので $L$ に属し、どちらも $U$ と異なる。よって $J(L)=\emptyset$ であり、写像 $\varphi$ はすべての元を $\emptyset$ に送るので単射でない。有限性を外すと、lem-dl-separation の 2 と thm-dl-birkhoff の 1 は成り立たない。

結合既約元の代わりに素フィルター($a\vee b\in F$ なら $a\in F$ または $b\in F$ を満たす真のフィルター)を使うと、無限の場合にも表現が得られる。分配束 $L$ のフィルター $F$ とイデアル $I$ が交わらなければ、$F$ を含み $I$ と交わらない素フィルターが存在し(GvG Theorem 3.10、p. 54。証明には Zorn の補題を使う)、そこから $a\mapsto\{F\mid F\text{ は素フィルターで }a\in F\}$ が $L$ から素フィルター全体の冪集合への単射な束準同型になる(GvG Theorem 3.11、p. 55)。この記事ではこれらを証明しない。GvG は束に最小元と最大元を含めて扱う(Remark 1.17、p. 17)ので、最小元や最大元のない分配束には新しい最小元・最大元を付け加えてから当てはめる。付け加えた束も分配律を満たすことは、新しい元を含む組を一つずつ確かめればわかり、もとの束はその部分束である。部分束は分配律を受け継ぐので、結果として「束が分配束であることと、ある集合の冪集合の部分束と同型であることは同値」となる。素フィルターに位相を入れて得られる双対性は Stone双対性 の節「分配束への拡張」と スペクトル空間 にある。素フィルターとイデアルの定義は 順序集合上のフィルターとイデアル にある。

反例の表

外す条件反例成り立たなくなること
分配律(モジュラー律は保つ)菱形 $M_3$消去律と補元の一意性($a$ の補元が $b,c$ の二つ)
分配律とモジュラー律五角形 $N_5$消去律と補元の一意性($c$ の補元が $a,b$ の二つ)
分配律菱形 $M_3$$\varphi\colon L\to\mathcal O(J(L))$ が同型であること($J(M_3)$ は三元の反鎖で $\#\mathcal O(J(M_3))=8\ne5$)
有限性$\mathbb N$ の余有限部分集合と $\emptyset$ からなる束各元が下にある結合既約元の結びであること
補元の存在三元の鎖有限分配束が冪集合と同型であること
文献

分配束の定義、二つの分配律の同値性、Dedekind と Birkhoff の特徴づけは BS12 I §3 Definition 3.1・Theorem 3.2(p. 10)、Theorem 3.5(p. 11)、Theorem 3.6(pp. 12–13)にある。有限分配束の表現定理は GvG Lemma 1.20・Proposition 1.21(p. 25)、Proposition 1.22(p. 26)、Theorem 1.25(p. 27)、無限の場合の表現は Theorem 3.10・3.11(pp. 54–55)にある。

関連項目

参考文献

[2]
Mai Gehrke, Sam van Gool, Topological Duality for Distributive Lattices: Theory and Applications, arXiv:2203.03286, arXiv:2203.03286v5(2023)。Remark 1.17(p. 17)、Exercise 1.2.6 c(p. 22)、Lemma 1.20・Proposition 1.21(p. 25)、Proposition 1.22(p. 26)、Theorem 1.25(p. 27)、Proposition 1.26(p. 28)、Theorem 3.10(p. 54)、Theorem 3.11(p. 55)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する