中間論理

同義語:intermediate logic超直観主義論理superintuitionistic logic

概要

中間論理(intermediate logic)とは、直観主義命題論理を含み古典命題論理に含まれる、前件肯定と代入で閉じた論理式の集合である。無矛盾な超直観主義論理は必ず古典論理に含まれる。自明でない Heyting 代数の多様体と順序を逆にして対応し、Gödel の鎖の論理、Gödel–Dummett 論理、弱い排中律の論理が代表例である。上の端は分類できるが、全体の個数は連続体濃度である。

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

前提知識: 直観主義論理, Heyting代数, Kripke意味論, 多値論理

中間論理(intermediate logic)とは、直観主義論理 と 古典論理 の間にある命題論理である。直観主義命題論理は 排中律 を公理にもたず、古典命題論理はもつ。その間には、排中律の一部だけを認める論理が無数にある。たとえば「$\lnot p$ か $\lnot\lnot p$ のどちらかは成り立つ」という弱い排中律や、「2 つの命題は含意で比較できる」という比較可能性を足すと、直観主義論理より強く古典論理より弱い論理が得られる。
中間論理は、自明でない Heyting代数 の多様体と 1 対 1 に対応し、Kripke意味論 のフレームの形とも結びつく。そのため「どの法則を足すと何が起こるか」が代数と順序の問題になる。この記事は、中間論理の全体がどんな形をしているかを、上の端と下の端の近くから調べる。
この記事では次のことを示す。

  1. 矛盾しない論理は自動的に古典論理に含まれる。→ thm-il-ceiling
  2. 否定の形の定理はどの中間論理でも同じである。→ cor-il-negative
  3. どの中間論理も Heyting 代数のクラスの論理である。→ prop-il-lindenbaum
  4. Gödel の鎖 $\mathrm{G}_n$ は真に減少する列をなし、直観主義論理は有限の行列で書けない。→ prop-il-chains、thm-il-finite
  5. Gödel–Dummett 論理 $\mathrm{LC}$ は鎖の論理で、その拡張は完全に分類できる。→ thm-il-dummett、cor-il-extensions
  6. 古典論理のすぐ下には $\mathrm{G}_3$ だけがある。→ thm-il-coatom
  7. 比較可能性と弱い排中律はフレームの形の条件に対応する。→ prop-il-frames

定義

論理式と証明は 直観主義論理 の記事のものを使う。命題変数と $\bot$ から $\land,\lor,\to$ で論理式を作り、$\lnot\varphi:=(\varphi\to\bot)$、$\varphi\leftrightarrow\psi:=(\varphi\to\psi)\land(\psi\to\varphi)$ とする。$\mathrm{IPC}$ は直観主義論理で証明可能な論理式の全体、$\mathrm{CPC}$ は古典論理の恒真式の全体である。

中間論理

論理式の集合 $L$ が 超直観主義論理(superintuitionistic logic)であるとは、$\mathrm{IPC}\subset L$ で、$L$ が前件肯定と代入で閉じていることをいう。$\bot\notin L$ のとき $L$ は 無矛盾 であるという。
$\mathrm{IPC}\subset L\subset\mathrm{CPC}$ を満たす超直観主義論理を 中間論理 という。
論理式の集合 $\Sigma$ について、$\Sigma$ を含む最小の超直観主義論理を $\mathrm{IPC}+\Sigma$ と書く。

$\mathrm{CPC}$ は $\mathrm{IPC}+(p\lor\lnot p)$ である。thm-il-ceiling により、中間論理と無矛盾な超直観主義論理は同じものである(Mos22 §6.1)。文献によっては 2 つの語を同じ意味で使う。全論理式の集合も超直観主義論理だが、中間論理ではない。
代表的な論理を挙げる。

記号名前$\mathrm{IPC}$ に足す公理
$\mathrm{KP}$Kreisel–Putnam 論理$(\lnot p\to q\lor r)\to(\lnot p\to q)\lor(\lnot p\to r)$
$\mathrm{KC}$Jankov 論理(弱い排中律の論理)$\lnot p\lor\lnot\lnot p$
$\mathrm{LC}$Gödel–Dummett 論理$(p\to q)\lor(q\to p)$
$\mathrm{G}_n$$n$ 元の鎖の論理下の定義
Gödel の鎖

