Heyting代数

同義語：ハイティング代数Heyting algebra

概要

前提知識: 半順序集合, 束, 随伴, 前層

定義

古典論理で命題の含意 $p\Rightarrow q$ は「$\neg p$ または $q$」と表せる。しかし開集合などを真理値とみなすと、補集合が開とは限らない。そこで含意を「$p$ と合わせると $q$ 以下になる最大の真理値」として定める。

Heyting代数

Heyting代数（Heyting algebra）とは、最小元 $0$ と最大元 $1$ をもつ束 $H$ で、各 $a,b\in H$ に対し元 $a\Rightarrow b$ が存在し、任意の $c\in H$ について
$$ c\leq(a\Rightarrow b)\quad\Longleftrightarrow\quad c\wedge a\leq b $$
を満たすものをいう。$a\Rightarrow b$ を含意、$\neg a:=a\Rightarrow0$ を否定という。これは $a\wedge(-)$ の右随伴が $a\Rightarrow(-)$ であるという条件である。MM92 I §8。

含意は順序条件によって一意に定まる。$H$ を $x\leq y$ のときだけ射 $x\to y$ がある圏と見ると、$\wedge$ は積、$\vee$ は余積であり、上の右随伴は指数対象にあたる。したがって Heyting 代数は、圏としてみれば有限積・有限余積をもち、Cartesian 閉な順序集合である。ただし、一般のトポスそのものを Heyting 代数と呼ぶわけではない。トポスの各対象の部分対象の順序に、この構造が現れる。

直感

$a\Rightarrow b$ は「$a$ が成り立つなら $b$ が成り立つ」と言ってよい範囲を最大限に広げた真理値である。否定 $\neg a$ も、$a$ と同時に成り立たない最大の真理値として得られる。開集合ではこの操作に内部が必要になり、古典的な補集合や排中律との差が見える。

例と反例

部分集合の束

集合 $X$ の冪集合 $\mathcal P(X)$ は包含を順序とし、$A\wedge B=A\cap B$、$A\vee B=A\cup B$ とする。このとき
$$ A\Rightarrow B=(X\setminus A)\cup B,\qquad \neg A=X\setminus A $$
である。実際 $C\cap A\subset B$ と $C\subset(X\setminus A)\cup B$ は同値である。この Heyting 代数はBoolean代数でもある。MM92 I §8。

開集合の束

位相空間 $X$ の開集合全体 $\operatorname{Op}(X)$ は包含を順序とし、$U\wedge V=U\cap V$、$U\vee V=U\cup V$、$0=\emptyset$、$1=X$ として Heyting 代数になる。開集合 $U,V$ に対し
$$ U\Rightarrow V=\operatorname{int}\bigl((X\setminus U)\cup V\bigr), \qquad \neg U=\operatorname{int}(X\setminus U)=X\setminus\overline U $$
である。開集合 $W$ について $W\subset\operatorname{int}((X\setminus U)\cup V)$ と $W\cap U\subset V$ は同値だから、含意の定義を満たす。MM92 I §8。

反例：排中律は一般には成り立たない

三元の鎖 $H=\{0< a<1\}$ では $\wedge=\min$、$\vee=\max$ とし、含意を $x\Rightarrow y=1$（$x\leq y$ のとき）、$x\Rightarrow y=y$（$x>y$ のとき）と定める。これは上の随伴条件を満たす Heyting 代数だが、$\neg a=a\Rightarrow0=0$ なので $a\vee\neg a=a\ne1$。よって「Heyting 代数なら排中律が成り立つ」は誤りである。これは二元の鎖 $0<1$ を圏とみなしたとき、その前層圏の終対象の部分対象でも実現できる。MM92 I §8。

性質

含意と否定の基本式

含意から従う式

Heyting 代数 $H$ の任意の $a,b,c\in H$ に対して、次が成り立つ。
$$ a\wedge(a\Rightarrow b)=a\wedge b,\qquad a\Rightarrow(b\wedge c)=(a\Rightarrow b)\wedge(a\Rightarrow c), $$
$$ (a\vee b)\wedge c=(a\wedge c)\vee(b\wedge c),\qquad \neg(a\vee b)=\neg a\wedge\neg b. $$
MM92 I §8。

