Heyting代数
概要
Heyting代数（Heyting algebra）とは、含意 $a\Rightarrow b$ が $c\leq(a\Rightarrow b)\iff c\wedge a\leq b$ で定まる有界束である。開集合や前層の部分対象の論理を表し、否定は $\neg a=a\Rightarrow0$ と定まる。含意の基本式、二重否定と排中律の関係、部分前層の含意を証明する。
定義
古典論理で命題の含意 $p\Rightarrow q$ は「$\neg p$ または $q$」と表せる。しかし開集合などを真理値とみなすと、補集合が開とは限らない。そこで含意を「$p$ と合わせると $q$ 以下になる最大の真理値」として定める。
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$ の開集合全体 $\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。
右辺を $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$」が必要なのはそのためである。特に終対象の部分前層では、この定理が圏論的な真理値を具体的に示す。部分対象分類子の篩による説明と対応する。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
