束と完備束 | 数学の基礎 | 天游ヶ丘数理学院

1 順序から定まる束

上限と下限は§E1.8 定義 2.1の意味で用いる。半順序集合では、存在する上限と下限は一意である（§E1.8 命題 2.3）。したがって、次の記号は値を一意に定める。

定義 1.1. $(L,\leq)$ を半順序集合とする。任意の $x,y\in L$ に対して集合 $\{x,y\}$ の上限と下限が存在するとき、 $(L,\leq)$ を束 (lattice) という。

$\{x,y\}$ の上限を $x\vee y$ と書いて $x$ と $y$ の結び (join) といい、下限を $x\wedge y$ と書いて $x$ と $y$ の交わり (meet) という。

注意 1.2. 半順序集合 $L$ の双対順序（§E1.8 定義 3.3）はふたたび半順序であり（§E1.8 命題 3.4）、部分集合の上限と下限、および最大元と最小元を交換する（§E1.8 注意 3.5）。したがって $L$ が束であることと $L^{\mathrm{op}}$ が束であることは同値であり、この対応のもとで $\vee$ と $\wedge$ が入れ替わる。順序だけを用いて証明した主張を $L^{\mathrm{op}}$ へ適用し、記号を入れ替えたものがその双対な主張である。以下で「双対に」と書くときは、この手続きを指す。

結びと交わりの記号は、順序を忘れても計算することができる二項演算である。上限と下限の定義から、次が従う。

命題 1.3. $(L,\leq)$ を束とし、 $x,y,z,u,l\in L$ とする。

$x\leq x\vee y$ 、 $y\leq x\vee y$ 、 $x\wedge y\leq x$ 、 $x\wedge y\leq y$ である。
$x,y\leq u$ ならば $x\vee y\leq u$ であり、 $l\leq x,y$ ならば $l\leq x\wedge y$ である。
$x\leq y$ 、 $x\vee y=y$ 、 $x\wedge y=x$ の三つは互いに同値である。
$\{x,y,z\}$ は上限 $(x\vee y)\vee z$ と下限 $(x\wedge y)\wedge z$ をもつ。

証明.(1)と(2)は、 $x\vee y$ が $\{x,y\}$ の上限であること、および $x\wedge y$ が $\{x,y\}$ の下限であることの言い換えである。

$x\leq y$ とすると、 $y\leq y$ とあわせて(2)から $x\vee y\leq y$ であり、(1)から $y\leq x\vee y$ である。反対称律により $x\vee y=y$ である。逆に $x\vee y=y$ ならば、(1)により $x\leq x\vee y=y$ である。 $x\leq y$ と $x\wedge y=x$ の同値は、注意 1.2によりこの同値を $L^{\mathrm{op}}$ へ適用して得られる。よって(3)が成り立つ。

(1)と推移律により $x,y\leq(x\vee y)\vee z$ であり、 $z\leq(x\vee y)\vee z$ である。 $u$ を $\{x,y,z\}$ の上界とすると、(2)により $x\vee y\leq u$ であり、ふたたび同じ性質により $(x\vee y)\vee z\leq u$ である。したがって $(x\vee y)\vee z$ は $\{x,y,z\}$ の上限であり、双対に $(x\wedge y)\wedge z$ は $\{x,y,z\}$ の下限である。▨

例 1.4.

集合 $X$ に対して、 $(\mathcal P(X),\subseteq)$ は束である。 $A\vee B=A\cup B$ 、 $A\wedge B=A\cap B$ である。
正の整数全体を整除関係で順序づけると束になる。 $a\vee b=\operatorname{lcm}(a,b)$ 、 $a\wedge b=\gcd(a,b)$ である。
全順序集合 $(T,\leq)$ は束である。 $x\vee y=\max\{x,y\}$ 、 $x\wedge y=\min\{x,y\}$ である。

2 代数法則と順序の復元

束から得られる二つの演算は、次の法則を満たす。逆に、これらの法則だけから順序を復元することができる。

定理 2.1. 集合 $L$ の上に二項演算 $\vee$ と $\wedge$ があるとする。次の二つの条件は同値である。

