読者です 読者をやめる 読者になる 読者になる

Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

直観主義論理の入り口~Heyting 代数~(その 9)

前回に引き続き 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 条件が同値であることが分かります.

  1. x = \neg \neg x.
  2. 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 = 0y \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 xx の補元となり, H は Boole 代数である.

Heyting 代数にはまだまだ面白い性質があります(6. のような弱い形での de Morgan の法則が強い意味で成り立つための様々な条件の同値性など)が, 一般論はここまでにして, 次回, 完備 Heyting 代数のお話をします.