$b\leq a\Rightarrow b$ は $a\wedge b\leq b$ から従い、$a\wedge(a\Rightarrow b)\leq b$ は随伴の定義から従う。両辺を $a$ とも交わすと最初の等式になる。次に任意の $z$ に対し、$z\leq a\Rightarrow(b\wedge c)$ は $z\wedge a\leq b$ かつ $z\wedge a\leq c$ と同値であり、これは $z\leq(a\Rightarrow b)\wedge(a\Rightarrow c)$ と同値である。
固定した $c$ について $(-)\wedge c$ は右随伴 $c\Rightarrow(-)$ をもつ左随伴なので二元の上限を保つ。これが三つ目の等式である。最後は $\neg(a\vee b)=(a\vee b)\Rightarrow0$ に随伴を使うと、任意の $z$ がその下にあることは $z\wedge a\leq0$ かつ $z\wedge b\leq0$ と同値であり、$z\leq\neg a\wedge\neg b$ と同値になる。$\square$

否定と古典性

任意の $a\in H$ について $a\leq\neg\neg a$、$\neg\neg\neg a=\neg a$ が成り立つ。また次の条件は同値である。

$H$ は Boolean 代数である。
すべての $a$ について $a\vee\neg a=1$。
すべての $a$ について $\neg\neg a=a$。
MM92 I §8。