$n\ge2$ について、$n$ 元の全順序集合を $C_n$ とする。最小元を $0$、最大元を $1$ として、$x\Rightarrow y:=1$($x\le y$ のとき)、$x\Rightarrow y:=y$($x>y$ のとき)と定める。$C_n$ は Heyting代数 である。$\bot$ を $0$、$\land,\lor$ を最小・最大、$\to$ を $\Rightarrow$ とし、指定値を $1$ とする行列の恒真式の全体を $\mathrm{G}_n$ と書く。

多値論理 の言葉では $\mathrm{G}_n$ は $n$ 値の行列の論理である(OLT26 Def. 46.6、47.4)。$\mathrm{G}_2=\mathrm{CPC}$ で、$\mathrm{G}_3$ が Gödel の 3 値論理である。Heyting 代数なので $\mathrm{IPC}\subset\mathrm{G}_n$ である(直観主義論理 の定理「Heyting 代数に関する健全性」)。添字を Kripke フレームの点の個数で数える文献もあり、そのときは番号が 1 つずれる(Mos22 §6.1)。

直観

$\mathrm{IPC}$ の Kripke モデルでは、情報の状態が枝分かれしながら増えていく。古典論理は状態が 1 つしかない場合である。中間論理は、枝分かれの仕方に制限をつけることに相当する。

  • $\mathrm{KC}$ は「どの 2 つの未来もやがて合流できる」という条件である。分かれても矛盾する情報には至らないので、$\lnot p$ か $\lnot\lnot p$ のどちらかが今決まる。
  • $\mathrm{LC}$ は「未来は 1 本道である」という条件である。すると 2 つの命題のどちらが先に証明されるかが比較できる。
  • $\mathrm{G}_n$ は「その 1 本道の長さが $n-1$ 点以下である」という条件である。
    したがって、上の端に近い論理はフレームが小さく単純で、下の端に近い論理はフレームが複雑である。実際、上の端の構造は明快に分類できるが、下の方は連続体濃度の論理が入り組んでいる。

例と反例

上の論理は 1 列に並ぶ。
$$ \mathrm{IPC}\subsetneq\mathrm{KP}\subsetneq\mathrm{KC}\subsetneq\mathrm{LC}\subsetneq\mathrm{G}_3\subsetneq\mathrm{CPC}. $$

包含の確かめ

$\mathrm{KP}\subset\mathrm{KC}$:$\lnot p$ を仮定すると、$\lnot p\to q\lor r$ から $q\lor r$ が出るので $(\lnot p\to q)\lor(\lnot p\to r)$ が出る。$\lnot\lnot p$ を仮定すると、$\lnot p\to q$ は矛盾から従う。よって $\lnot p\lor\lnot\lnot p$ の場合分けで $\mathrm{KP}$ の公理が証明できる。
$\mathrm{KC}\subset\mathrm{LC}$:$\mathrm{LC}$ の公理の $q$ に $\lnot p$ を代入すると $(p\to\lnot p)\lor(\lnot p\to p)$ である。$p\to\lnot p$ から $\lnot p$ が、$\lnot p\to p$ から $\lnot\lnot p$ が出る。
$\mathrm{LC}\subset\mathrm{G}_3$:鎖では $x\Rightarrow y$ か $y\Rightarrow x$ が $1$ である。

次の表の式は左の論理ほど証明しにくい。$\mathrm{BD}$ と書いたのは式 $p\lor(p\to q\lor\lnot q)$ である。

式$\mathrm{IPC}$$\mathrm{KP}$$\mathrm{KC}$$\mathrm{LC}$$\mathrm{G}_3$$\mathrm{CPC}$
$\mathrm{KP}$ の公理×○○○○○
$\lnot p\lor\lnot\lnot p$××○○○○
$(p\to q)\lor(q\to p)$×××○○○
$\mathrm{BD}$××××○○
$p\lor\lnot p$×××××○

× は次の有限フレームで確かめられる(prop-il-frame-logic)。フレームの上に閉じた部分集合をすべて調べる有限の計算である。

