束論の勉強1：束の2通りの定義とそれらの同値性

　論理学方面の関心から束論について勉強したいと思うようになったので，このシリーズでまとめます．束は代数構造の一種で，論理の意味論を組むときに出てくるブール代数やハイティング代数などの代数構造は束として表されます．束について理解すると論理学の理解も深まると思われます．

　束には順序構造としての定義と，代数構造としての定義があります．これらを順番に見ていって，あとでそれらの定義の同値性を確認します．まずは順序構造の方からです．

　集合 $A$ 上の2項関係 $\leq$ が $A$ 上の半順序（partial order）であるとは，それが反射的・推移的・反対称的であることです．すなわち，任意の $a, b \in A$ に対して，

$a \leq a$
$a \leq b$ , $b \leq c \Rightarrow a \leq c$
$a \leq b$ , $b \leq a \Rightarrow a = b$

が成り立つことをいいます（ここで" $\Rightarrow$ "の前件に現れるカンマは「かつ」を表します．はてなブログの数式ではアンパサンドがうまく使えないので，今後もこのような書き方をします）．半順序が定義された集合 $A$ の部分集合 $S$ に対して， $S$ の下限 $i$ とは， $S$ の任意の元 $x$ について $i \leq x$ となるようなものの中で最大のものをいいます．同様に， $S$ の上限 $s$ とは， $S$ の任意の元 $x$ について $x \leq s$ となるようなものの中で最小のものです．

　半順序構造 $\langle A, \leq \rangle$ の部分集合 $S$ に対して， $S$ の下限をそのmeet（交わり）と呼び， $S$ の上限をそのjoin（結び）といいます． $S$ のmeetを $\bigwedge S$ と書き，joinを $\bigvee S$ と書きます．特に， $\bigwedge \{ a, b \}$ を $a \land b$ と書き， $\bigvee \{ a, b \}$ を $a \lor b$ と書きます．

　半順序構造 $\langle A, \leq \rangle$ が束（lattice）であるとは， $A$ の任意の有限部分集合がmeetとjoinをもつことをいいます． $\langle A, \leq \rangle$ が束である場合， $\varnothing$ は $A$ の有限部分集合なので， $\bigvee \varnothing$ ， $\bigwedge \varnothing$ が存在し，それぞれ $0$ ， $1$ と表されます． $0$ は $A$ の最小元， $1$ は $A$ の最大元です（ $0$ は〈空集合のどの要素についてもそれ以上であり，かつ，そのようなものの中で最小の $A$ の要素〉ですが，この連言肢のひとつ目の条件は空虚に満たされるので（ $A$ の任意の要素がそれを満たすので），要は $0$ は $A$ の最小の要素ということになります． $1$ についても同様の議論ができ， $1$ は $A$ の最大元となります）．ここで $\land$ と $\lor$ は $A$ 上の2項演算となります．ここまでが順序構造としての束の定義です．

　次に，代数構造としての束の定義に入ります． $A$ を集合とし， $\land$ と $\lor$ を $A$ 上の2項演算， $0$ と $1$ を $A$ の要素とします．構造 $\langle A, \land, \lor, 0, 1 \rangle$ が束であるとは，演算 $\land$ と $\lor$ が可換的かつ結合的で，吸収律をみたし， $0$ と $1$ がそれぞれ，両演算に関して双対的な零元と単位元となることです．すなわち，任意の $a, b \in A$ に対して，

$a \land b = b \land a$
$(a \land b ) \land c = a \land ( b \land c)$
$a \land ( a \lor b ) = a$
$a \land 0 = 0$
$a \land 1 = a$

および，上の5つの式の $\land$ と $\lor$ ， $0$ と $1$ を一気に入れ換えたものが成り立つことです．

