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

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

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

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

今回は Boole 代数に関する大事な性質について見ていきます.

Boole 代数は Heyting 代数である

補題 {x \wedge a \le b \Leftrightarrow x \le \neg a \vee b.}

(証明)
{(\Rightarrow)}
{\begin{align}
x &=   x \wedge 1 \\
  &=   x \wedge (\neg a \vee a) \\
  &=   (x \wedge \neg a) \vee (x \wedge a) \\
  &\le (x \wedge \neg a) \vee b \le \neg a \vee b.
\end{align}}

{(\Leftarrow)}
{\begin{align}
x \wedge a &\le x \wedge (a \vee b) \\
           &\le (\neg a \vee b) \wedge (a \vee b) \\
           &=   (\neg a \wedge a) \vee b \\
           &=   0 \vee b = b. \Box
\end{align}}

定理 Boole 代数は Heyting 代数である.

(証明)
{\begin{align}
(\neg a \vee b) \wedge a &= (\neg a \wedge a) \vee (b \wedge a) \\
                         &= 0 \vee (a \wedge b) \\
                         &= a \wedge b \le b
\end{align}}
補題により {a \to b = \neg a \vee b. \Box}

Boole 代数ではない Heyting 代数が存在する

補題 {H} を Heyting 代数とする. もし {a \in H} に対してその補元が存在するならば, それは擬補元 {\neg a} である.

(証明)
{x}{a} の補元とする. このとき {a \wedge x = 0} であるから {x \le \neg a} である. よって単調性により
{1 = a \vee x \le a \vee \neg a}
であるから {a \vee \neg a = 1.} {a \wedge \neg a = 0} は定義より直ちにわかるから, {\neg a}{a} の補元である. {H} は分配的だから, 補元は存在すれば一意である. 故に {x = \neg a. \Box}

{H = \Bigl\{ 0, \dfrac12, 1 \Bigr\}} を, 通常の大小関係を入れて順序集合と見ると, これは有界束になっています. このとき {a \wedge b}

{a \backslash b} {0} {\dfrac12} {1}
{0} {0} {0} {0}
{\dfrac12} {0} {\dfrac12} {\dfrac12}
{1} {0} {\dfrac12} {1}

{a \vee b}

{a \backslash b} {0} {\dfrac12} {1}
{0} {0} {\dfrac12} {1}
{\dfrac12} {\dfrac12} {\dfrac12} {1}
{1} {1} {1} {1}

です. そして {a \to b} については

{a \backslash b} {0} {\dfrac12} {1}
{0} {1} {1} {1}
{\dfrac12} {0} {1} {1}
{1} {0} {\dfrac12} {1}

が成り立ちます. よって擬補元については以下の表のようになります.

a {\neg a}
{0} {1}
{\dfrac12} {0}
{1} {0}

{H} が Boole 代数になるためには擬補元が補元に一致する必要がありますが, {H} においては
{\dfrac12 \vee \neg \dfrac12 = \dfrac12 \vee 0 = \dfrac12 \ne 1}
なので, {H} は Boole 代数ではありません. しかし Heyting 代数ではあるので, これは Boole 代数ではない Heyting 代数の例になっています.