妥当でない式フレーム妥当な論理
$\mathrm{KP}$ の公理根の上に比較できない 3 点$\mathrm{IPC}$
$\lnot p\lor\lnot\lnot p$根の上に比較できない 2 点$\mathrm{KP}$
$(p\to q)\lor(q\to p)$根の上に比較できない 2 点、その上に頂点$\mathrm{KC}$
$\mathrm{BD}$3 点の鎖$\mathrm{LC}$
$p\lor\lnot p$2 点の鎖$\mathrm{G}_3$
反例:比較可能性だけでは排中律は出ない

$C_3=\{0< h<1\}$ で $v(p)=h$ とすると、$p\lor\lnot p$ の値は $h\lor0=h\ne1$ である。一方、$C_3$ は鎖なので $(p\to q)\lor(q\to p)$ の値はつねに $1$ である。

  • 満たすこと:$\mathrm{LC}$ の公理は $C_3$ で妥当である。
  • 満たさないこと:$p\lor\lnot p$ は $C_3$ で妥当でない。
  • 成り立たない含意:「比較可能性から排中律が従う」。
    このため $\mathrm{LC}\ne\mathrm{CPC}$ である。
反例:選言特性

$\mathrm{IPC}$ は Kripke意味論 の定理「選言特性」のとおり、$\varphi\lor\psi$ が証明できるなら $\varphi$ か $\psi$ が証明できる。$\mathrm{KC}$ と $\mathrm{LC}$ はこの性質をもたない。$\lnot p\lor\lnot\lnot p$ は両方の論理の元だが、$\lnot p$ は古典の付値 $v(p)=1$ で、$\lnot\lnot p$ は $v(p)=0$ で偽になるので、どちらも $\mathrm{CPC}$ に属さず、両方の論理に属さない。
選言特性をもつ中間論理は $\mathrm{IPC}$ だけではない。$\mathrm{KP}$ は選言特性をもつ(ST06 §9、Mos22 §6.1。この記事では証明しない)。

性質

上の端

無矛盾な論理は古典論理に含まれる

$L$ が超直観主義論理で $L\not\subset\mathrm{CPC}$ なら、$L$ は全論理式の集合である。

まず、変数を含まない論理式 $\chi$ について、古典の値が真なら $\vdash_{\mathrm I}\chi$、偽なら $\vdash_{\mathrm I}\lnot\chi$ であることを $\chi$ の組み立てについての帰納法で示す。$\bot$ は $\lnot\bot=(\bot\to\bot)$ が証明できる。$\land,\lor$ は直ちに従う。$\alpha\to\beta$ については、$\vdash_{\mathrm I}\beta$ か $\vdash_{\mathrm I}\lnot\alpha$ なら $\vdash_{\mathrm I}\alpha\to\beta$ であり、$\vdash_{\mathrm I}\alpha$ かつ $\vdash_{\mathrm I}\lnot\beta$ なら $\vdash_{\mathrm I}\lnot(\alpha\to\beta)$ である。
$\varphi\in L\setminus\mathrm{CPC}$ とする。$\varphi$ を偽にする古典の付値 $w$ がある。$w(p)$ が真の変数 $p$ に $\bot\to\bot$ を、偽の変数に $\bot$ を代入した式を $\chi$ とする。$\chi$ は変数を含まず、古典の値は偽である。代入で閉じていることから $\chi\in L$、前半から $\lnot\chi\in\mathrm{IPC}\subset L$ である。前件肯定で $\bot\in L$ となり、公理 $\bot\to\psi$ からすべての $\psi$ が $L$ に属する。$\square$

この性質を古典論理の Post 完全性 と呼ぶことがある。これと Glivenko の定理を合わせると、中間論理の違いは否定の形の式には現れないことが分かる。

否定の定理は共通である

$L$ を中間論理とする。論理式 $\varphi$ について $\lnot\varphi\in L\iff\lnot\varphi\in\mathrm{IPC}$ である。

$\lnot\varphi\in L$ なら $\lnot\varphi\in\mathrm{CPC}$ である。Glivenkoの定理 により $\lnot\lnot\lnot\varphi\in\mathrm{IPC}$ で、$\lnot\lnot\lnot\varphi\to\lnot\varphi$ は証明できるから $\lnot\varphi\in\mathrm{IPC}$ である。逆は $\mathrm{IPC}\subset L$ による。$\square$

Heyting 代数による完全性

