束
概要
束（lattice）とは、任意の二つの元が上限および下限を持つ半順序集合のことである。二元に対して上限を対応させる二項演算と、下限を対応させる二項演算とを持つ代数構造としても定義することができる。
前提知識: 半順序集合
定義
半順序とは、反射律・反対称律・推移律を満たす関係である。以下では集合 $L$ 上の半順序を $\le$ と書く。
束（lattice）とは、任意の二元 $x,y$ に対して上限 $x\vee y$ と下限 $x\wedge y$ が存在する半順序集合 $(L,\le)$ である。ML26 の Lattice に対応する。
本記事では空集合もこの条件を満たす束として認める。非空を要求する流儀を使う場合は、以下の二つの定義にともに非空条件を加える。二元の上限・下限の存在だけでは、任意の無限部分集合の上限・下限や、最小元・最大元の存在は要求しない。
二元の上限と下限は、存在すればそれぞれ一意である。
$s,s'$ がともに $x,y$ の上限なら、$s'$ が上界であることと $s$ の最小性から $s\le s'$。逆向きも同様なので、反対称律から $s=s'$ である。下限については不等号の向きを逆にすればよい。
直感
$x\vee y$ は「$x$ と $y$ の両方以上になるために必要な最小の元」、$x\wedge y$ は「両方以下に収まる最大の元」である。$x,y$ 自身が比較できなくても、共通の上限・下限が存在すればよい。
たとえば集合の包含関係では、和集合が上限、共通部分が下限になる。束は、この二つの操作の関係を一般の順序へ抽象化したものである。
例
集合 $S$ の冪集合 $\mathcal P(S)$（部分集合全体）を包含関係で順序づけると束になる。
$$
A\vee B=A\cup B,\qquad A\wedge B=A\cap B.
$$
$A,B$ を両方含む集合は $A\cup B$ を含み、$A,B$ の両方に含まれる集合は $A\cap B$ に含まれるので、それぞれ上限・下限の条件を満たす。
任意の二元が比較できる全順序集合は束である。
$$
x\vee y=\max\{x,y\},\qquad x\wedge y=\min\{x,y\}.
$$
たとえば通常の順序を入れた $\mathbb R$ は束だが、最小元も最大元も持たない。
異なる二元 $a,b$ からなる集合に、等しい元同士だけを比較する半順序を入れる。$a,b$ には共通の上界も下界もないので、この半順序集合は束ではない。冪集合の例では比較できない部分集合にも和集合・共通部分が用意されていた点が異なる。
代数系としての定義
二つの二項演算 $\vee,\wedge\colon L\times L\to L$ を備えた集合 $L$ が束であるとは、すべての $x,y,z\in L$ について、次の恒等式を満たすことである。
- 交換律: $x\vee y=y\vee x$、$x\wedge y=y\wedge x$。
- 結合律: $(x\vee y)\vee z=x\vee(y\vee z)$、$(x\wedge y)\wedge z=x\wedge(y\wedge z)$。
- 冪等律: $x\vee x=x$、$x\wedge x=x$。
- 吸収律: $x\wedge(x\vee y)=x$、$x\vee(x\wedge y)=x$。
交換律・結合律・冪等律を満たす一つの演算を備えた集合を、可換冪等半群という。したがって、この定義は二つの可換冪等半群構造を吸収律で結びつけたものである。
結び半束と交わり半束
任意の二元の上限だけを要求する半順序集合を**結び半束（join-semilattice）、下限だけを要求するものを交わり半束**（meet-semilattice）という。同じ順序について両方の条件を満たすものが束である。
結び半束の上限演算は交換律・結合律・冪等律を満たす。逆に、その三つの法則を満たす演算 $\vee$ から
$$
x\le y\quad\Longleftrightarrow\quad x\vee y=y
$$
と定めると半順序となり、$x\vee y$ はその順序についての上限になる。
上限の一意性から交換律と冪等律が従う。$(x\vee y)\vee z$ は $\{x,y,z\}$ の最小上界である。同様に $x\vee(y\vee z)$ もそうであるから、両者は一致し、結合律が成り立つ。
逆に、演算から定めた関係の反射律は冪等律による。$x\vee y=y$ かつ $y\vee x=x$ なら交換律から $x=y$ となる。さらに $x\vee y=y$、$y\vee z=z$ なら
$$
x\vee z=x\vee(y\vee z)=(x\vee y)\vee z=y\vee z=z
$$
なので推移律も成り立つ。
$x\vee(x\vee y)=x\vee y$ と、その $x,y$ を交換した式から、$x,y\le x\vee y$ が従う。$x,y\le u$ なら
$$
(x\vee y)\vee u=x\vee(y\vee u)=x\vee u=u
$$
だから $x\vee y\le u$。よって演算の値が最小上界である。
交わり半束についても、不等号の向きを逆にすると同じ対応が得られる。順序は $x\le y\Longleftrightarrow x\wedge y=x$ で復元される。
二つの束の定義の同値性
半順序集合としての束と、代数系としての束は互いに対応する。この二つの構成（順序から演算を作る操作と、演算から順序を作る操作）は互いに逆である。そのとき
$$
x\le y\quad\Longleftrightarrow\quad x\vee y=y
\quad\Longleftrightarrow\quad x\wedge y=x
$$
である。
順序から上限・下限を定めれば、prop-lattice-semilattice により交換律・結合律・冪等律が成り立つ。$x\le x\vee y$ だから $x$ と $x\vee y$ の下限は $x$ であり、$x\wedge(x\vee y)=x$。双対にもう一方の吸収律も成り立つ。
逆に、二つの演算が代数系としての束の法則を満たすとする。prop-lattice-semilattice により、$\vee$ から半順序と二元の上限が得られる。吸収律を使うと、
$$
x\vee y=y\ \Longrightarrow\ x\wedge y=x\wedge(x\vee y)=x,
$$
$$
x\wedge y=x\ \Longrightarrow\ x\vee y=(x\wedge y)\vee y=y
$$
なので、$\wedge$ から得る順序も同じである。したがって $\wedge$ はこの順序の下限を与え、半順序集合としての束が得られる。一意性により、元の順序や演算も復元される。
特別な束のクラス
束 $(L,\vee,\wedge)$ が分配束（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)$）を満たすことをいう。$L$ が完備束（complete lattice）であるとは、任意の部分集合 $S\subseteq L$ が上限・下限を持つことをいう。特に空集合の上限・下限として最小元・最大元が存在するので、完備束は有界束（bounded lattice、最小元と最大元を持つ束）である。$L$ の部分集合 $M$ が部分束（sublattice）であるとは、$M$ が $\vee,\wedge$ で閉じている、すなわち任意の $x,y\in M$ に対し $x\vee y\in M$ かつ $x\wedge y\in M$ であることをいう。
$M_3$（菱形、$0,1$ の間に互いに比較不能な三元 $a,b,c$ を持つ束）と $N_5$（五角形、$0< a< b<1$ の鎖に比較不能な元 $c$（$0< c<1$）を加えた束）はいずれも分配的でない。実際 $N_5$ で $x=b,y=a,z=c$ とすると、$y\vee z=a\vee c=1$ より $x\wedge(y\vee z)=b\wedge1=b$ だが、$x\wedge y=a$、$x\wedge z=b\wedge c=0$ より $(x\wedge y)\vee(x\wedge z)=a\vee0=a\ne b$ となり、分配律が破れる。部分群の束は一般に分配的でない（モジュラー束）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
