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

半年ぶりの記事です. 今回は, 数回にわたって Heyting 代数について書きたいと思います.

半順序集合と束

半順序集合から束

$\langle L, \le \rangle$ を半順序集合とします. すなわち $a, b, c \in L$ について

$a \le a$ (反射律)*1
$a \le b, b \le a \Rightarrow a = b$ (反対称律)
$a \le b, b \le c \Rightarrow a \le c$ (推移律)

が成り立つものとします.

$a, b \in L$ について

$a \le c, b \le c$
$(\forall x \in L)(a \le x, b \le x \Rightarrow c \le x)$

を満たす $c \in L$ が存在するとき, これを $a \vee b$ と書き, $a$ と $b$ の交わり(join)と言います. このような元は, 常に存在するとは限りませんが, 存在すれば一意であることは明らかです.

同様に $a, b \in L$ について

$c \le a, c \le b$
$(\forall x \in L)(x \le a, x \le b \Rightarrow x \le c)$

を満たす $c \in L$ が存在するとき, これを $a \wedge b$ と書き, $a$ と $b$ の結び(meet)と言います.

任意の $a, b \in L$ に対して, 常に $a \vee b$ と $a \wedge b$ が存在するとき, $L$ は束(lattice)であると言います.*2

束の結びと交わりについて, 以下の法則が成り立ちます.

$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 \wedge y) = x, x \wedge (x \vee y) = x$ (吸収法則)

これらのうち吸収法則が成り立つことについては少し難しいと思いますので, 片方だけ証明します.

定義から $x \le x \vee (x \wedge y)$ は明らかです. また $x \le x, x \wedge y \le x$ が成り立つので $x \vee (x \wedge y) \le x$ も成り立ちます. よって反対称律により $x \vee (x \wedge y) = x.$

これに以下の冪等法則を加えているケースもあります.
$x \vee x = x, x \wedge x = x$
しかしこれは
$x \vee x = x \vee (x \wedge (x \vee x)) = x$
のように吸収法則を 2 回使えば証明できるので必須ではありません.

束から半順序集合

集合 $L$ と, $L$ 上の演算 ${\vee : L \times L \to L, \wedge : L \times L \to L}$ の組 $\langle L, \vee, \wedge \rangle$ が, 上記の交換法則, 結合法則および吸収法則を満たすとき, やはり $L$ は束であると言います.

このとき, $L$ 上の関係 $\le$ を $a \le b \Leftrightarrow a \vee b = b$ で定義すると $\langle L, \le \rangle$ は半順序集合になります. 試しに推移律を示すと
${\begin{align} a \le b, b \le c \Rightarrow a \vee c &= a \vee (b \vee c) \\ &= (a \vee b) \vee c \\ &= b \vee c = c \end{align}}$
故, 定義により $a \le c.$