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

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

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

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

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

半順序集合と束

半順序集合から束

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

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

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

a, b \in L について

  1. a \le c, b \le c
  2. (\forall x \in L)(a \le x, b \le x \Rightarrow c \le x)

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

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

  1. c \le a, c \le b
  2. (\forall x \in L)(x \le a, x \le b \Rightarrow x \le c)

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

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

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

  1. x \vee y = y \vee x, x \wedge y = y \wedge x (交換法則)
  2. x \vee (y \vee z) = (x \vee y) \vee z, x \wedge (y \wedge z) = (x \wedge y) \wedge z (結合法則)
  3. 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 上の関係 \lea \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.

ちなみに
a \vee b = b \Rightarrow a \wedge b = a \wedge (a \vee b) = a
で, 逆も成り立つので, 関係 \le の定義は
a \le b \Leftrightarrow a \wedge b = a
で置き換えても同じです.

しかも, このようにして作った順序から作った束は元の束と一致します. したがって, 束とは半順序集合を含む真に強い概念であると言えます.

*1:私が参考にした「直観主義集合論」では, この記述が抜けているように思います.

*2:同じく「束」と訳される数学の概念に bundle がありますが無関係です.