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

今回は 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 代数の例になっています.