Heyting 代数 $H$ で $\varphi$ が 妥当 であるとは、直観主義論理 の定義「Heyting 代数での値」の意味で、すべての付値で値が $1$ であることをいう。$H$ で妥当な式の全体を $\mathrm{Log}(H)$ と書く。$\mathrm{Log}(H)$ は超直観主義論理である(代入は付値の取り替えにあたる)。

Lindenbaum 代数

超直観主義論理 $L$ について、$\varphi\sim\psi:\iff(\varphi\leftrightarrow\psi)\in L$ で論理式を割った集合 $H_L$ は、結合子から定まる演算で Heyting 代数になる。$L\subset\mathrm{Log}(H_L)$ であり、$\varphi\notin L$ なら $H_L$ の付値 $p\mapsto[p]$ で $\varphi$ の値は $1$ でない。特に $L=\mathrm{Log}(H_L)$ である。

$\sim$ が結合子と両立することは、$\mathrm{IPC}$ で $\leftrightarrow$ の置き換えが証明できることによる。$[\varphi]\le[\psi]:\iff(\varphi\to\psi)\in L$ は半順序で、$\land,\lor$ は交わり・結びを与える。随伴の条件 $[\chi]\le[\varphi\to\psi]\iff[\chi\land\varphi]\le[\psi]$ は、$\mathrm{IPC}$ で $(\chi\to(\varphi\to\psi))\leftrightarrow(\chi\land\varphi\to\psi)$ が証明できることから従う。最大元は $L$ の元の類で、$[\varphi]=1\iff\varphi\in L$ である。
付値 $p\mapsto[\sigma(p)]$ での $\varphi$ の値は $[\sigma(\varphi)]$ である。$\varphi\in L$ なら $\sigma(\varphi)\in L$ なので値は $1$ である。$\sigma$ を恒等写像とすると後半が得られる。$\square$

超直観主義論理 $L$ に対し、$L$ が妥当な Heyting 代数の全体は等式で定まるクラス(多様体)である。prop-il-lindenbaum により、$L$ はこのクラスから復元できる。逆に Heyting 代数の多様体は、その等式を論理式に読み替えて論理を定める。こうして超直観主義論理の全体は、Heyting 代数の多様体の全体と順序を逆にして対応する。

Gödel の鎖

鎖の列

$n\ge2$ とし、
$$ D_n:=\bigvee_{0\le i< j\le n}(p_i\leftrightarrow p_j) $$
とする。このとき $D_n\in\mathrm{G}_n\setminus\mathrm{G}_{n+1}$ で、$\mathrm{G}_{n+1}\subsetneq\mathrm{G}_n$ である。

鎖で $x\ne y$ なら $x\Leftrightarrow y:=(x\Rightarrow y)\land(y\Rightarrow x)=\min\{x,y\}$ で、$x=y$ なら $1$ である。
$C_n$ の付値では $n+1$ 個の変数のうち 2 つの値が等しいので、$D_n$ の値は $1$ である。$C_{n+1}$ の付値で $n+1$ 個の変数にすべての元を割り当てると、どの 2 つも異なるので、$D_n$ の値は異なる 2 元の最小の最大、すなわち上から 2 番目の元で、$1$ でない。
$C_n$ は $C_{n+1}$ の部分集合として $0,1$ を含み演算で閉じている(鎖の含意の値は $1$ か第 2 引数である)ので、$C_{n+1}$ で値 $1$ の式は $C_n$ でも値 $1$ である。よって $\mathrm{G}_{n+1}\subset\mathrm{G}_n$ である。$\square$

Gödel の観察は、prop-il-chains の $D_n$ を一般の行列に当てはめることである。多値論理 の行列は Heyting 代数に限らない。

有限の行列で書けないこと(Gödel)

$\mathcal M$ を値の集合が有限の行列とする。$\mathrm{IPC}\subset\mathrm{Taut}(\mathcal M)$ なら $\mathrm{IPC}\ne\mathrm{Taut}(\mathcal M)$ である。

