圏論的論理(categorical logic)とは、論理体系を圏で解釈し、圏の構造と論理の構造の対応を調べる数理論理学の分野である。型を対象に、項を射に、論理式を部分対象に対応させ、代入を引き戻しで、量化記号を引き戻しの左右の随伴で解釈する。等式の理論は有限積をもつ圏に、幾何学的理論は分類トポスに、高階の直観主義論理は初等トポスに、依存型は局所 Cartesian 閉圏に対応し、理論を圏、モデルを関手と見ることができる。
一階述語論理のモデルは、集合と写像と部分集合で作る。では、集合の代わりに位相空間の上の層や、群の作用する集合を使ってはいけないのだろうか。使ってよい、というのが圏論的論理の答えである。論理式の解釈に要るのは集合そのものではなく、積・部分対象・引き戻しのような圏の構造だけだからである。
この見方を徹底すると、論理の結合子や量化記号は圏の普遍性で定義でき、理論の断片ごとに、そのモデルを解釈できる圏のクラスが対応する。理論そのものを圏と見なすこともでき、そのときモデルは圏の間の関手になる。この記事はその対応の地図である。
圏論的論理(categorical logic)は、論理体系を圏で解釈し、圏の構造と論理の構造の対応を調べる分野である。解釈の基本の形は次のとおりである。
有限極限をもつ圏 $\mathcal C$ と、ソート・関数記号・関係記号からなる多ソートの言語を考える。$\mathcal C$ における解釈とは、次の対応のことである。
$\mathcal C$ が集合の圏なら、これは普通の Tarski の意味論である。論理の結合子と量化記号をどう解釈するかは、$\mathcal C$ がもつ構造で決まる。部分対象の束 $\mathrm{Sub}(X)$ の交わりが連言を、Heyting 代数の含意が $\Rightarrow$ を与える。量化記号は、代入の随伴として統一的に定まる。
有限積をもつ圏 $\mathcal T$ に対し、次の組を考える。
これは Lawvere の定式化を順序集合で書き、代入が含意を保つことを加えたものである(Law69a pp. 11–12。原論文では $\mathcal T$ は Cartesian 閉圏、$P(X)$ は Cartesian 閉圏で、述語の間の導出を射として残し、代入は一般に含意を保たないとする)。随伴の式
$$
\exists_f\varphi\le\psi\iff\varphi\le f^*\psi,\qquad\psi\le\forall_f\varphi\iff f^*\psi\le\varphi
$$
は、射影 $f\colon X\times Y\to Y$ の場合に、量化記号の導入規則と除去規則の組そのものである。量化子の随伴 がこの計算を集合と前層で行っている。論理の推論規則が随伴の普遍性に置き換わることが、この分野の出発点である。
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 等式だけの理論はどの圏で表されるか | 等式で定まる代数系の理論は有限積をもつ圏(Lawvere 理論)で表され、集合の圏へのモデルの圏が代数系の圏と同値になる | Lawvere理論、等式論理 |
| 真・連言・存在量化・等号の断片はどうか | 正則圏で解釈でき、健全性定理が成り立つ。関係の合成の結合律がこの論理で証明できる | 正則論理、正則圏 |
| 含意と単純型はどう読むか | Cartesian 閉圏は型の理論と命題論理の共通の抽象である(Law69a p. 1)。指数対象が関数の型にあたる | Cartesian閉圏、型理論 |
| 高階の直観主義論理はどこで解釈できるか | 初等トポスの内部言語で解釈できる。論理式は部分対象、結合子は Heyting 代数の演算である(MM92 VI.5) | トポス、内部論理 |
| 幾何学的な理論のモデルの全体は何で表されるか | 有限的な幾何学的理論は分類トポスをもち、それはコヒーレントトポスである | 分類トポス |
| 依存型はどの圏に対応するか | 局所 Cartesian 閉圏の $f^*$ の左右の随伴 $\Sigma_f,\Pi_f$ が依存和と依存積にあたる(KL18 p. 11、Rie16 p. 172) | 局所Cartesian閉圏、Martin-Löf型理論 |
| 恒等型まで含めるとどうなるか | 恒等型を道と読み、単体的集合のモデルが作られる | ホモトピー型理論 |
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 前層のトポスでの真偽をどう計算するか | Kripke–Joyal 意味論。対象の上の局所的な強制関係で妥当性が計算できる | 内部論理 の定理「前層のトポスの Kripke–Joyal 意味論」 |
| 内部論理が古典的になるのはいつか | 前層のトポスが Boolean であることは、添字の圏が亜群であることと同値である | 内部論理 の定理「前層のトポスが Boolean になる条件」 |
| 完全性定理の圏論の形は何か | コヒーレントトポスは十分多くの点をもつ(Deligne の定理)。点は集合でのモデルなので、有限的な幾何学的理論の完全性定理の形になる | コヒーレントトポス、分類トポス |
| 連続体仮説の独立性をトポスで見られるか | Boolean で選択公理を満たし、連続体仮説を否定する対象をもつトポスがある | Cohenトポス |
| 「局所的に成り立つ」は論理でどう書くか | 部分対象分類子の自己射 $j$ が閉包作用素を与え、層の概念を定める。二重否定はその例である | Lawvere–Tierney位相、二重否定位相 |
| 所属関係なしに集合論ができるか | 集合の圏の公理系 ETCS は BZC と等無矛盾である | 集合の圏の初等理論 |
| 自然数はどう公理化されるか | 再帰の普遍性をもつ対象として定まり、帰納法はそこから従う | 自然数対象 |
| 対角線論法の共通の形は何か | Cartesian 閉圏の不動点定理から Cantor の定理の形が出る。Tarski の定義不可能性や Gödel の不完全性の型の議論も同じ形に置かれる(Law69) | Cartesian閉圏 の定理「Lawvere の不動点定理」 |
全体を通した要点は 3 つある。第一に、理論は圏であり、モデルは関手である。第二に、論理の演算は普遍性である。第三に、断片を選ぶことは圏の構造を選ぶことである。たとえば $\forall$、$\Rightarrow$、$\neg$ を使わない幾何学的論理式は、幾何学的射の逆像関手で保たれる(分類トポス の注意「幾何学的理論」)。逆像関手は有限極限・像・部分対象の合併を保つが、$\forall$ などの解釈は一般に保たないからである。どの結合子を許すかが、どの関手でモデルが運ばれるかを決めている。
第一の要点を群の理論で見る。群の演算と等式を記述する有限積つきの圏 $\mathcal T$(Lawvere理論)を作ると、有限積を保つ関手 $\mathcal T\to\mathbf{Set}$ は群そのもので、自然変換は群準同型である。集合の代わりに有限積をもつ圏 $\mathcal C$ を値にとれば、同じ関手が $\mathcal C$ の群対象を与える。位相群、Lie 群、層の群は、同じ理論の別の圏でのモデルである。理論が 1 つの圏として固定され、モデルを取る先の圏だけが替わる。ここに、圏の解釈を使う利点がある。
圏で解釈すると、同じ論理式の意味が集合のときと変わる。その違いを最も小さな例で計算する。
$G=\mathbb Z/2$ の作用する集合と同変写像の圏 $G\text{-}\mathbf{Set}$ を考える(トポス の例「$G$ 集合の圏」)。終対象 $1$ は 1 点に自明な作用を入れたものである。$X$ を $G$ に左移動で作用させた $G$ 集合とする。
部分対象。$G$ 集合の部分対象は、作用で閉じた部分集合である。作用で閉じた部分集合の補集合も作用で閉じるので、各 $\mathrm{Sub}(Y)$ は Boole 代数である。とくに $\mathrm{Sub}(1)=\{\emptyset,1\}$ である。
内部の存在量化。文 $\exists x{:}X.\,\top$ の解釈は、$X\to1$ に沿う $\exists$ を最大の部分対象 $X\subset X$ に施したものである。これは $X\to1$ の像である。$X$ は空でないので、像は $1$ の全体である。よって $\exists x{:}X.\,\top$ は $G\text{-}\mathbf{Set}$ で妥当である。
大域元。一方、射 $1\to X$ は $G$ の固定点である。左移動は自由な作用なので、固定点はない。
したがって、「$X$ の元が存在する」は内部では真であるが、$X$ の大域元は存在しない。
この例の読み方は、位相空間の層で見ると分かりやすい。円周の上の 2 重被覆(Möbius の帯の境界)を層と見ると、局所的には切断があるが大域切断はない。内部論理の $\exists$ は「局所的に存在する」を意味する。層のトポスの Kripke–Joyal 意味論でも、存在量化は被覆の上で元を見つけることとして計算される(内部論理 の節「層のトポスと一般のトポス」)。この例の $\mathrm{Sub}(Y)$ は Boole 代数なので、内部論理は古典的である。それでも $\exists$ は「元を 1 つ取り出せる」ことを意味しない。
上の例と対照的に、$G$ の代わりに亜群でない圏の前層をとると排中律が落ちる。2 点の鎖 $0\to1$ の上の前層の圏(写像 $A_1\to A_0$ のなす圏)では、内部論理 の例「反例:2 点の鎖の上の前層と排中律」が示すように $\mathrm{Sub}(1)$ が 3 元の鎖になる。Heyting代数 の議論がそのまま使えて、$\varphi\lor\lnot\varphi$ は妥当でない。
こうして、同じ言語の同じ文の妥当性を、圏を取り替えることで調べられる。証明できないことを示すには、それが妥当でない圏を 1 つ見つければよい。これは強制法やKripke意味論の議論を圏の言葉で 1 つにしたものである。
| 段階 | 読むもの | ここで分かること |
|---|---|---|
| 1 | 随伴関手、Heyting代数、量化子の随伴 | 論理の演算が普遍性であること |
| 2 | Lawvere理論、正則論理 | 理論を圏と見る、断片ごとの解釈 |
| 3 | Cartesian閉圏、型理論 | 含意と関数の型 |
| 4 | トポス、部分対象分類子、冪対象、内部論理 | 高階の論理の解釈 |
| 5 | Lawvere–Tierney位相、Cohenトポス、分類トポス、コヒーレントトポス | 独立性、モデルの分類、完全性 |
| 6 | 局所Cartesian閉圏、Martin-Löf型理論、ホモトピー型理論 | 依存型とホモトピーの解釈 |
段階 1 までは束だけで読める。代数系で同じことを見るのが 代数的論理 で、圏論的論理はその束を圏に広げたものと読める。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する