$a\wedge\neg a=0$ なので、随伴により $a\leq\neg\neg a$。これを $\neg a$ に適用すると $\neg a\leq\neg\neg\neg a$。否定は反単調（$x\leq y$ なら $\neg y\leq\neg x$。実際 $\neg y\wedge x\leq\neg y\wedge y=0$ だから）だから $a\leq\neg\neg a$ から $\neg\neg\neg a\leq\neg a$ も得られ、等号が従う。
1 を仮定する。Boolean 代数とは、最小元・最大元をもつ分配束で、各元 $a$ が補元 $a'$（$a\wedge a'=0$、$a\vee a'=1$）をもつものをいう。$a\wedge a'=0$ より随伴で $a'\leq\neg a$。逆に $\neg a=\neg a\wedge(a\vee a')=(\neg a\wedge a)\vee(\neg a\wedge a')\leq a'$。よって $a'=\neg a$ であり、$a\vee\neg a=a\vee a'=1$ で 2 が成立する。2 が成立すれば $a\wedge\neg a=0$ と合わせて各元が補元をもつため 1 である。さらに 2 から $\neg\neg a=(\neg\neg a)\wedge(a\vee\neg a)=((\neg\neg a)\wedge a)\vee((\neg\neg a)\wedge\neg a)\leq a$ となり、先の不等式と合わせて 3 を得る。逆に 3 を仮定し、$\neg(a\vee\neg a)=\neg a\wedge\neg\neg a=0$ と 3 を $a\vee\neg a$ に適用すると、$a\vee\neg a=\neg\neg(a\vee\neg a)=\neg0=1$ なので 2 が従う。$\square$

前層の部分対象

$\mathcal C$ を小圏、$P\colon\mathcal C^{\mathrm{op}}\to\mathbf{Set}$ を前層とする。部分前層 $S\subset P$ とは、各対象 $U$ で $S(U)\subset P(U)$ であり、任意の射 $f\colon V\to U$ について $P(f)(S(U))\subset S(V)$ となるものをいう。$\operatorname{Sub}(P)$ は $P$ の部分前層を包含で並べた順序集合である。

部分前層の含意

$\operatorname{Sub}(P)$ は Heyting 代数である。部分前層 $S,T\subset P$ の含意は、各対象 $U$ において
$$ (S\Rightarrow T)(U)=\{x\in P(U)\mid \text{すべての }f\colon V\to U\text{ について、}P(f)x\in S(V)\Rightarrow P(f)x\in T(V)\} $$
となる。右辺の条件中の $\Rightarrow$ は「ならば」という通常の論理記号である。ここでの否定は $T=\emptyset$ とした場合である。MM92 I §8 Proposition 5（p. 56）。

右辺を $Q(U)$ と書く。$x\in Q(U)$ を射 $g\colon U'\to U$ で制限し、さらに $f\colon V\to U'$ をとると $P(f)P(g)x=P(g\circ f)x$ である。$x\in Q(U)$ の条件を $g\circ f$ に適用すれば、$P(g)x\in Q(U')$ と分かる。ゆえに $Q$ は部分前層である。$x\in Q(U)\cap S(U)$ には $f=\operatorname{id}_U$ を適用できるので $x\in T(U)$、すなわち $Q\cap S\subset T$。
逆に部分前層 $R$ が $R\cap S\subset T$ を満たすなら、$x\in R(U)$ のすべての制限 $P(f)x$ は $R(V)$ にある。これが $S(V)$ にも入れば $T(V)$ に入るので $x\in Q(U)$。したがって $R\subset Q$。これは $Q=S\Rightarrow T$ の随伴条件そのものである。部分前層の有限交叉・有限和、空前層と $P$ はそれぞれ $\wedge,\vee,0,1$ を与える。$\square$

点ごとに $S(U)\Rightarrow T(U)$ を集合の補集合で計算すると、制限に閉じないことがある。例えば $\mathcal C$ を $0\to1$ の二元鎖、$P=1$（各対象で一元集合）、$S$ を $S(0)=\{*\}$、$S(1)=\emptyset$、$T=\emptyset$ とすると、点ごとの $(P(U)\setminus S(U))\cup T(U)$ は $U=1$ で $\{*\}$、$U=0$ で $\emptyset$ となるが、制限 $P(1)\to P(0)$ で $*$ が $\emptyset$ の外へ出るので、これは部分前層でない（破れる条件：制限への閉性）。上の式に「すべての $f\colon V\to U$」が必要なのはそのためである。特に終対象の部分前層では、この定理が圏論的な真理値を具体的に示す。部分対象分類子の篩による説明と対応する。

含意を「最も弱い追加条件」として計算する

Heyting代数の含意は、$a$ を仮定したときに $b$ が従うような追加条件のうち、最も大きいものとして定まる。順序を論理的含意と読むと、$c\le a\Rightarrow b$ は「$c$ があれば、$a$ から $b$ が出る」を意味する。この条件を $c\wedge a\le b$ と同値にすることが、含意を操作可能な数学的対象として指定している。定義には上限が存在することが含まれ、単に条件を満たす $c$ がいくつかあるだけでは十分でない。

含意の判定式と変数への単調性

Heyting代数で次が成り立つ。
$$ a\Rightarrow b=1\iff a\le b,\qquad 0\Rightarrow b=1,\qquad 1\Rightarrow b=b. $$
また $a\le a'$、$b\le b'$ なら
$$ a'\Rightarrow b\le a\Rightarrow b, \qquad a\Rightarrow b\le a\Rightarrow b'. $$
MM92 I §8（pp. 51–52）。

$a\Rightarrow b=1$ は $1\le a\Rightarrow b$ と同値であり、随伴式により $a=1\wedge a\le b$ と同値である。$0\le b$ なので $0\Rightarrow b=1$。任意の $c$ に対して $c\le1\Rightarrow b$ は $c\wedge1=c\le b$ と同値だから $1\Rightarrow b=b$。
含意 $q=a'\Rightarrow b$ は $q\wedge a'\le b$ を満たす。$a\le a'$ なら交わりの単調性から $q\wedge a\le q\wedge a'\le b$。随伴式で $q\le a\Rightarrow b$ を得る。第二変数については、$(a\Rightarrow b)\wedge a\le b\le b'$ に随伴式を適用する。$\square$

第一変数と第二変数では向きが逆になる。仮定 $a$ を強めれば、それから $b$ を導くために課す追加条件は弱くできる。結論 $b$ を弱めても追加条件は弱くできる。二つの変数の向きが違うことは、含意の式を比較するときに特に重要である。単調性を両変数で同じ方向に使うと、否定が反単調になる理由も失われてしまう。
三元鎖の含意を表にすると、この判定が具体的に見える。

$\Rightarrow$	$0$	$a$	$1$
$0$	$1$	$1$	$1$
$a$	$0$	$1$	$1$
$1$	$0$	$a$	$1$

$x\le y$ なら、どの $c$ に対しても $c\wedge x\le x\le y$ なので最大の $c=1$ が許される。$x>y$ なら $c\wedge x\le y$ は $c\le y$ と同値である。鎖では $c>y$ かつ $x>y$ なら両者の最小値も $y$ より大きくなるためだ。したがって最大の $c$ は $y$ であり、表の式が随伴条件を満たすことが確かめられる。

開集合の否定と境界

開集合の論理では、補集合が開集合とは限らないため、否定をそのまま補集合にできない。そこで、補集合の中に含まれる最大の開集合を取り、$\neg U=X\setminus\overline U$ とする。$U$ と $\neg U$ は互いに交わらないが、その和が全体になるとは限らない。残るのは境界付近の点であり、そうした点は $U$ の中にも、$U$ から開近傍ごと離れた側にも入らない。

実直線における二重否定

$X=\mathbb R$、$U=(0,1)$ とする。$\neg U=(-\infty,0)\cup(1,\infty)$ なので、$U\cup\neg U$ は $0,1$ を含まない。したがって排中律は成り立たない。この $U$ については $\neg\neg U=(0,1)=U$ である。しかし $V=(0,1)\cup(1,2)$ とすると
$$ \neg\neg V=\operatorname{int}(\overline V)=(0,2) $$
であり、$1$ が加わる。二重否定が一つの元で等号になることと、Heyting代数のすべての元で等号になることは異なる。

一般の開集合について $\neg\neg U=\operatorname{int}(\overline U)$ である。これは $\neg U=X\setminus\overline U$ にもう一度否定を適用し、集合恒等式 $X\setminus\overline{X\setminus A}=\operatorname{int}(A)$ を $A=\overline U$ に用いた結果である。二重否定は、開集合の穴のうち、その閉包の内部に残る穴を埋める操作として見える。ただし閉包全体を取るのではなく、その内部を取るので、結果は開集合のままである。

完備性だけでは含意は作れない

完備束なら、候補集合 $\{c\mid c\wedge a\le b\}$ の上限は存在する。しかしその上限自身が候補条件を満たすとは限らない。最大候補を作るには、固定した元との交わりが上限と交換できることが必要になる。有限の場合でも、分配律を失うとこの問題が現れる。

反例：完備束でもHeyting代数にならない

菱形束 $M_3=\{0,a,b,c,1\}$ を考える。異なる中間元の交わりは $0$、結びは $1$ である。この束は有限だから完備である。$x\wedge a\le0$ を満たす元は $0,b,c$ だが、$b,c$ を両方支配する候補はない。候補の上限は $b\vee c=1$ であり、$1\wedge a=a\ne0$ なので候補ではない。よって $a\Rightarrow0$ は存在しない。破れる含意は「完備束ならHeyting代数である」であり、完備性は保持したまま分配性を欠いている。

この例は、上限が存在することと最大の適格な候補が存在することの違いを示す。上限は候補全体を上から支配するが、候補を定める条件を保つとは限らない。逆に有限分配束では、候補全体の有限結びが交わりの分配律によって再び候補になるため含意を作れる。より一般に、任意上限と有限交わりの分配が成り立つ完備束では、同じ議論を無限族に適用できる。MM92 I §8（p. 51）。

外す条件	反例	成り立たなくなること
排中律	三元鎖の中間元	Heyting代数がBoole代数であること
すべての元での二重否定除去	実直線の二つの隣接開区間	$\neg\neg U=U$
分配性	菱形完備束 $M_3$	含意の存在
すべての制限先を調べる条件	二元鎖上の終前層	点ごとの含意が部分前層をなすこと

論理式としての含意と、Heyting代数の元としての含意を区別することも必要である。部分前層の定義式に現れる「すべての射について、ある条件なら別の条件」は、通常の数学言語で元の集合を指定している。その結果としてできる部分前層が、束の中の含意を与える。式の中の論理記号をそのまま各対象で集合の含意に置き換えると、制限の整合性を失う。含意は現在の対象だけでなく、すべての制限先における条件をまとめたものなのである。