$n\ge2$ を値の個数以上にとる。$D_n\in\mathrm{Taut}(\mathcal M)$ を示す。$D_n\notin\mathrm{G}_{n+1}$ で $\mathrm{IPC}\subset\mathrm{G}_{n+1}$ だから $D_n\notin\mathrm{IPC}$ なので、これで十分である。
付値 $v$ をとる。変数は $n+1$ 個なので、$i< j$ で $v(p_i)=v(p_j)$ となるものがある。$p_j$ に $p_i$ を代入する代入を $\sigma$ とする。論理式の組み立てについての帰納法で、すべての $\psi$ で $v(\sigma(\psi))=v(\psi)$ である。$\sigma(D_n)$ は選言の項に $p_i\leftrightarrow p_i$ を含むので $\mathrm{IPC}$ の元で、仮定から $v$ で指定値をとる。よって $v(D_n)$ も指定値である。$\square$

Gödel が 1932 年に示した結果で、$\mathrm{IPC}$ が有限の真理値表で書けないことの証明である(Mos22 §6.1)。一方、$\mathrm{IPC}$ は有限の Heyting 代数の全体の論理である。これは Jaśkowski と McKinsey–Tarski の定理で(ST06 Theorem 9.1)、1 つの有限の行列では足りないが、有限の行列の族なら足りる。$\mathrm{IPC}$ は無限の行列 1 つでも書ける(多値論理 の命題「無限の行列による表示」)。

Gödel–Dummett 論理

$\mathrm{LC}$ が鎖の論理であることを、フィルターによる商で示す。Heyting 代数 $H$ の フィルター とは、$1$ を含み、$\land$ で閉じ、上に閉じた部分集合である。

フィルターによる商

