数理論理学：ノート1 - クッキーの日記

この本を読みます。

数理論理学
戸次大介

東京大学出版会 2012-03
売り上げランキング : 498190

Amazonで詳しく見る by G-Tools

以下、第2章の自分の理解（第1章は予備知識なので省略）。

我々は数学の証明問題を解くことができる。例えば以下のように。
- 教科書の例は「数学ガールの秘密ノート」第178回で "僕" が出した問題と同じだけど、長いのでミルカさんの問題にする。
  - 第178回背理法をめぐって（後編）｜数学ガールの秘密ノート｜結城浩｜cakes（ケイクス）

例題　　実数 $\alpha$ に収束する実数列 $\{ a_n \, | \, n \in \mathbb{N} \}$ について，任意の $n$ で $a_n < A$ ならば， $\alpha \leqq A$ である．

証明

(1)　 $\alpha > A$ であると仮定する．
(2)　 $\alpha - A = \varepsilon_0$ とおく．
(3)　(1) と (2) より， $\varepsilon_0 > 0$ である．
(4)　 $\displaystyle \lim_{n \to \infty} a_n = \alpha$ より， $\varepsilon_0 > 0$ に対してある $N_0$ が存在して，任意の $n > N_0$ で $| a_n - \alpha | < \varepsilon_0$
　　である．
(5)　(4) より，任意の $n > N_0$ で $\alpha - \varepsilon_0 < a_n < \alpha + \varepsilon_0$ である．
(6)　(2) と (5) より，任意の $n > N_0$ で $A < a_n < \alpha + \varepsilon_0$ である．
(7)　(6) は任意の $n$ で $a_n < A$ であることに矛盾する．
(8)　(1) と (7) より， $\alpha > A$ ではない．
(9)　(8) より， $\alpha \leqq A$ である．

でもこのようにして証明した定理はどのように "妥当" なのだろうか。物理や化学や生物学、社会学だったら、見出した定理がどのように妥当かは、現実世界の現象をどれくらいよく説明するかということになる。というかそれらの学問の目的が現実世界の現象をよく説明することである。でも数学はそういうんじゃない。
- このくだりの教科書での表現はこのようなものではなく、「特定の力学の理論が『正しい』ということを証明することはできない」（理論にしたがわない現象が観測されれば反証されてしまうから）（14ページ）。でも数学は特別だと。
数学的な訓練を受けたもの同士では（14ページ）、ある程度「この証明は妥当っぽい」とわかり合えるけど、そういう曖昧な感じでは駄目なので、「妥当な証明とは何か」をちゃんと考えることにする。それを考える学問が論理学になる。

「妥当な証明とは何か」はまず「証明とは何か」から考える。上の例をみると、証明とは、文章を順番に並べたものであって、個々の文章は「 $\varphi$ である」「 $\varphi$ ではない」「 $\varphi$ より， $\psi$ である」のような形式をしている。

$\varphi$ や $\psi$ の位置にくるものは、真偽を問うことのできる形式（≡ 命題）といえる。実際、以下の (b)，(c) のような形式は証明につかわない（但し、厳密には「真偽が問えるとは何か」は論理体系による）。なお、命題に「である」「ではない」を付けたり、命題どうしを「かつ」「または」で結んだりしたものもまた真偽を問える命題になる。

(a)　3は偶数である　 $\cdots$ 真偽が問えるので、命題
(b)　3は偶数だと思う　 $\cdots$ 真偽が問えないので、命題ではない
(c)　ペンパイナッポーアッポーペン　 $\cdots$ 真偽が問えないので、命題ではない

また、証明は命題の順不同な羅列ではなく、「 $\varphi_1, \cdots, \varphi_n$ より， $\psi$ である」のように命題（たち）から命題を導いていく。この形式を推論とよび、「 $\varphi_1, \cdots, \varphi_n \Rightarrow \psi$ 」とかく。また、この推論（たち）から推論を導くこともある。例えば、以下のような3ステップの証明が考えられる。

(1)　 $\varphi_1 \Rightarrow \varphi_2$ 　 $\cdots$ 命題から命題を導出＝推論
(2)　 $\varphi_2 \Rightarrow \varphi_3$ 　 $\cdots$ 命題から命題を導出＝推論
(3)　(1) と (2) より， $\varphi_1 \Rightarrow \varphi_3$ 　 $\cdots$ 推論たちから推論を導出

この証明が妥当であるには、(1)，(2) の推論が妥当な推論であり、(3) の「推論たちからの推論の導出」も妥当なものでなければならない（このうち後者のような手法の妥当性については、「妥当な推論とは何か」を決めた後で別に取り扱う）。「妥当な推論とは何か」については、この本では「意味論的推論」に基づき、「『前提の命題がすべて真であって、帰結の命題が偽である状況』が存在しない」ときにその推論を妥当とすることにする。

(a)　すべて真である命題たち $\Rightarrow$ 真である命題　　　 $\cdots$ 妥当な推論
(b)　すべて真である命題たち $\Rightarrow$ 偽である命題　　　 $\cdots$ 妥当ではない推論
(c)　~~偽であるものを含む~~すべて真ではない命題たち $\Rightarrow$ 真である命題　 $\cdots$ 妥当な推論
(d)　~~偽であるものを含む~~すべて真ではない命題たち $\Rightarrow$ 偽である命題　 $\cdots$ 妥当な推論
恒偽式を含まなくても命題どうしが矛盾することがあるという意味で訂正（ 2017-01-07 ）

こうしてみると、「妥当な証明とは何か」は、以下を決めれば決まる。

1.　推論とは何か → つまり、命題とは何か（推論とは「命題たち $\Rightarrow$ 命題」なので）
2.　妥当な推論とは何か → つまり、命題のうち真（偽）であるものとは何か

このうち、形式を定める 1. を統語論（syntax）といい、定めた形式の意味を決める 2. を意味論（semantics）という。この本の第Ｉ部の残りでは、「一階命題論理」と「一階述語論理」という形式体系において「妥当な証明とは何か」をどう定めるか（つまり、この「統語論」と「意味論」をどう定めるか）をみていく。