代数的論理

同義語:代数的論理学algebraic logic

概要

代数的論理(algebraic logic)とは、論理式の同値類や論理の演算を代数系として扱い、論理体系の性質を代数系の性質に翻訳して調べる数理論理学の分野である。古典命題論理には Boole 代数、直観主義論理には Heyting 代数、様相論理には様相代数、等号つきの一階述語論理には円柱代数が対応する。証明可能性は代数系の等式に、モデルは代数系への準同型に、完全性定理は表現定理や準同型の存在に翻訳される。

$$\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}} $$

前提知識: 命題論理, Boole代数, Heyting代数, 一階述語論理

論理式は記号の列であり、そのままでは足し算も掛け算もできない。しかし「同値な論理式を同じものと見なす」と、連言 $\land$ と選言 $\lor$ は集合の共通部分と和集合によく似た演算になり、論理式の全体は 1 つの代数系になる。代数的論理は、この見方を出発点にして、論理についての問いを代数系についての問いに翻訳して調べる。
翻訳の仕組みは、どの論理でもほぼ同じである。証明できることは「代数系の等式」に、モデルは「代数系への準同型」に、完全性定理は「代数系の十分多くの準同型の存在」に対応する。論理の側の難しさが、代数の側では表現定理の難しさとして現れる。この記事はその対応の地図であり、個々の定理の証明はそれぞれの記事に任せる。

定義

代数的論理(algebraic logic)は、論理体系に代数系のクラスを対応させ、両者を行き来して論理体系の性質を調べる分野である。対応を作る基本の操作が、論理式の同値類をとることである。

Lindenbaum–Tarski 代数

結合子の集合と変数の集合を固定し、論理式の全体を $\mathrm{Fm}$ とする。各結合子は $\mathrm{Fm}$ の上の演算なので、$\mathrm{Fm}$ は代数系である。証明可能性 $\vdash$ と双条件 $\leftrightarrow$ をもつ論理で、
$$ \varphi\equiv\psi\ :\Longleftrightarrow\ \vdash\varphi\leftrightarrow\psi $$
が結合子と両立する同値関係(合同関係)になるとき、商代数 $\mathrm{Fm}/{\equiv}$ をその論理の Lindenbaum–Tarski 代数 という。理論 $T$ を固定して $T\vdash\varphi\leftrightarrow\psi$ で割ったものを $T$ の Lindenbaum–Tarski 代数という。

この操作には Lindenbaum の着想と Tarski の定式化がある(SA13 p. 2)。古典命題論理からは Boole代数 が、直観主義命題論理からは Heyting代数 が、基本様相論理 K からは様相代数(下の表)が得られる。どの場合も、「$\varphi$ が証明できる」と「$\varphi$ の類が最大元 $1$ である」は同じことである。
一階述語論理では量化記号と等号を演算として扱う必要がある。そのための代数系が円柱代数である。

円柱代数