$L$ に束の順序があり、 $\vee$ と $\wedge$ はその結びと交わりである。
任意の $x,y,z\in L$ に対して、次の交換律、結合律、冪等律、吸収律が成り立つ。 $\begin{aligned} 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\vee(x\wedge y)&=x,&x\wedge(x\vee y)&=x. \end{aligned}$

(2)から(1)の順序を復元するときは、

x\leq y\iff x\vee y=y

と定める。この条件は $x\wedge y=x$ と同値である。逆に、 $(L,\leq)$ が束であるとき、その結びから同じ式によって定まる順序は $\leq$ 自身である。すなわち、順序から演算を作る対応と演算から順序を作る対応は互いに逆である。

証明.(1)を仮定する。交換律と冪等律は、 $\{x,y\}=\{y,x\}$ と $\{x,x\}=\{x\}$ の上限・下限の一意性から従う。命題 1.3 (4)により $(x\vee y)\vee z$ は $\{x,y,z\}$ の上限であり、同じ主張を $y$ 、 $z$ 、 $x$ へ適用すると $(y\vee z)\vee x$ は $\{y,z,x\}=\{x,y,z\}$ の上限である。交換律によりこれは $x\vee(y\vee z)$ に等しいので、上限の一意性から結合律が従う。交わりの結合律も、 $(x\wedge y)\wedge z$ と $x\wedge(y\wedge z)$ がどちらも $\{x,y,z\}$ の下限であることから従う。 $x\wedge y\leq x$ なので、 $x$ は $x$ と $x\wedge y$ の上界である。また、この二元集合のどの上界も、その元 $x$ 以上である。したがって $x$ は最小上界であり、 $x\vee(x\wedge y)=x$ である。双対に $x\wedge(x\vee y)=x$ である。

(2)を仮定し、 $x\leq y$ を $x\vee y=y$ によって定める。冪等律により $x\leq x$ である。 $x\leq y$ かつ $y\leq x$ ならば、交換律により $y=x\vee y=y\vee x=x$ である。 $x\leq y$ かつ $y\leq z$ ならば、

x\vee z=x\vee(y\vee z)=(x\vee y)\vee z=y\vee z=z

なので $x\leq z$ である。よって $\leq$ は半順序である。

$x\vee y=y$ ならば、吸収律により $x\wedge y=x\wedge(x\vee y)=x$ である。逆に $x\wedge y=x$ ならば、もう一方の吸収律と交換律により $x\vee y=(x\wedge y)\vee y=y$ である。したがって二つの順序条件は同値である。

$x\leq x\vee y$ は $x\vee(x\vee y)=x\vee y$ から従い、 $y\leq x\vee y$ も同様である。 $x,y\leq u$ ならば、

(x\vee y)\vee u=x\vee(y\vee u)=x\vee u=u

なので $x\vee y\leq u$ である。よって $x\vee y$ は $\{x,y\}$ の上限である。交わりについて双対の計算を行うと、 $x\wedge y$ は $\{x,y\}$ の下限である。したがって(1)が成り立ち、演算から作った順序について結びと交わりを取り直すと元の $\vee$ と $\wedge$ に戻る。 $(L,\leq)$ が束であるとき、その結びから $x\vee y=y$ によって定まる関係が $\leq$ に一致することは命題 1.3 (3)による。▨

注意 2.2.定理 2.1により、束を半順序集合として定義しても、二つの二項演算をもつ代数系として定義しても、得られる対象は同じである。順序を用いる証明では最小上界・最大下界としての特徴づけを用い、等式を用いる証明では四種類の法則を用いることができる。

注意 2.3. 分配律

x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)

は定理 2.1 (2)の四種類の法則から従わない。五元集合 $L=\{0,a,b,c,1\}$ に、 $0$ を最小元、 $1$ を最大元とし、 $a$ 、 $b$ 、 $c$ を互いに比較不能とする順序を入れる。 $a$ 、 $b$ 、 $c$ のうち相異なる二つを取ると、その上界は $1$ だけ、下界は $0$ だけであるから、 $L$ は束であり、この二つの結びは $1$ 、交わりは $0$ である。したがって

a\wedge(b\vee c)=a\wedge1=a, \qquad (a\wedge b)\vee(a\wedge c)=0\vee0=0

