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

前回に引き続き Heyting 代数の性質を見ていきます.

最小元 $0$ を持つ Heyting 代数 $H$ において $\neg x = x \to 0$ と定義し, これを $x$ の擬補元と言うのでした. 今回は擬補元の性質を中心に見ていきます.

1. $x \le y$ ならば $\neg y \le \neg x.$
$\neg y = y \to 0 \le x \to 0 = \neg x.$

2. $x \wedge \neg x = 0.$
$\neg x$ の定義より明らか.

3. $x \le \neg \neg x$
2. より $x \le \neg x \to 0 = \neg \neg x.$

4. $\neg x = \neg \neg \neg x.$
3. で $x$ を $\neg x$ で置き換えると $\neg x \le \neg \neg \neg x,$ 一方で 3. に 1. を適用すると $\neg \neg \neg x \le \neg x,$ よって $\neg x = \neg \neg \neg x.$

5. $\neg(x \vee y) = \neg x \wedge \neg y.$
${\begin{align} \neg(x \vee y) &= (x \vee y) \to 0 \\ &= (x \to 0) \wedge (y \to 0) \\ &= \neg x \wedge \neg y. \end{align}}$

6. $\neg(x \wedge y) = \neg \neg(\neg x \vee \neg y).$
これは長いので証明は省略.
4., 5. と前記事の 7. を使えば証明可能.

正則性

さて, $x \le \neg \neg x$ は常に成り立つのですが, 等号 $x = \neg \neg x$ に関しては常に成り立つとは限りません. $x \in H$ については, 以下の 2 条件が同値であることが分かります.

$x = \neg \neg x.$
$x = \neg y$ となる $y \in H$ が存在する.

$1. \Rightarrow 2.$ は明らかですが, $2. \Rightarrow 1.$ については
$x = \neg y \Rightarrow \neg \neg x = \neg \neg \neg y = \neg y = x.$

$x \in H$ が上のいずれかの条件(したがって両方)を満たすとき, $x$ は正則(regular)であると言います. もし全ての $x \in H$ が正則ならば, $H$ は Boole 代数であることが, 以下のように示されます.

$y = \neg(x \vee \neg x)$ と置きます. 定義により $y \wedge (x \vee \neg x) = 0$ です. 分配則により
$0 = y \wedge (x \vee \neg x) = (y \wedge x) \vee (y \wedge \neg x)$
なので $y \wedge x = 0$ と $y \wedge \neg x = 0$ がともに成り立ちます. 故に $y \le x \to 0 = \neg x$ かつ $y \le \neg x \to 0 = \neg \neg x = x$ が成り立つので $y \le \neg x \wedge x = 0,$ すなわち $y = 0.$
よって $x \vee \neg x = \neg \neg(x \vee \neg x) = \neg y = \neg 0 = 1.$
以上により $\neg x$ は $x$ の補元となり, $H$ は Boole 代数である.