数理論理学

Wikipedia

ウィキペディアに数理論理学の記事があります。

論理とは

論理とは、簡単に言えばある問題の答えを出すための思考方法の一つである。ただ、其の様な意味だとこの書で扱うには少し広義すぎるので、以降では論理とはすなわち「真と偽が判定可能な命題の真偽を判定する事」を指すものとして捉えて欲しい。数理論理学では、大抵このような論理しか扱わないのである。コレ以外の論理、つまり答えが「真偽判定不能」となるような命題を考える事はここではしない。例としては以下のようなものとなる

アルキメデスは人間である　 …命題P

人間は皆死ぬ　　　　　　　…命題Q

故に、アルキメデスは死ぬ　…命題A

これは有名な三段論法の一種である。結論は最後の行である。三段論法によって命題Pと命題Qが真ならば、Aも真であることが保証される。

数理論理学とは

数理論理学とは、数学で使う「論理」をより数学的にしたもので、自然言語の代わりに記号による表記を行い、機械的な式変形を容易にした形式である。記号による表記に特化している、という特徴から「記号論理学」とも呼ばれるが、これは数理論理学と同義なので混乱しないようにしてほしい。以降、この書では「数理論理学」という語で統一することとする。

まず、数理論理学をこれから学習するならば、「論理とは言葉で考えるもの」という様なこれまでの常識は捨ててほしい。数理論理学においては、論理とは「真(True)」か「偽(False)」の二つの値しかもたない集合への「写像」として捉えられる。必ず「真」か「偽」のどちらかになり、「真偽不明」などといった値は持たないので、数理論理学では曖昧な議論は不可能である。この点は注意して欲しい。実際は通常の論理よりも、扱える守備範囲自体は狭いのである。ただし、扱える守備範囲においては強力な威力を発揮する理論でもある。数理論理学は「論理」を一つの写像として数学的に考える事で、論理自体に一種の「演算規則のようなもの」が見出せる。例えば、「AかつB」という文は、数理論理学では記号「A∧B」で表し、一種の演算として扱う。まさしく数学で言う「A×B」のような扱いにするのだ。この演算の規則を見出すことで命題を色々な形に変形し、簡単に出来るのがこの学問の強みだろう。

上記のアルキメデスの例を数理論理学的に表現してみると、以下のようになる。

P\wedge Q\Rightarrow A

記号「∧」は「かつ」、記号「⇒」は「ならば」と読む。これを日本語として読むと

P かつ Q ならば A である

となるので、自明であることはすぐにわかるだろう（もっとも三段論法の理解が必要ではあるが）。このように、論理を記号として表現するのが数理論理学である。なぜそんなことをするのかというと、式変形を容易におこなえるという強力な利点があるからである。

記号の導入

数学を、一切の形式的な視点から構成する（すなわち、単なる記号操作として捉える）場合、以下の記号を出発点とする。

対象記号： $c_{0},c_{1},c_{2},{\text{...}}$
関数記号： $f_{0},f_{1},f_{2},{\text{...}}$
述語記号： $P_{0},P_{1},P_{2},{\text{...}}$
自由変数： $a_{0},a_{1},a_{2},{\text{...}}$
束縛変数： $x_{0},x_{1},x_{2},{\text{...}}$
論理記号： $\neg$ （否定）、 $\wedge$ （論理積）、 $\vee$ （論理和）、 $\rightarrow$ （含意）、 $\forall$ （全称量化子）、 $\exists$ （存在量化子）
括弧：(、)

※関数記号と述語記号には、m個の自由変数が含まれるものとする。

数学の形式的な構成において、変数、論理記号、括弧はすべての数学に共通して使われる。しかし、対象記号、関数記号、述語記号はそれぞれの論（自然数論、集合論など）に固有のものである。であるから、各論の対象記号、関数記号、述語記号の集合は $L$ として書かれる。

例

自然数論では、対象記号として $0$ 、関数記号として $m'$ （後者関数）、 $(m_{1})+(m_{2})$ 、 $(m_{1})*(m_{2})$ 、述語記号として $m_{1}=m_{2}$ を持つ。ここで、 $m$ 、 $m_{1}$ 、 $m_{2}$ は自由変数として含まれている。これが先の注釈の意味である。
集合論では、対象記号と関数記号を持たず、述語記号として $m_{1}\in m_{2}$ のみを持つ（外延性公理を等号の定義と見なさなければ、 $m_{1}=m_{2}$ も）。

項

何が項であるかは、以下のように厳密に定められる。

自由変数および対象記号は項である。
$f$ がn個の自由変数を持つ関数記号であり、 $t_{0},t_{1},t_{2},\ldots ,t_{n-1}$ が項ならば、 $f(t_{0},t_{1},t_{2},\ldots ,t_{n-1})$ も項である。
上記の規則によってのみ得られるものだけが項である。

例

自然数論の場合、 $0$ は項である（規則1）。 $0'$ 、 $(0')'$ 、 $0+0'$ 、 $(0')'*0'$ も項である（規則2）。しかし、「数+学」は項ではない（規則3）。
公理的集合論の場合、自由変数のみが項である。このとき、 $\emptyset$ はあくまで略記号で、議論に必須ではない。 $x=\emptyset \Leftrightarrow \forall y(y\notin x)$ と定義されるから、例えば、論理式 $P(\ldots ,\emptyset ,\ldots )$ があれば、 $P(\ldots ,x,\ldots )\wedge \forall y(y\notin x)$ と置き換えればよろしい。