であり、 $a\ne0$ から分配律は成り立たない。冪集合の包含束、正の整数全体の整除束、全順序集合の束、および有限集合または補集合が有限である自然数の部分集合全体の包含束は、いずれも分配律を満たす。しかし、上の五元束が示すように、分配律は束の定義に含まれない条件であり、「Boolean 代数」はこれを追加の公理として要求する。

3 有界束と完備束

二元について上限と下限が存在しても、空集合や無限部分集合について上限と下限が存在するとは限らない。空集合の上限は最小元であり、空集合の下限は最大元である。この点を含めて有界性と完備性を定義する。

定義 3.1. 束 $(L,\leq)$ が最小元 $0$ と最大元 $1$ をもつとき、 $L$ を有界束 (bounded lattice) という。最小元を零元 (bottom element)、最大元を単位元 (top element) ともいう。

任意の $x\in L$ に対して $0\leq x\leq1$ であるから、命題 1.3 (3)により

x\vee0=x,\quad x\vee1=1, \qquad x\wedge0=0,\quad x\wedge1=x

が成り立つ。すなわち $0$ は $\vee$ の、 $1$ は $\wedge$ の§E1.4 定義 2.4の意味での単位元である。

定義 3.2. 半順序集合 $(L,\leq)$ のすべての部分集合 $A\subseteq L$ に上限と下限が存在するとき、 $L$ を完備束 (complete lattice) という。 $A$ の上限を $\bigvee A$ 、下限を $\bigwedge A$ と書き、それぞれ $A$ の任意の結び (arbitrary join) と任意の交わり (arbitrary meet) という。

完備束では、二元部分集合の上限と下限が結びと交わりを与えるので、 $L$ はまず束である。さらに

0=\bigvee\emptyset=\bigwedge L, \qquad 1=\bigwedge\emptyset=\bigvee L

である。したがって、完備束は必ず有界束である。

命題 3.3. 半順序集合 $L$ について、次の条件は同値である。

$L$ は完備束である。
すべての $A\subseteq L$ に $\bigvee A$ が存在する。
すべての $A\subseteq L$ に $\bigwedge A$ が存在する。

(2)が成り立つとき、

\bigwedge A=\bigvee\{x\in L\mid \forall a\in A,\ x\leq a\}

である。(3)が成り立つときは双対な式で $\bigvee A$ を得る。

証明.(1)から(2)と(3)は定義による。(2)を仮定し、 $B=\{x\in L\mid \forall a\in A,\ x\leq a\}$ とおく。 $b\in B$ ならば、各 $a\in A$ は $B$ の上界なので $b\leq\bigvee B\leq a$ である。したがって $\bigvee B$ は $A$ の下界である。任意の下界 $l$ は $B$ の元なので $l\leq\bigvee B$ である。よって $\bigvee B=\bigwedge A$ であり、(2)から(1)が従う。(3)から(1)は、注意 1.2により同じ議論を $L^{\mathrm{op}}$ へ適用して従う。▨

上限だけから下限を構成するこの手続きは、poset の部分集合に上界全体と下界全体を対応させて完備束を作る「Dedekind–MacNeille 完備化」で用いる。

例 3.4. 代表的な束における完備性を比較する。

