これは Math Advent Calendar 2018 1日目の記事です.
Math Advent Calendar 2018 の記念すべきトップバッター! 緊張しますね. これから皆さんを排中律の成り立たない世界へとお連れします. 前提知識としては, 束(lattice)論と圏論の基礎的な知識があれば読めるようにしています.「束って何?」って人は私のサイトでも紹介しているからざっと目を通しておいてね!
$H$ を有界束とし, 交わりを $\wedge$, 結びを $\vee$ で, また最小元を $0$ で, 最大元を $1$ で表す. 任意の $a, b \in H$ に対して $$\{ x \in H \ | \ x \wedge a \le b \}$$ に最大元が存在するとき, $H$ は Heyting 代数であるという. $$a \to b := \max \{ x \in H \ | \ x \wedge a \le b \}$$ と表す.
$H$ は(束演算から定まる)順序があって, 順序集合は圏とみなせるのでした. 交わりは積, 結びは余積です. $$x \wedge a \le b \iff x \le a \to b$$ が成り立つことを圏論っぽく書くと $$\hom(x \wedge a, b) \cong \hom(x, a \to b)$$ となります. これは $x$ と $b$ について自然な同型です. つまり随伴 $$(-) \wedge a \dashv a \to (-)$$ が成り立っているわけです.
圏の一般論で「左随伴は余極限を保つ」という事実があります. 特に余積は余極限ですから $$(a \vee b) \wedge c = (a \wedge c) \vee (b \wedge c)$$ が成り立ちます. 双対的に $$(a \wedge b) \vee c = (a \vee c) \wedge (b \vee c)$$ も成り立ちます. つまり $H$ は分配束です!
Heyting 代数に関するいくつかの性質を圏の一般論も使いつつ証明しておきましょう. 以下, $a, b, c, a', b', x \in H$ とします.
$a \to b$ の定義から明らかである.
$(a \to b) \wedge a' \le (a \to b) \wedge a \le b \le b'$ より.
函手 $a \to (-)$ は右随伴だから極限, 特に積を保つ.
$$\begin{align} \hom (x, (a \vee b) \to c) &\cong \hom (x \wedge (a \vee b), c) \\ &\cong \hom ((x \wedge a) \vee (x \wedge b), c) \\ &\cong \hom (x \wedge a, c) \times \hom (x \wedge b, c) \\ &\cong \hom (x, a \to c) \times \hom (x, b \to c) \\ &\cong \hom (x, (a \to c) \wedge (b \to c)) \end{align}$$ と米田の補題から.
$a \to c \le (a \wedge b) \to c$ と $b \to c \le (a \wedge b) \to c$ から.
$a \to b \le a \to (b \vee c)$ と $a \to c \le a \to (b \vee c)$ から.
$$\begin{align} \hom (x, a \to (b \to c)) &\cong \hom (x \wedge a, b \to c) \\ &\cong \hom ((x \wedge a) \wedge b, c) \\ &\cong \hom (x \wedge (a \wedge b), c) \\ &\cong \hom (x, (a \wedge b) \to c) \end{align}$$ と米田の補題から.
有界束 $B$ が分配的でかつ相補則を満たすとします. つまり $x \in B$ に対して $$x \wedge x' = 0, x \vee x' = 1$$ となる $x' \in B$ が存在するとします. ちなみに分配的であることから, そのような $x'$ は $x$ に対して一意に定まります(通常は $\neg x$ と書きます).
このような $B$ を Boole 代数と言います.
Boole 代数において $x \wedge a \le b \iff x \le \neg a \vee b.$
$(\Longrightarrow)$ $$\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}$$
$(\Longleftarrow)$ $$\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. \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.$
Heyting 代数 $H$ においても, $a \to 0$ のことを $\neg a$ と書いて, これを擬補元と言います. 以下, 擬補元に関する性質をいくつか挙げておきます.
$\neg y = y \to 0 \le x \to 0 = \neg x.$
定義より明らか.
2. から $x \le \neg x \to 0 = \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.$
$$\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}$$
$$\begin{align} \neg (x \wedge y) &= (x \wedge y) \to 0 \\ &= x \to (y \to 0) \\ &= x \to \neg y \\ &= x \to \neg \neg \neg y \\ &= x \to (\neg \neg y \to 0) \\ &= (x \wedge \neg \neg y) \to 0 \\ &= (\neg \neg y \wedge x) \to 0 \\ &= \neg \neg y \to (x \to 0) \\ &= \neg \neg y \to \neg x \\ &= \neg \neg y \to \neg \neg \neg x \\ &= \neg \neg y \to (\neg \neg x \to 0) \\ &= (\neg \neg y \wedge \neg \neg x) \to 0 \\ &= \neg (\neg y \vee \neg x) \to 0 \\ &= \neg \neg (\neg y \vee \neg x) \\ &= \neg \neg (\neg x \vee \neg y). \\ \end{align}$$
$\left\{0, \dfrac12, 1\right\}$ を実数の大小関係で順序集合とします. これは自然に束になります. このとき, 擬補元について以下が成り立ちます.
| $x$ | $\neg x$ | $x \vee \neg x$ |
|---|---|---|
| $0$ | $1$ | $1$ |
| $\dfrac12$ | $0$ | $\dfrac12$ |
| $1$ | $0$ | $1$ |
Boole 代数なら常に $x \vee \neg x = 1$ でなければなりませんが, そうなっていないのでこれは Boole 代数ではないことになります. しかし Heyting 代数にはなっています.
Boole 代数では $x \wedge \neg x = 0, x \vee \neg x = 1$ が常に成り立ちます. Heyting 代数でも $x \wedge x' = 0, x \vee x' = 1$ となる $x'$ があれば, それは $\neg x = x \to 0$ でなければなりません. しかし, 上記の例でわかる通り, $x \vee \neg x = 1$ は常に成り立っているとは限りません.
Boole 代数における $x \vee \neg x = 1$ は, (古典)論理学における「排中律」に相当します. 雑に言えば, 古典論理とは Boole 代数の世界です. これに対して, Heyting 代数に対応する論理学があります. それが「直観主義論理」です. 「直観主義論理」はまさに「排中律が成り立たない世界」なのです.
排中律が成り立たないことは一見不自然に思えますが, そうではありません. 私たちは「$P$ を証明する手立てが無かった」からと言って「$P$ でない」と結論付けられるでしょうか. 多くの人はそうは思わないでしょう. 直観主義論理では, 命題が成り立つことを「その命題が成り立つことを証明する具体的な方法がある」と解釈します. 人間的な感覚として, こちらの方が古典論理よりも自然だと思いませんか?
Heyting 代数が Boole 代数より真に広い概念であることは分かりました. では Heyting 代数って(直観主義論理以外で)どういう場面で使うんでしょう?
位相空間 $X$ の開集合の全体 $\mathcal{O}(X)$ を考えます. これは集合の包含関係で順序集合になっています. また, 2 個の開集合の和集合, 共通部分は再び開集合になります. 従って $\mathcal{O}(X)$ は束になっています. また, 任意の $O_1, O_2 \in \mathcal{O}(X)$ に対して $$\mathcal{U} = \{ U \in \mathcal{O}(X) \ | \ U \cap O_1 \subset O_2 \}$$ は $\bigcup \mathcal{U}$ を最大元として持つことがわかります. 従って $\mathcal{O}(X)$ は完備1Heyting 代数になります. ただし, 開集合の補集合は一般に開集合ではないので, Boole 代数にはなりません.
$\mathcal{O}(X)$ を圏とみなすとき, 函手 $\mathcal{O}(X)^\mathrm{op} \to C$ を ($C$ 上の)前層と言います(前層の中でさらに「良い」性質をもつものを「層」と言います). 上記の理屈から, (前)層の世界は Heyting 代数の世界です. 従って完備 Heyting 代数は「層」の理論の定式化に使われます.
他にも, 「位相空間の開集合の全体は完備 Heyting 代数になる」ことから逆算して, 完備 Heyting 代数から位相空間論を展開する「pointless topology」という分野もあります. これはトポスとの相性が良いです.
Heyting 代数って大学の講義でもあまり扱われない(というか, 自分はそれについて講義で聞いた記憶がありません)概念ですが, 定義や基本的な性質を知っているだけでもだいぶ違うと思います. 特に, 層やトポス, 直観主義論理に興味がある人は押さえておきたいところです.
赤猫堂本舗「数学に関するよしなしごと」へ