完備束
数学の一分野順序論における完備束(complete lattice)とは部分集合が常に上限と下限を持つ半順序集合のことである。
完備束は束の重要な例で順序集合論及び普遍代数の研究対象であり、数学及び計算機科学に多くの応用を持つ。
順序集合上の完備性には様々な異なる定義があるので注意を要する(例えば完備半順序 (CPO) は完備束とは異なる概念である)。特に重要な完備束のクラスとして完備ブール代数や完備ハイティング代数 (locale) がある。
半順序集合 (L,\le) の任意の部分集合が下限(最大下界)及び上限(最小上界)を持つとき、 (L,\le) を完備束という。
半順序集合 (L,\le) の部分集合 A に対し、
その下限を \bigwedge A と書き A の結び(meet)といい、
その上限を \bigvee A と書き A の交わり(join)という。
\bigwedge L は (L,\le) の最小元、 \bigvee L は (L,\le) の最大元となるので、完備束は有界束の特別なクラスである。
半順序集合において、任意の部分集合が上限を持つことと任意の部分集合が下限を持つこととは同値であり、これらは完備束であることとも同値である。
なので完備(上)半束(complete (upper) semi-lattice)及び完備下半束(complete lower semi-lattice)も完備束と同じ対象を表す。
ただし、準同型の定義が異なる(下記の写像の節を参照)。
完備束 L とその部分集合 M について、
Mの任意の部分集合の L での下限及び上限が全て M に属するとき、
M を L の完備部分束(complete sublattice)という。
上の条件を「任意の空でない部分集合」に取り替えたものは閉部分束(closed sublattice)と言われる。
(空でない)任意の有限束は完備束。
集合の冪集合 に包含関係で順序を入れたものは完備束になり、下限は集合の共通部分、上限は合併として与えられる。
単位区間 [0,1] 及び拡大実数直線(順序集合として互いに同型)は完備束。一般に全順序集合が完備束になることと順序位相でコンパクトになることは同値。
自然数全体に整除関係で順序を入れたものは完備束になる。 この順序集合は最小元として 1 を最大元として 0 を持つ。下限は最大公約数、上限は最小公倍数として与えられる。無限集合の上限が常に 0 なのに対し、下限は 1 より真に大きい値を持ち得る。自然数全体から 0 を除いたものは、整除関係のもとで完備束でない(が有界完備である)束をなす。
群の部分群全体は包含関係に関して完備束をなす。下限は共通部分として、上限は合併の生成する部分群として与えられ、最小元は単位群、最大元は全体となる。
同様に、加群の部分加群全体や環のイデアル全体などは包含関係で完備束をなす(より一般にある代数系の部分代数系は包含関係で完備束をなす)。
位相空間の開集合全体は包含関係で完備束となる。上限は集合としての合併で、下限は共通部分の内部として与えられる。
集合上の位相構造全体は開集合系間の包含関係により完備束となる。下限は開集合系の共通部分を取ることで、上限は開集合系の合併から生成される開集合系として与えられる。
実ベクトル空間の凸部分集合全体は包含関係で完備束をなす。下限は共通部分として上限は合併の凸包として与えられる。
実又は複素ヒルベルト空間の閉部分空間全体は包含関係で完備(可補)束をなす。下限は共通部分として上限は合併の生成する部分空間の閉包として与えられる。
フォン・ノイマン環上の直交射影全体は完備束をなす。
集合上の推移的関係全体は完備束をなす。
集合上の同値関係全体は完備束をなす。
集合上の完備束への関数全体は完備束をなす。
完備束の直積は再び完備束になる。
完備束の間の下限及び上限を保つ写像を完備準同型(完備束準同型)(complete homomorphisms(complete lattice homomorphisms))という。
正確に述べると、
完備束 L, M の間の写像 f\colon L\to M が完備準同型であるとは
f(\bigwedge A) = \bigwedge\{f(a)\mid a\in A\} 及び
f(\bigvee A) = \bigvee\{f(a)\mid a\in A\}
が L の任意の部分集合 A に対して満たすことをいう。
このような写像は自動的に単調増加写像となる。
この定義はしばしば強すぎることがあり、その場合は上限を保存する写像もしくは下限を保存する写像を考える。それらは各々完備(上)半束準同型(complete (upper) semi-lattices homomorphisms)及び完備下半束準同型(complete lower semi-lattices homomorphisms)と呼ばれる。
完備半束準同型には以下の様な特徴付けが存在する。
完備束間の写像が完備上半束準同型となることとガロア接続(Galois connection)の下随伴(lower adjoint)となることは同値。
同様に、完備束間の写像が完備下半束準同型となることとガロア接続の上随伴(upper adjoint)となることは同値。(このようなガロア接続は完備準同型に対し一意的に定まる)
完備半束の圏における自由対象を自由完備半束(free complete semilattice))という。
集合 X と完備半束 F_X 及びその間の写像 i\colon X\to F_X について、F_X が X を生成系とする自由完備半束であるとは次の普遍性を満たすことである。
任意の完備半束 L 及び写像 j\colon X\to L に対し、完備半束準同型 j^*\colon F_X\to L が一意的に存在し j=j^*\circ i となる。
任意の集合に対しそれの生成する自由完備半束を具体的に構成することができる。
即ち、
(二点以上の元を含む)集合 X に対し、その冪集合 \mathfrak{P}(X) は包含関係を順序として、X を生成系とする自由完備半束となる(但し、写像 i\colon X\to \mathfrak{P}(X) は各元をその元のみからなる一点集合に写す写像)。
普遍性は次のように言える。
完備半束 L 及び写像 j\colon X\to L が与えられたとき、
j^*(A):=\bigvee\{j(a)\colon a\in A\}
とすれば j^*\colon\mathfrak{P}(X)\to L は j=j^*\circ i を満たす完備半束準同型となる。
完備束と完備準同型の圏における同様の問題はより困難である。
集合 X が三点以上の要素を含むとき X で生成される完備束はいくらでも大きい濃度を取りうるため、 X で生成される自由完備束は存在し得ない。
但し(空でない)集合 X が高々二点しか含まないとき X で生成される自由完備束は存在する(それは二点ブール代数及び一点集合である)。
半順序集合に対して、それから生成される「最大の」完備束を考えることは一般には出来ない(なぜなら、離散順序集合に対してそれを考えればそれは自由完備束となるから)。
しかし、半順序集合に対して、それから生成される「最小の」完備束を考えることはできる。
これを具体的に構成する方法がホルブルク・マクニール によりデデキント切断を一般化することで与えられてる(デデキント・マクニール完備化)。
完備半束に対するデデキント・マクニール完備化は完備半束を集合族(と包含関係及び合併のなす完備半束)として表現していると思える。この構成を任意の閉包作用素に一般化することが出来る。
すなわち、
完備束 P 上に閉包作用素 cl\colon P\to P (つまり、 p\le cl(p) 、cl\circ cl=cl 、p\le q\rightarrow cl(p)\le cl(q) を満たす写像)が与えられたとき、 cl の像 cl(P) は再び完備束となる。
デデキント・マクニール完備化は完備束を冪集合上の閉包作用素の像として与えていると見なすことが出来る。
クナスタ・タルスキの定理によると完備束から自分自身への単調写像の不動点全体は再び完備束になる。これは閉包作用素の場合の結果の一般化とみなせる。