圏論的論理

同義語:圏論的論理学categorical logic

概要

圏論的論理(categorical logic)とは、論理体系を圏で解釈し、圏の構造と論理の構造の対応を調べる数理論理学の分野である。型を対象に、項を射に、論理式を部分対象に対応させ、代入を引き戻しで、量化記号を引き戻しの左右の随伴で解釈する。等式の理論は有限積をもつ圏に、幾何学的理論は分類トポスに、高階の直観主義論理は初等トポスに、依存型は局所 Cartesian 閉圏に対応し、理論を圏、モデルを関手と見ることができる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 圏, 随伴関手, 部分対象, 一階述語論理

一階述語論理のモデルは、集合と写像と部分集合で作る。では、集合の代わりに位相空間の上の層や、群の作用する集合を使ってはいけないのだろうか。使ってよい、というのが圏論的論理の答えである。論理式の解釈に要るのは集合そのものではなく、積・部分対象・引き戻しのような圏の構造だけだからである。
この見方を徹底すると、論理の結合子や量化記号は圏の普遍性で定義でき、理論の断片ごとに、そのモデルを解釈できる圏のクラスが対応する。理論そのものを圏と見なすこともでき、そのときモデルは圏の間の関手になる。この記事はその対応の地図である。

定義

圏論的論理(categorical logic)は、論理体系を圏で解釈し、圏の構造と論理の構造の対応を調べる分野である。解釈の基本の形は次のとおりである。

圏における解釈

有限極限をもつ圏 $\mathcal C$ と、ソート・関数記号・関係記号からなる多ソートの言語を考える。$\mathcal C$ における解釈とは、次の対応のことである。

  • ソート $A$ に対象 $[\![A]\!]$。文脈 $\Gamma=(x_1:A_1,\dots,x_n:A_n)$ には積 $[\![\Gamma]\!]=[\![A_1]\!]\times\dots\times[\![A_n]\!]$
  • 関数記号に射。項 $t$ には合成で射 $[\![t]\!]\colon[\![\Gamma]\!]\to[\![B]\!]$
  • 関係記号に部分対象。論理式 $\varphi$ には、結合子の解釈(下で述べる)を通して部分対象 $[\![\varphi]\!]\subset[\![\Gamma]\!]$
    項の代入は射の合成で、論理式への代入は部分対象の引き戻しで解釈する。文脈 $\Gamma$ の列 $\varphi\vdash_\Gamma\psi$ が妥当であるとは、$[\![\varphi]\!]\le[\![\psi]\!]$ が部分対象の順序で成り立つことをいう。

$\mathcal C$ が集合の圏なら、これは普通の Tarski の意味論である。論理の結合子と量化記号をどう解釈するかは、$\mathcal C$ がもつ構造で決まる。部分対象の束 $\mathrm{Sub}(X)$ の交わりが連言を、Heyting 代数の含意が $\Rightarrow$ を与える。量化記号は、代入の随伴として統一的に定まる。

ハイパードクトリンの順序版

有限積をもつ圏 $\mathcal T$ に対し、次の組を考える。

  • 各対象 $X$ に Heyting 代数 $P(X)$
  • 各射 $f\colon X\to Y$ に Heyting 代数の準同型 $f^*\colon P(Y)\to P(X)$(関手的)
  • 各 $f$ に $f^*$ の左随伴 $\exists_f$ と右随伴 $\forall_f$
    対象を型、$P(X)$ の元を型 $X$ の述語、$f^*$ を代入と読む。集合の圏と $P(X)=2^X$、$f^*=f^{-1}$ はこの例で、$\exists_f$ は順像である。

これは 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 つの圏として固定され、モデルを取る先の圏だけが替わる。ここに、圏の解釈を使う利点がある。

具体例

内部の「存在する」は大域元の存在と違う

圏で解釈すると、同じ論理式の意味が集合のときと変わる。その違いを最も小さな例で計算する。

2 元の群の作用する集合

$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代数、量化子の随伴論理の演算が普遍性であること
2Lawvere理論、正則論理理論を圏と見る、断片ごとの解釈
3Cartesian閉圏、型理論含意と関数の型
4トポス、部分対象分類子、冪対象、内部論理高階の論理の解釈
5Lawvere–Tierney位相、Cohenトポス、分類トポス、コヒーレントトポス独立性、モデルの分類、完全性
6局所Cartesian閉圏、Martin-Löf型理論、ホモトピー型理論依存型とホモトピーの解釈

段階 1 までは束だけで読める。代数系で同じことを見るのが 代数的論理 で、圏論的論理はその束を圏に広げたものと読める。

関連項目

参考文献

[2]
F. William Lawvere, Adjointness in foundations, Dialectica 23 (1969), 281–296, 2006, 著者の解説(pp. 1–2)、hyperdoctrine の定義(pp. 11–12)
[3]
F. William Lawvere, Diagonal arguments and cartesian closed categories, Category Theory, Homology Theory and their Applications II, Lecture Notes in Mathematics 92, Springer,, 2006, 著者の解説(pp. 1–3)
[4]
Krzysztof Kapulkin and Peter LeFanu Lumsdaine, The simplicial model of Univalent Foundations (after Voevodsky), arXiv:1211.2851v5, 2018, §1.4(p. 11)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する