直観主義論理の真理値について: Gödel: "Zur intuitionistischen Aussagenkalkül" (1932)を読む

入門書による独学でも大学の講義でも記号論理学の初歩として学ぶと思われるのは(古典論理の)真理値表の概念と計算方法である。そして少し進んだ講義ではそのあとに証明体系としてシーケント計算よりも自然演繹を学ぶところが多いのではないかと思う¹。

真理値表では意識することなく古典論理を扱っているのに対し、自然演繹では複数の体系、直観主義論理と古典論理(と最小論理)が登場する。真理値表と自然演繹を学んだ後で勘のよい学生は以下のような疑問を持つかもしれない。

古典論理命題論理と二値の真理値表が対応するのならば、直観主義命題論理にはどのような真理値表が対応するのだろうか？

この疑問の答えは以下のようになる。

直観主義命題論理を多値論理と見做すことはできない。つまり、いかなる真理値表も対応しない。

このことは不完全性定理で有名であるゲーデルが1932年に短いノート"Zur intuitionistischen Aussagenkalkül"(直観主義命題論理について)で証明している²。この結果は後に中間論理と呼ばれる分野の先駆的研究となっている。さらに直観主義論理が選言特性(disjunction property)と呼ばれる重要な性質を満たすことにも言及している(証明はされていない)。ノートは解説を除くと1ページ程度の長さであり、英訳も載っているので読んでみるのも良いだろう。

以下(Gödel, 1932)での証明について解説する。ゲーデルは二つの命題を述べている。ゲーデルによる一番目の命題の表現は少しわかりにくいのでTroelstraの解説の定式化を引用する(p.222-223)³。

(1) [Intuitionistic Propositional logic] $\bf{H}$ cannot be viewed as a system of many-valued logic.

(that is to say, we cannot find a finite set $M$ of truth values, with a subset $D\subset M$ of designeated values, plus an interpretation of $\to, \land, \lor$ by binary operations on $M$ and an interpretation of $\lnot$ by a unary operation on $M$ , such that $H\vdash A$ iff, for all valuations $\phi$ in $M$ , $\phi(A)\in D$ ) ⁴.

(2) There is an infinite descending chain of logics intermediate in strength between $\bf{A}$ (classical propositional logic) and $\bf{H}$ .

(2)を仮定して(1)を示す。もし直観主義論理が多値論理(i.e. 有限個の真理値を持つ)だとする。古典論理から直観主義論理までの多値論理体系のchainを考えると長さは有限。これは(2)と矛盾する。よって(1)が成り立つ。

(1)は(2)の系のようなものであり、ゲーデルは(2)の証明のスケッチのみを書いている⁵。

ゲーデルは次の定義を与えている。記号は一部現代風に書き直したものがある。

論理式 $F_n$ を以下の式で定義する。

$\displaystyle{\sum_{1\le i \lt k\le n}(A_i \leftrightarrow A_k)}$

体系 $S_n$ の解釈を以下で定義する。

真理値の有限集合: ${1,2,\dots, n}$ ,

designated element (value): 1,

$a\lor b=min(a, b)$ ,

$a\land b=max(a, b)$ ,

$a\to b=1$ for $a\geq b$ ,

$a\to b=b$ for $a\lt b$ ,

$\lnot(a=n)$ for $a \neq n$ ,

$\lnot (n=1)$ .

自分で考えてみたい人はここまでで一旦読むのをやめて手を動かしてみるのが良いでしょう。 $F_n$ の具体例を考えてみる。 $F_2=a_1\leftrightarrow a_2$ ,

$F_3=(a_1\leftrightarrow a_2)\lor (a_1\leftrightarrow a_3)\lor (a_2\leftrightarrow a_3)$ .

二値の真理値を持つ場合に $F_3$ を考えてみよう。変数が3つあるのに対して、値は二つしかない。なのでどうやっても一つの値は重複して現れることになる⁶。

重複する値を $e$ とすると、 $(e\leftrightarrow e)=1$ が現れることになるので選言全体も1となる。これは体系がn値を持つ場合に(i.e. $S_n$ で) $F_{n+1}$ と $n+1\lt i$ とであるすべての $F_i$ が成り立ち、 $F_{n}$ と $j\lt n$ であるすべての $F_j$ が成り立たないことになる。つまり古典論理では $F_3$ 以降の式は全て成り立ち、 $S_3$ (3値論理)では $F_4$ 以降は全て成り立ち・・・と強さに関して段々と真に減少していくchainを直接に構成できたことになる。以上が証明の概略である。

この記事では命題論理のみを扱う。以下では適宜「命題」,「命題論理」という語を省略している。↩
K.Gödel, Zur intuitionistischen Aussagenkalkül, Anzieger der Akademie der Wissenschaften in Wien 69, 1932, 65-66. 我々はK.Gödel, Collected Works I, S.Feferman et al. (eds), Oxford University Press, 1985 pp.222-225のテキストとTroestraによる解説を参照した。↩
日本語で書くと(1) 直観主義命題論理は多値論理の体系として見做すことはできない。(2) 古典命題論理と直観主義命題論理の間には強さにおいて中間的な無限長の論理体系の降下列が存在する。↩
健全かつ完全となるような多値論理モデルはないということ。↩
以下は技術的に興味がない人は読む必要はありません。↩
鳩の巣原理↩

Asinus's blog

西牟田祐樹のブログです。

直観主義論理の真理値について: Gödel: "Zur intuitionistischen Aussagenkalkül" (1932)を読む