$(\mathcal P(X),\subseteq)$ は完備束である。 $\mathcal A\subseteq\mathcal P(X)$ に対して、 $\bigvee\mathcal A=\bigcup\mathcal A$ 、 $\bigwedge\mathcal A=\bigcap\mathcal A$ である。ただし、 $\mathcal A=\emptyset$ のときは $\bigcap\emptyset=X$ と解釈する。
正の整数全体の整除による束は完備束ではない。素数全体は共通の倍数をもたないので、上限をもたない。また、最大元も存在しない。一方、空でない部分集合 $A$ については、 $A$ の共通の約数全体 $D$ は $1$ を含み、 $A$ の一つの元の約数からなるので有限である。二つの共通の約数の最小公倍数もまた共通の約数であるから、 $D$ の元全体の最小公倍数は $D$ に属し、 $D$ のすべての元で割り切られる。これが $A$ の下限、すなわち最大公約数である。したがって命題 3.3 (3)が破れているのは $A=\emptyset$ の場合だけであり、この条件から空集合を除くことができない。
整数全体 $\mathbb Z$ は通常の順序について束であるが、有界束でも完備束でもない。空でない有限部分集合の上限と下限は最大値と最小値であるが、 $\mathbb Z$ 自身には上限も下限も存在しない。
空でない有限な全順序集合は完備束である。空でない部分集合は最大元と最小元をもち、空集合については全体の最小元と最大元が上限と下限になる。
集合 $X$ の部分集合のうち、有限であるか補集合が有限であるもの全体を $\mathrm{FC}(X)$ とおく。有限集合どうしの合併は有限であり、少なくとも一方の補集合が有限である二つの集合の合併は、その補集合が有限集合に含まれるので補有限である。したがって $\mathrm{FC}(X)$ は二元の和集合で閉じ、帰納法により有限合併で閉じている。一方が有限である二つの集合の共通部分は有限であり、補集合がともに有限である二つの集合の共通部分は、その補集合が有限集合の合併になるので補有限である。したがって $\mathrm{FC}(X)$ は二元の共通部分で閉じ、帰納法により有限共通部分で閉じている。 $\emptyset$ と $X$ は $\mathrm{FC}(X)$ に属する。和集合と共通部分は $\mathcal P(X)$ における上限と下限であるから、 $\mathrm{FC}(X)$ は包含順序について最小元 $\emptyset$ と最大元 $X$ をもつ有界束である。ここで $X=\mathbb N_{\geq 0}$ とすると、この有界束は完備束ではない。偶数全体 $E$ を含む $\mathrm{FC}(\mathbb N_{\geq 0})$ の元は補集合が有限であり、 $E$ に属さない元を無限に含むので、そのうちの一つを取り除いてもふたたび $E$ を含む $\mathrm{FC}(\mathbb N_{\geq 0})$ の元になる。したがって一元集合 $\{2k\}$ （ $k\in\mathbb N_{\geq 0}$ ）の全体は上限をもたない。整数全体の例とあわせると、束、有界束および完備束の三つの条件は順に真に強い。

4 束の構造を保つ写像

束の間の準同型は、演算を保つ写像という§E1.6 定義 1.1の考え方を二つの演算へ適用したものである。保つ演算の範囲に応じて、次の三種類を区別する。

定義 4.1. 束 $L$ 、 $M$ の間の写像 $f:L\to M$ が、すべての $x,y\in L$ に対して

f(x\vee y)=f(x)\vee f(y), \qquad f(x\wedge y)=f(x)\wedge f(y)

を満たすとき、 $f$ を束準同型 (lattice homomorphism) という。

$L$ 、 $M$ が有界束であり、さらに $f(0_L)=0_M$ と $f(1_L)=1_M$ を満たす束準同型を有界束準同型 (bounded lattice homomorphism) という。 $L$ 、 $M$ が完備束であり、すべての $A\subseteq L$ に対して

f\!\left(\bigvee A\right)=\bigvee f(A), \qquad f\!\left(\bigwedge A\right)=\bigwedge f(A)

を満たす写像を完備束準同型 (complete lattice homomorphism) という。

命題 4.2. 束準同型は単調写像である。完備束準同型は有界束準同型であり、とくに束準同型である。

証明. $x\leq y$ とする。命題 1.3 (3)により $x\vee y=y$ なので、

f(x)\vee f(y)=f(x\vee y)=f(y)

である。 $M$ において命題 1.3 (3)をふたたび用いると $f(x)\leq f(y)$ である。よって $f$ は単調である。

$f$ を完備束準同型とする。二元集合に対する任意の結びと交わりを保つので、 $f$ は束準同型である。また、 $0_L=\bigvee\emptyset$ 、 $1_L=\bigwedge\emptyset$ であり、 $f(\emptyset)=\emptyset$ なので、任意演算を保つ条件から $f(0_L)=0_M$ と $f(1_L)=1_M$ が従う。▨

注意 4.3. 単調写像が束準同型であるとは限らない。二元束 $\mathbf 2=\{0<1\}$ を取り、 $f\colon\mathcal P(\{p,q\})\to\mathbf 2$ を、 $f(\{p,q\})=1$ 、それ以外の元では $f=0$ によって定める。 $f(X)=1$ となるのは $X=\{p,q\}$ のときに限り、 $\{p,q\}$ を含む $\mathcal P(\{p,q\})$ の元は $\{p,q\}$ だけであるから、 $f$ は単調である。一方、 $f(\{p\}\vee\{q\})=f(\{p,q\})=1$ であるが $f(\{p\})\vee f(\{q\})=0\vee0=0$ なので、 $f$ は結びを保たない。したがって、単調であることから束準同型であることは従わない。