　最後に，ふたつの定義の同値性を確認します．まず，順序構造としての束が，演算 $\land$ と $\lor$ に関して，代数構造としての束をなすことを見ましょう．まず，これらの演算は明らかに可換的です．次に， $x=(a \land b ) \land c$ とすると， $x \leq a \land b$ かつ $x \leq c$ であり，かつ，そのようなものの中で $x$ は最大です．ここで $x \leq a, x \leq b$ なので（ $\leq$ の推移性から）， $x \leq b \land c$ です（ $b$ 以下かつ $c$ 以下なので，大きくても $\{ b, c \}$ の下限以下）．ここで， $y \leq a$ かつ $y \leq b \land c$ なる $y$ が $x$ より真に大きいとします．このとき， $y$ は $a \land b$ 以下（上と同じ論法）かつ $c$ 以下であるのに $x$ より真に大きいことになり，これは $x$ のもとの最大性に反します．したがって， $x$ は $a$ 以下かつ $b \land c$ 以下なるものの中でも最大のものであり，したがって $a \land ( b \land c)$ に等しいです（ここで「 $x$ が $a$ 以下」などの表現は単に $x \leq a$ を意味し，「 $y$ が $x$ より真に大きい」とは $x \leq y$ かつ $x \neq y$ であることをいいます． $x$ が $S$ の最大元であることと任意の $t \in S$ に対して $x=t$ または $x \geq t$ となることの同値性を示すのに $\leq$ の反射性を， $y \in S$ に対して $x \neq y$ かつ $x \leq y$ となることが $x$ の $S$ における最大性と矛盾することを示すのに $\leq$ の反対称性を暗に用いています）．最大元の一意性（これは $\leq$ の反対称性から出ます）から，「逆の議論」は必要ありません． $\lor$ に関しても同様に示せます．吸収律に関しては， $a \leq a$ （反射性）かつ $a \leq a \lor b$ なので，あとは $a$ がそのようなものの中で最大のものであることを示せばよいですが， $x \leq a$ かつ $x \leq a \lor b$ とすると，連言肢の前半が既に $x \leq a$ ということを言っているのでこれも成り立ちます． $\land$ と $\lor$ を入れ換えたものに関しても同様です．さらに，順序構造としての束は最小・最大元をもつので，それぞれを $0$ ， $1$ とすれば， $0$ 以下の元は $0$ しかなく， $1$ は任意の $a \in A$ に対して $1 \geq a$ で $\{ a, 1 \}$ が最小元 $a$ をもつので，零元・単位元についてもOKです． $\lor$ についても同様です．したがって，順序構造としての束は代数構造としての束にもなります．

　逆に，代数構造としての束は， $a \leq b$ を $a = a \land b$ であることとして定めると， $\leq$ は半順序になり，この順序のもとで束をなします．まず， $a \land a = a \land (a \lor (a \land a))$ で（吸収律），右辺は再び吸収律によって $a$ に等しいので， $a \land a = a$ で（これを冪等律ともいいます．冪等律は $\lor$ についても成り立ちます）， $\leq$ は反射的です．また， $a = a \land b$ かつ $b = b \land c$ だとすると， $a = a \land (b \land c) = (a \land b ) \land c = a \land c$ なので，推移性も成り立ちます．反対称性に関しても， $a = a \land b$ かつ $b = b \land a$ とすると， $a = a \land b = b \land a = b$ となるので成り立ちます．よって， $\leq$ は半順序になります．

　次に，meetとjoinの存在です． $S = \{ x_1, x_2, \dots ,x_n \}$ に対して， $x_1 \land x_2 \land \dots \land x_n$ は（結合的なのでこのような書き方が許されます） $S$ のどの元をとってもそれ以下になります．なぜなら，可換性を有限回使って順番を入れ替えて冪等律を使えば $x_1 \land \dots \land x_n = x_1 \land \dots \land x_n \land x_k$ となるからです．そして， $x_1 \land \dots \land x_n$ はそのようなものとして最大です．実際， $x_1 \land \dots \land x_n = x_1 \land \dots \land x_n \land y$ なる $y$ でそのようなもの考えると， $y = y \land x_1$ で， $y = y \land x_2$ だから， $y = y \land x_1 \land x_2$ となり，これを $n$ まで続けると， $y = y \land x_1 \land \dots \land x_n= x_1 \land \dots \land x_n \land y = x_1 \land \dots x_n$ となります．空集合の下限としては $1$ をもってくればよいです（ $a = a \land 1$ ）．また， $x_k = x_k \land (x_1 \lor x_2 \lor \dots \lor x_n)$ です．なぜなら， $x_1 \lor \dots \lor x_n$ は可換性を有限回使って $x_k \lor ( x_1 \lor \dots \lor x_n)$ と変形でき，したがって吸収律が適用できるからです．また， $x_1 \lor \dots \lor x_n$ はそのようなものとして最小です．実際， $y = y \land (x_1 \lor \dots \lor x_n)$ なる $y$ でそのようなものを考えると，まず $x_k = x_k \land y(k = 1, \dots, n)$ です．ここで，吸収律から $y = y \lor (y \land x_k)$ で，これは先の式から $y = y \lor x_k$ と簡略化できます．各 $k$ について， $y$ に対するこのような代入を繰り返して並び替えると， $y = (x_1 \lor \dots \lor x_n) \lor y$ となり，これを使うと $y = (x_1 \lor \dots \lor x_n) \land y = (x_1 \lor \dots \lor x_n) \land ( (x_1 \lor \dots \lor x_n) \lor y) = (x_1 \lor \dots \lor x_n)$ となります．空集合の上限としては $0$ をもってくればよいです（ $0 = 0 \land a$ ）．かくして，代数構造としての束が順序構造としての束にもなることが分かりました．

　以上で，ふたつの定義の同値性が示されました．ちなみに，今回の定義における束は「有界束」とも呼ばれ，最大元と最小元をもつバージョンの束ですが，最大元や最小元をもたない束を考えることもあります．その場合，順序構造としての束については「空でない任意の有限部分集合がjoinとmeetをもつ」と定義を書き換え，代数構造としての束については単位元と零元に関するルールを抜けばよいです．

　次回は束の基本的な性質を確認していきます．その際には主に順序構造に関する束で考えていく予定です．