$n$ を自然数とする。Boole 代数 $(A,\vee,\wedge,{}',0,1)$ に、1 変数の演算 $c_i$($0\le i< n$)と定数 $d_{ij}$($0\le i,j< n$)を加えた代数系で、次を満たすものを $n$ 次元の円柱代数(cylindric algebra)という。

  • $c_i0=0$、$x\le c_ix$、$c_i(x\wedge c_iy)=c_ix\wedge c_iy$、$c_ic_jx=c_jc_ix$
  • $d_{ii}=1$
  • $j\ne i$ かつ $j\ne k$ のとき $d_{ik}=c_j(d_{ij}\wedge d_{jk})$
  • $i\ne j$ のとき $c_i(d_{ij}\wedge x)\wedge c_i(d_{ij}\wedge x')=0$

定義は BS12 II §1 の例 (13)(pp. 26–27)による。$c_i$ が「$x_i$ について存在量化する」演算、$d_{ij}$ が等式 $x_i=x_j$ にあたる。下の例で、集合の上の関係がこの公理を満たすことを確かめる。

主な問題と結果の一覧

問い代表的な結果入る記事
古典命題論理の同値類は何をなすか$n$ 変数の論理式の論理的同値の類は Boole 代数をなし、$2^{2^n}$ 個の元をもつ命題論理 の定理「論理式の同値類のなすBoole代数」
Boole 代数はいつ集合の代数か任意の Boole 代数は Stone 空間の開閉集合の代数に同型である(Stone の表現定理)。有限なら冪集合に同型であるBoole代数、Stone双対性
分配束ではどうなるかStone の双対性は分配束へ広がり、可換環のスペクトルとも結びつくStone双対性 の節「分配束への拡張」と節「可換環のスペクトルとの関係」、分配束
直観主義論理にあたる代数は何かHeyting 代数に関する健全性と完全性が成り立つ。3 元の鎖で排中律が落ちる直観主義論理、Heyting代数
Heyting 代数と Kripke モデルの関係半順序集合の上集合の全体は Heyting 代数をなし、Kripke モデルはその特別な値づけと読めるKripke意味論 の命題「上集合の Heyting 代数」
様相論理にあたる代数は何か様相代数は Boole 代数と有限の交わりを保つ $\Box$ の組である。K は様相代数の全体に関して完全である(GvG Definition 4.46、Theorem 4.47)様相論理
様相論理の Kripke 意味論はどこから来るかBoole 代数の Stone 双対を $\Box$ つきに広げたものから、位相を忘れて得られる(GvG p. 107)様相論理、Stone双対性
一階述語論理にあたる代数は何か円柱代数。$\omega$ 次元で局所有限な円柱代数は表現可能である(Tarski)。この表現定理と Gödel の完全性定理は、互いに短い議論で導ける(SA13 p. 4)一階述語論理、Gödelの完全性定理
円柱代数の公理は足りているか次元が 2 より大きいと、表現可能な円柱代数のクラスは、円柱代数の公理のような有限の等式の図式では公理化できない(Monk。SA13 p. 8)この記事の下の節
等式だけの論理はどうかBirkhoff の完全性定理が成り立つ。等式クラスと、部分代数・準同型像・直積で閉じたクラス(多様体)は一致する等式論理、普遍代数
関係の計算はどこまで表せるか関係代数の表現力は、変数を 3 個に制限した一階論理と同じである(BL21)。すべての関係代数が 2 項関係の代数に同型とは限らない(SA13 p. 6)この記事の下の節
論理の性質と代数の性質はどう対応するか有限的で有限代数化可能で演繹定理をもつ論理では、Craig の補間性質は、対応する代数系のクラスの融合性と同値である(Jan22 Theorem 2)。直観主義論理と 中間論理 は、これで Heyting 代数の多様体の融合性と結びつくCraigの補間定理
どの論理が代数化できるか論理の体系ごとに代数を探すのでなく、Blok と Pigozzi は 1989 年に有限的な論理に対して代数化可能性の概念を定義した(Jan22)この記事の下の節
強制法の裏の代数は何か分離的な強制概念は完備 Boole 代数の中に稠密に埋まる完備Boole代数、強制法

表のうち、個別の記事をもたない話題を補っておく。
様相代数は Boole 代数 $B$ と写像 $\Box\colon B\to B$ の組で、$\Box1=1$ と $\Box(x\wedge y)=\Box x\wedge\Box y$ を満たすものである。これは $\vdash\Box\top\leftrightarrow\top$ と $\vdash\Box(\varphi\land\psi)\leftrightarrow(\Box\varphi\land\Box\psi)$ の翻訳になっている。Kripke フレーム $(X,R)$ からは、$X$ の冪集合に
$$ \Box S:=\{x\in X\mid xRy\text{ なるすべての }y\text{ について }y\in S\} $$
を入れた様相代数が得られる。Kripke モデルでの真偽は、この様相代数での値にほかならない。
関係代数は、集合の上の 2 項関係がもつ合成と逆を、Boole 演算とともに等式で公理化したものである。De Morgan・Peirce・Schröder の関係の計算を、Tarski が 1941 年に等式の体系として取り上げた(BL21)。
表現可能性は代数的論理の中心の問題である。Boole 代数では「公理を満たす抽象的な代数」と「集合の代数」が一致した。これが Stone の表現定理である。円柱代数では同じことが成り立たない。次元 $\alpha>1$ では、表現可能な円柱代数のクラスは円柱代数のクラスより真に小さい(SA13 p. 8)。公理で捉えられるものと、関係の実物から来るものの差が、この分野の問題の源になっている。
代数化可能性は、個々の論理と代数の対応を 1 つの定義にまとめたものである。論理 $L$ が代数化可能であるとは、大まかには、$L$ の導出可能性と、ある代数系のクラスの等式の帰結とが、論理式と等式の翻訳で互いに写り合うことをいう。正確な定義は Jan22 にある。

具体例

変数が有限個の古典命題論理

論理式の同値類の個数

変数 $p_1,\dots,p_n$ の論理式を論理的同値で割った Boole 代数 $B_n$ の元の個数を求める。論理式 $\varphi$ に真理値表、すなわち関数 $f_\varphi\colon\{0,1\}^n\to\{0,1\}$ を対応させる。2 つの論理式が論理的同値であることは、定義により真理値表が等しいことである。よって $[\varphi]\mapsto f_\varphi$ は単射である。
全射であることは、選言標準形の存在から従う。関数 $f$ に対して、$f(a)=1$ となる $a$ ごとに、$a_i=1$ なら $p_i$、$a_i=0$ なら $\lnot p_i$ を連言でつないだ論理式 $C_a$ を作り、それらの選言をとれば真理値表は $f$ になる($f$ が恒等的に $0$ なら $p_1\land\lnot p_1$ をとる)。
関数 $f$ の個数は $2^{2^n}$ だから、$B_n$ の元は $2^{2^n}$ 個である。$n=1$ なら $4$ 個で、$[p_1]$、$[\lnot p_1]$、$[p_1\lor\lnot p_1]$、$[p_1\land\lnot p_1]$ である。$f$ に $f^{-1}(1)$ を対応させれば、$B_n$ は $\{0,1\}^n$ の冪集合と同型になる。原子は $[C_a]$ である。

同じ問いを直観主義論理に置くと、$p_1$ と $\lnot\lnot p_1$ は同じ類にならない。3 元の鎖 $0< a< 1$ で $p_1$ に $a$ を割り当てると、$\lnot\lnot a=1\ne a$ だからである(直観主義論理 の例「反例:3 元の鎖と排中律」)。論理の違いは、そのまま代数の違いとして見える。

完全性定理を代数で読む

代数的な見方が定理の証明を短くする例として、命題論理の完全性定理を Boole 代数の言葉で導く。

超フィルターから付値を作る

古典命題論理の証明体系で、$\vdash$ による同値の類の全体 $B$ が Boole 代数になっているとする($[\varphi]\vee[\psi]=[\varphi\lor\psi]$、$[\varphi]'=[\lnot\varphi]$ など。これは公理と規則から確かめることで、体系ごとの作業である)。変数は無限個でもよい。
$\varphi$ が証明できないとする。$[\varphi]=1$ なら $\vdash\varphi$ だから $[\varphi]\ne1$、すなわち $[\lnot\varphi]\ne0$ である。$0$ でない元を含む超フィルター $U$ をとる(Stone双対性 の補題「超フィルターへの延長」)。$h(x)=1\iff x\in U$ で定めた $h\colon B\to\{0,1\}$ は Boole 代数の準同型である。
変数 $p$ に $v(p):=h([p])$ を割り当てる。論理式の構成についての帰納法で、すべての $\psi$ について $v(\psi)=h([\psi])$ である。実際、$h$ が演算を保ち、$v$ の真理値表の計算も同じ演算だからである。$[\lnot\varphi]\in U$ より $v(\varphi)=0$ なので、$\varphi$ は恒真式でない。
対偶をとれば、恒真式は証明できる。これが完全性定理(命題論理)である。この道筋は Gal15 の問題 3.5.18(pp. 103–104)にある。

ここでの対応は、付値と $B$ から $\{0,1\}$ への準同型と $B$ の超フィルターの 3 つが同じものだ、という形にまとめられる。「モデル=代数系への準同型」という翻訳の最も簡単な場合である。

一階の論理式と集合の円柱代数

関係の円柱代数

$M$ を空でない集合とし、$M^n$ の部分集合の全体 $A$ を考える。$s\in M^n$ に対し、
$$ c_iX:=\{s\in M^n\mid t_j=s_j\ (j\ne i)\text{ なる }t\in X\text{ がある}\},\qquad d_{ij}:=\{s\in M^n\mid s_i=s_j\} $$
とおく。$c_iX$ は $X$ を第 $i$ 座標の方向に引き延ばした筒である。これが「円柱」の名の由来と読める。
変数 $x_0,\dots,x_{n-1}$ の一階の論理式 $\varphi$ に、それを満たす列の集合 $[\![\varphi]\!]\subset M^n$ を対応させると、充足の定義から
$$ [\![\varphi\land\psi]\!]=[\![\varphi]\!]\cap[\![\psi]\!],\quad[\![\lnot\varphi]\!]=[\![\varphi]\!]^c,\quad[\![\exists x_i\,\varphi]\!]=c_i[\![\varphi]\!],\quad[\![x_i=x_j]\!]=d_{ij} $$
となる。公理のうち等号に関わる 2 つを確かめる。
$j\ne i$、$j\ne k$ とする。$s\in d_{ik}$ なら、$s$ の第 $j$ 座標を $s_i$ に替えた $t$ は $d_{ij}\cap d_{jk}$ に入るので、$s\in c_j(d_{ij}\cap d_{jk})$ である。逆に $t\in d_{ij}\cap d_{jk}$ が第 $j$ 座標以外で $s$ と一致すれば、$s_i=t_i=t_j=t_k=s_k$ である。
$i\ne j$ とする。$s\in c_i(d_{ij}\cap X)$ は、$s$ の第 $i$ 座標を $s_j$ に替えた列 $s^*$ が $X$ に入ることと同じである。したがって $c_i(d_{ij}\cap X)$ と $c_i(d_{ij}\cap X^c)$ は交わらない。
残りの公理($c_i\emptyset=\emptyset$、$X\subset c_iX$ など)は定義からすぐに分かる。

こうして、$n$ 個の変数の範囲の一階の論理式の真理集合は円柱代数の演算で計算される。定義と例の $n$ は順序数 $\alpha$ に替えられる(SA13 pp. 3, 5)。この例の形の代数の部分代数の族の部分直積に同型な円柱代数を表現可能という(同 p. 4)。すべての元 $x$ について $c_ix\ne x$ となる $i$ が有限個である円柱代数を局所有限という(同 p. 4)。抽象的な公理がどこまで表現可能なものを捉えるかが、一覧の表の問題である。

読み進め方

段階読むものここで分かること
1命題論理、束、Boole代数論理式の同値類が代数系になること
2Stone双対性、超フィルターモデルが準同型であること、表現定理
3直観主義論理、Heyting代数、Kripke意味論排中律を外すと代数がどう変わるか
4様相論理演算を足した Boole 代数と Kripke フレーム
5等式論理、普遍代数論理と代数系のクラスの一般の対応
6一階述語論理、Gödelの完全性定理 のあとで円柱代数の文献量化記号の代数化と表現可能性
7トポス、内部論理束の代わりに圏を使う一般化。圏論的論理 へ続く

等式で定義された代数系として見るときは 5 が、位相との双対を見るときは 2 が入口になる。

関連項目

参考文献

[2]
Mai Gehrke, Sam van Gool, Topological Duality for Distributive Lattices: Theory and Applications, arXiv:2203.03286, 2023, arXiv:2203.03286v5。Chapter 4(p. 107)、Definition 4.46(p. 107)、Theorem 4.47(p. 108)
[4]
Tarek Sayed Ahmed, The Finitizability Problem in Algebraic Logic, recent results and developments: From neat embeddings to Erdos' graphs, arXiv:1302.1368v1, 2013, p. 2(由来)、pp. 3–5(定義、局所有限な代数の表現)、p. 6(関係代数)、p. 8(表現可能性と有限公理化)

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