束準同型が零元と単位元を自動的に保つとも限らない。三元鎖 $M=\{0<a<1\}$ を取り、 $f\colon\mathbf 2\to M$ を $f(0)=f(1)=a$ によって定める。この定値写像は二項の結びと交わりを保つが、 $f(0)=a\ne0$ かつ $f(1)=a\ne1$ なので、零元も単位元も保たない。このため、束準同型と有界束準同型を区別する。

有界束準同型が任意の結びと交わりを保つとも限らない。 $A_n=\{k\in\mathbb N_{\geq 0}\mid k\geq n\}$ とし、包含順序を入れた完備鎖

L=\{\emptyset\}\cup\{A_n\mid n\in\mathbb N_{\geq 0}\}

から $\mathbf 2$ への写像を、 $f(\emptyset)=0$ 、 $f(A_n)=1$ によって定める。 $L$ は包含について鎖である。 $S=\emptyset$ の上限は $\emptyset$ 、下限は $\mathbb N_{\geq 0}$ である。 $S\subseteq L$ が空でないとき、 $\mathbb N_{\geq 0}$ の空でない部分集合が最小元をもつことから、 $S$ の上限は、 $S$ が $\emptyset$ 以外の元をもつならば $S$ に現れる添字が最小である $A_n$ 、 $S=\{\emptyset\}$ ならば $\emptyset$ である。 $S$ の下限は、 $S$ が $\emptyset$ を含むか $S$ に現れる添字が無限個であるならば $\emptyset$ 、そうでないならば $S$ に現れる添字が最大である $A_n$ である。よって $L$ は完備束であり、 $\emptyset$ と $\mathbb N_{\geq 0}$ がその零元と単位元である。 $\emptyset$ は $L$ の最小元であり他の元はすべて $1$ へ送られるので $f$ は単調であり、 $L$ と $\mathbf 2$ はいずれも鎖であって二元の結びと交わりは大きい方と小さい方であるから、 $f$ は二項の結びと交わりを保つ。 $f(\emptyset)=0$ と $f(\mathbb N_{\geq 0})=1$ から最小元と最大元も保つ。一方、 $\bigwedge_{n\in\mathbb N_{\geq 0}}A_n=\bigcap_{n\in\mathbb N_{\geq 0}}A_n=\emptyset$ であるから $f\!\left(\bigwedge_{n\in\mathbb N_{\geq 0}}A_n\right)=f(\emptyset)=0$ であり、 $\bigwedge_{n\in\mathbb N_{\geq 0}}f(A_n)=1$ とは異なる。したがって $f$ は任意の交わりを保たない。このため、有界束準同型と完備束準同型も区別する。

問題 4.4. 写像 $g:X\to Y$ に対して、逆像写像

g^{-1}:\mathcal P(Y)\longrightarrow\mathcal P(X), \qquad A\longmapsto g^{-1}(A)

が完備束準同型であることを証明せよ。

解答.

$\mathcal A\subseteq\mathcal P(Y)$ とする。元 $x\in X$ について、

x\in g^{-1}\!\left(\bigcup\mathcal A\right) \iff g(x)\in\bigcup\mathcal A \iff \exists A\in\mathcal A,\ x\in g^{-1}(A)

なので、 $g^{-1}(\bigcup\mathcal A)=\bigcup_{A\in\mathcal A}g^{-1}(A)$ である。同様に、

x\in g^{-1}\!\left(\bigcap\mathcal A\right) \iff \forall A\in\mathcal A,\ x\in g^{-1}(A)

なので、 $g^{-1}(\bigcap\mathcal A)=\bigcap_{A\in\mathcal A}g^{-1}(A)$ である。空の族についても、 $g^{-1}(\emptyset)=\emptyset$ と $g^{-1}(Y)=X$ が成り立つ。例 3.4の演算の記述により、逆像写像は任意の結びと交わりを保つ完備束準同型である。▨

§E1.9束と完備束

1 順序から定まる束

2 代数法則と順序の復元

3 有界束と完備束

4 束の構造を保つ写像

参考文献

前提記事