直観主義論理の入り口～Heyting 代数～(その 6) - Red cat の数学よもやま話・新装開店

前回まで束に関する一般的な性質を見てきましたが, 今回からいよいよ Heyting 代数の話をします.

Heyting 代数の定義

$L$ は有界束とします. このとき $L$ が Heyting 代数であるとは, $L$ が圏*1として冪を持つことを言います. すなわち函手
$(-) \wedge a : L \to L$
が右随伴函手
$a \to (-) : L \to L$
を持つことを言います.

このとき, 圏の一般論から $(-) \wedge a$ が余極限を保つこと, 特に
$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
が成り立つので, $L$ は分配束であることが分かります.

$c = a \to b$ に関しては
$c \wedge a \le b$ かつ $x \wedge a \le b \Leftrightarrow x \le c$
で特徴づけることができます. つまり圏の言葉を使わずに定義するならば, 有界束 $L$ は
$\{ x | x \wedge a \le b \}$
に常に最大元が存在するときに Heyting 代数であるといい, $\max \{ x | x \wedge a \le b \}$ のことを $a \to b$ と書きます. これを $a$ の $b$ に対する相対擬補元と言います.

特に $a$ の $0$ に対する相対擬補元 $a \to 0$ を単に擬補元と言い, $\neg a$ と書きます.

Boole 代数

Heyting 代数の性質を細かく見る前に, Heyting 代数より真に強い概念*2である Boole 代数について見ていきたいと思います.

相補律

有界束 $L$ が相補律を満たすとは, 任意の $x \in L$ に対して
$x \wedge x' = 0, x \vee x' = 1$
を満たす $x' \in L$ が存在することを言います. このとき $x'$ は $x$ の補元であると言います. 一般には補元は一意ではありません. 相補律は自己双対な概念です.

Boole 代数

有界束 $L$ が分配束でかつ相補律を満たすとき, $L$ は Boole 代数(もしくは Boole 束)であると言います. Boole 代数においては, $x', x''$ がともに $x$ の補元ならば
${\begin{align} x' &= x' \wedge 1 \\ &= x' \wedge (x \vee x'') \\ &= (x' \wedge x) \vee (x' \wedge x'') \\ &= 0 \vee (x' \wedge x'') = x' \wedge x'' \end{align}}$
が成り立ち, 同様に $x'' = x' \wedge x''$ も示せますので, $x' = x''$ が成り立ちます. すなわち, 補元は一意に決まります. したがって, Boole 代数では $x$ の補元を $\neg x$ と書くのが習わしです.

$\neg x$ の補元の一意性から $\neg \neg x = x$ が成り立ちます. つまりある元を補元に移すという写像は対合になっています.

de Morgan の法則

$\neg(a \vee b) = \neg a \wedge \neg b, \neg(a \wedge b) = \neg a \vee \neg b$
は de Morgan の法則として有名です. 証明は
${\begin{align} (a \vee b) \wedge (\neg a \wedge \neg b) &= ( (a \wedge \neg a) \vee (\neg a \wedge b) ) \wedge \neg b \\ &= ( 0 \vee (\neg a \wedge b) ) \wedge \neg b \\ &= (\neg a \wedge b) \wedge \neg b \\ &= \neg a \wedge (b \wedge \neg b) \\ &= \neg a \wedge 0 = 0, \end{align}}$
${\begin{align} (a \vee b) \vee (\neg a \wedge \neg b) &= a \vee ( b \vee (\neg a \wedge \neg b) ) \\ &= a \vee ( (\neg a \vee b) \wedge (b \vee \neg b) ) \\ &= a \vee ( (\neg a \vee b) \wedge 1 ) \\ &= a \vee (\neg a \vee b) \\ &= (a \vee \neg a) \vee b \\ &= 1 \vee b = 1. \end{align}}$
もう一方はその双対です.

$a \le b$ ならば $a \vee b = b$ なので de Morgan の法則により
$\neg a \wedge \neg b = \neg(a \vee b) = \neg b$
が成り立つので $\neg b \le \neg a$ が成り立ちます. つまり, 補元を取るという操作は順序を逆にします.

直交相補束

有限次元ベクトル空間 $V$ の部分空間の全体は有界束になります. $W_1 \subset V$ と $W_2 \subset V$ を部分空間とするとき, 結びは $W_1 \cap W_2$ , 交わりは $W_1 + W_2$ になります.
$W'$ が $W$ の補元であることは $V = W \oplus W'$ と表せますが, 一般に補元は一意でないことは次のような例を考えるとわかります.

$V = \mathbb{R}^2, W = \{ (x, 0) | x \in \mathbb{R} \}, W' = \{ (0, y) | y \in \mathbb{R} \}, W'' = \{ (y, y) | y \in \mathbb{R} \}$
とおくと, 明らかに $V = W \oplus W'$ ですが, 一方で任意の $(x, y) \in V$ は
$(x, y) = (x - y, 0) + (y, y) \in W + W''$
と表すことができ, また $W \cap W'' = \{\boldsymbol{0}\}$ なので $V = W \oplus W''$ も成り立ちます.

しかし, $V$ に内積を与えたとき, $W \subset V$ に対して
$W^\perp = \{ \boldsymbol{v} \in V | (\forall \boldsymbol{w} \in W)( (\boldsymbol{v}, \boldsymbol{w}) = 0 )\}$
とおけば
$V = W \oplus W^\perp, (W^\perp)^\perp = W, W_1 \subset W_2 \Rightarrow {W_2}^\perp \subset {W_1}^\perp$
が成り立ちます.

このことを一般化して, 有界束 $L$ について $\perp : L \ni a \mapsto a^\perp \in L$ が

$a \wedge a^\perp = 0, a \vee a^\perp = 1$
$(a^\perp)^\perp = a$
$a \le b \Rightarrow b^\perp \le a^\perp$

を満たしているとき, $\langle L, \perp \rangle$ を直交相補束と言います. 一般に有界束 $L$ の直交相補束としての構造は複数入る可能性があります(上記の例では, 内積の取り方によって異なる直交相補束としての構造が考えられる).

直交相補束においては
$a^\perp \le (a \wedge b)^\perp, b^\perp \le (a \wedge b)^\perp$
であり, $a^\perp \le x, b^\perp \le x$ ならば $x^\perp \le a, x^\perp \le b$ だから $x^\perp \le a \wedge b$ であり, よって $(a \wedge b)^\perp \le x$ であるから $(a \wedge b)^\perp = a^\perp \vee b^\perp$ が成り立ちます. 同様に $(a \vee b)^\perp = a^\perp \wedge b^\perp$ も成り立ちます(de Morgan の法則).

Boole 代数は明らかに直交相補束です.

*1:束演算から定義される順序を導入して, 順序集合がなす小さな圏と考える.

*2:このことは後で証明します.