$F$ を Heyting 代数 $H$ のフィルターとする。$a\equiv b:\iff$ ある $c\in F$ で $c\land a=c\land b$、と定めると、$\equiv$ は Heyting 代数の演算と両立する同値関係である。商 $H/F$ で $[a]=1\iff a\in F$ である。さらに $a\notin F$ なら、$a$ を含まないフィルターの中で極大な $F'\supset F$ があり、$F'$ は素である($x\lor y\in F'$ なら $x\in F'$ または $y\in F'$)。

証明を開く

$F$ は $\land$ で閉じているので同値関係である。$c\land a=c\land a'$、$c\land b=c\land b'$ とする(2 つの条件の $c$ は交わりをとれば共通にできる)。$\land$ との両立は明らかで、$\lor$ との両立は分配律による。$\Rightarrow$ については、等式 $c\land(a\Rightarrow b)=c\land((c\land a)\Rightarrow(c\land b))$ を使う。この等式は、$z\le c$ について $z\le a\Rightarrow b\iff z\land a\le b\iff z\land(c\land a)\le c\land b$ であることから従う。右辺は $a,b$ を $a',b'$ に替えても同じである。

$[a]=1$ は $c\land a=c$、すなわち $c\le a$ となる $c\in F$ があることだから、$a\in F$ と同値である。

極大な $F'$ は Zorn の補題で存在する。$x\lor y\in F'$、$x,y\notin F'$ とする。$F'$ と $x$ で生成されるフィルターは $a$ を含むので、$f\land x\le a$ となる $f\in F'$ がある。同様に $f'\land y\le a$ である。$g=f\land f'\land(x\lor y)\in F'$ について、分配律から $g\le a$ となり、$a\in F'$ に矛盾する。$\square$

Dummett の定理

$\mathrm{LC}=\bigcap_{n\ge2}\mathrm{G}_n$ である。さらに、この論理は $[0,1]$ を鎖とする Gödel の行列の恒真式の全体に等しい。

鎖では $(x\Rightarrow y)\lor(y\Rightarrow x)=1$ なので $\mathrm{LC}\subset\mathrm{G}_n$ である。
$\varphi\notin\mathrm{LC}$ とする。$H:=H_{\mathrm{LC}}$ で $a:=[\varphi]\ne1$ である(prop-il-lindenbaum)。$a$ を含まない極大なフィルターを $F$ とすると、lem-il-quotient により $F$ は素である。$H$ で $(x\Rightarrow y)\lor(y\Rightarrow x)=1\in F$ なので、$x\Rightarrow y\in F$ か $y\Rightarrow x\in F$ である。したがって $H/F$ は全順序で、$[a]\ne1$ である。
$H/F$ の中で、$0,1$ と $\varphi$ の部分論理式の値だけを集めた有限集合を $S$ とする。全順序の Heyting 代数では含意は $1$ か第 2 引数なので、$S$ は部分代数である。$S$ は $k$ 元の鎖 $C_k$ と同型で、$\varphi$ の値は $1$ でない。よって $\varphi\notin\mathrm{G}_k$ である。
$[0,1]$ については、$C_n$ が $[0,1]$ の部分代数として埋め込まれるので、$[0,1]$ の恒真式は $\bigcap_n\mathrm{G}_n$ に含まれる。逆に $[0,1]$ の付値で偽になる式は、同じ議論で有限の鎖で偽になる。$\square$

Dummett によるこの論理の特徴づけは OLT26 §47.3 にある。単位区間の上の論理としては、多値論理 の注意「単位区間の値」の Gödel の論理である。

LC の拡張の分類

$\mathrm{LC}$ を含む中間論理は、$\mathrm{LC}$ 自身と $\mathrm{G}_n$($n\ge2$)だけである。

$L\supset\mathrm{LC}$ を中間論理とする。$\varphi\notin L$ なら、thm-il-dummett の証明を $H_L$ で繰り返すと、$L\subset\mathrm{G}_k$ かつ $\varphi\notin\mathrm{G}_k$ となる $k$ がある。実際、$H_L$ で妥当な式はその商と部分代数でも妥当である。
よって $L=\bigcap\{\mathrm{G}_k:L\subset\mathrm{G}_k\}$ である。$\mathrm{G}_{k+1}\subset\mathrm{G}_k$ なので、$\{k:L\subset\mathrm{G}_k\}$ は下に閉じている。これがすべての $k$ なら $L=\mathrm{LC}$、最大元 $n$ をもつなら $L=\mathrm{G}_n$ である。空でないのは $L\ne$ 全論理式だからである。$\square$

したがって $\mathrm{LC}$ より上の論理は
$$ \mathrm{CPC}=\mathrm{G}_2\supsetneq\mathrm{G}_3\supsetneq\mathrm{G}_4\supsetneq\cdots\supsetneq\mathrm{LC} $$
の 1 列だけで、可算個である。特に、$\mathrm{BD}$ は $C_3$ で妥当で $C_4$ で妥当でないので、$\mathrm{LC}+\mathrm{BD}=\mathrm{G}_3$ である。
実は $\mathrm{G}_3$ の位置は $\mathrm{LC}$ の上に限らない。

古典論理のすぐ下

$L\ne\mathrm{CPC}$ が中間論理なら $L\subset\mathrm{G}_3$ である。

$p\lor\lnot p\in L$ なら $L$ は $\mathrm{CPC}$ を含むので、$L\ne\mathrm{CPC}$ より $p\lor\lnot p\notin L$ である。$H:=H_L$、$a:=[p]$、$b:=a\lor\lnot a$ とおくと $b\ne1$ である(prop-il-lindenbaum)。
Heyting 代数の式から $\lnot b=\lnot a\land\lnot\lnot a=0$ である。$b=0$ なら $1=\lnot0=\lnot b=0$ となり $b=1$ と矛盾するので、$b\ne0$ である。$\{0,b,1\}$ は $\land,\lor$ で閉じ、$b\Rightarrow0=\lnot b=0$、$1\Rightarrow b=b$、$b\Rightarrow b=1$ なので $\Rightarrow$ でも閉じている。これは $C_3$ と同型な部分代数である。$H$ で妥当な式は部分代数で妥当なので、$L\subset\mathrm{G}_3$ である。$\square$

Kripke フレーム

Kripke フレーム $\mathcal F$ で $\varphi$ が 妥当 であるとは、$\mathcal F$ の上のすべての Kripke モデルのすべての点で $\varphi$ が強制されることをいう。定義は Kripke意味論 による。

フレームの論理

フレーム $\mathcal F$ で妥当な式の全体は超直観主義論理である。したがって、公理 $\alpha$ が $\mathcal F$ で妥当なら、$\mathrm{IPC}+\alpha$ の元はすべて $\mathcal F$ で妥当である。

$\mathrm{IPC}$ の元の妥当性と前件肯定で閉じることは Kripke意味論 の定理「Kripke 意味論の健全性」による。代入 $\sigma$ については、モデルの付値 $V$ に対し $V'(p):=\{w:w\Vdash\sigma(p)\}$ とおく。持続性により $V'$ は付値である。帰納法で、$V'$ での $\varphi$ の強制と $V$ での $\sigma(\varphi)$ の強制は一致する。$\varphi$ が妥当なら $\sigma(\varphi)$ も妥当である。$\square$

比較可能性と弱い排中律の対応

$\mathcal F=(W,\le)$ を Kripke フレームとする。

  1. $(p\to q)\lor(q\to p)$ が $\mathcal F$ で妥当であることと、$x\le y$、$x\le z$ なら $y\le z$ か $z\le y$ であることは同値である。
  2. $\lnot p\lor\lnot\lnot p$ が $\mathcal F$ で妥当であることと、$x\le y$、$x\le z$ なら $y,z$ の上にともにある点 $w$ があることは同値である。

1 を示す。条件が成り立たないとして、$y,z$ を比較できない $x$ の上の点とする。$V(p)=\{u:y\le u\}$、$V(q)=\{u:z\le u\}$ とおくと、$y\Vdash p$、$y\not\Vdash q$、$z\Vdash q$、$z\not\Vdash p$ なので、$x$ は $p\to q$ も $q\to p$ も強制しない。
逆に、条件が成り立つのに $x\not\Vdash(p\to q)\lor(q\to p)$ とする。$y\ge x$ で $y\Vdash p$、$y\not\Vdash q$ となる点と、$z\ge x$ で $z\Vdash q$、$z\not\Vdash p$ となる点がある。$y\le z$ なら持続性で $z\Vdash p$、$z\le y$ なら $y\Vdash q$ となり、どちらも矛盾である。
2 を示す。条件が成り立たないとして、$y,z\ge x$ に共通の上の点がないとする。$V(p)=\{u:y\le u\}$ とおくと、$y\Vdash p$ から $x\not\Vdash\lnot p$ である。$z$ の上に $V(p)$ の点はないので $z\Vdash\lnot p$ で、$x\not\Vdash\lnot\lnot p$ である。
逆に、条件が成り立つのに $x\not\Vdash\lnot p\lor\lnot\lnot p$ とする。$y\ge x$ で $y\Vdash p$ となる点と、$z\ge x$ で $z\Vdash\lnot p$ となる点がある。共通の上の点 $w$ では $w\Vdash p$ かつ $w\Vdash\lnot p$ となり矛盾である。$\square$

下の方の複雑さ

上の端の単純さと対照的に、$\mathrm{IPC}$ の近くは非常に複雑である。次の結果はこの記事では証明しない。

  • Jankov の定理:中間論理は連続体濃度だけある(Mos22 §6.1、Fus25 §3.1)。cor-il-extensions の可算性は $\mathrm{LC}$ の上に限った話である。
  • 補間:Craig の補間性質をもつ超直観主義論理は、全論理式の集合を含めてちょうど 8 個である。$\mathrm{IPC}$、$\mathrm{KC}$、$\mathrm{LC}$、$\mathrm{CPC}$ はそこに含まれる。これは Maksimova の定理で(Fus25 §3.1 Theorem 4)、代数の融合性と結びつく(代数的論理)。
  • Medvedev の論理:有限問題の論理 $\mathrm{LM}$ は中間論理で、$\mathrm{KP}$ を含む(ST06 Corollary 5.6)。

反例:条件を外すと成り立たないこと

外す条件例成り立たなくなる主張
無矛盾であること全論理式の集合$L\subset\mathrm{CPC}$(thm-il-ceiling)
代入で閉じること$p_0$ から直観主義論理で導かれる式の全体$L\subset\mathrm{CPC}$($\bot$ を含まないが $p_0$ を含む)
行列の有限性$H_{\mathrm{IPC}}$$\mathrm{IPC}$ が行列で書けないこと(thm-il-finite)
比較可能性の公理$\mathrm{IPC}$ の拡張の全体上の論理が 1 列で可算個(cor-il-extensions)
枝分かれしないこと根の上に比較できない 2 点、その上に頂点$(p\to q)\lor(q\to p)$ の妥当性
合流できること根の上に比較できない 2 点$\lnot p\lor\lnot\lnot p$ の妥当性

関連項目

参考文献

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