数理論理学
数理論理学(独: mathematische Logik、英: mathematical logic)は、論理学(形式論理学)の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。[1]数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。
数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学(とくにACM Classification)における数理論理学の役割の詳細はこの記事には含まれていない。詳細は計算機科学における数学を参照。
この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか(逆数学のように)ということに焦点を当てている。
Contents
下位分野
Handbook of Mathematical Logic は数理論理学を大まかに次の4つの領域に分類している:
それぞれの領域は異なる焦点を持っているものの、多くの技法や結果はそれら複数の領域の間で共有されている。これらの領域を分かつ境界線や、数理論理学と他の数学の分野とを分かつ境界線は、必ずしも明確ではない。ゲーデルの不完全性定理は再帰理論と証明論のマイルストーンであるだけではなく、様相論理におけるレープの定理を導く。また集合論や逆数学における独立性証明の基本的な道具とされる。強制法の手法は集合論、モデル理論、再帰理論のほか直観主義的数学の研究などでも用いられる。
圏論の分野では多くの形式公理的方法を用いる。それには圏論的論理の研究も含まれる。しかし圏論は普通は数理論理学の下位分野とは見做されない。圏論の応用性は多様な数学の分野に亙っているため、ソーンダース・マックレーンを含む数学者らは、集合論とは独立な数学のための基礎体系としての圏論を提案している。これはトポスと呼ばれる古典または非古典論理に基づく集合論の成す圏に類似の性質を持つ圏を基礎に置く方法である。
数理論理学の発祥
言葉を、代数学におけると同様に文字や記号の列で表して、その変換について研究するいわゆる記号論理学、数理論理学の発祥は、19世紀のジョージ・ブールによる「論理代数」、ゴットロープ・フレーゲの書『概念記法』に見ることができる。前者は命題論理、後者は述語論理の原型である。数学自体を数学によって研究する数学基礎論は、数理論理学なしにはあり得ないものである。
たとえば数理論理学の一分科である命題論理では、「風が吹いた」という観念を文字 A で表し「桶屋が儲かる」という観念を 文字 B で表したとき、「風が吹いたならば桶屋が儲かる(風が吹けば桶屋が儲かる)」という観念を A ⇒ B などと表す。ここに、記号 ⇒ は「前の概念が正しければ(真ならば)、後ろの概念も正しい(真である)」ということを表し、A ⇒ B を「A ならば B」と読む。
数理論理学の諸体系
数理論理学の体系は、論理式を構成する文法及び推論規則によって構成される。
上記文法及び推論規則の違いにより、命題論理・述語論理・様相論理等々の体系が存在する。
命題論理と述語論理を古典論理とし、その他の論理を非古典論理とすることがある。
命題論理
命題論理では、論理式は原子論理式および
- 論理式から論理記号によって論理式を作る文法
によって定められる。
具体的には、論理式 A, B, ... から論理記号 ∧, ∨, ¬, ⇒ によって、A ∧ B, A ∨ B, ¬A, A ⇒ B なる論理式が作られる。A ∧ B は論理積、A ∨ B を論理和、¬A を A の否定、A ⇒ B を論理包含という。なお、記号は研究者・流派によって、たとえば ⇒ のほかに →, ⊃ や、 ¬ のほかに ∼ など異なるものが用いられることがあるが、いずれも同じものである。⇒ と → を使い分ける流儀もある。
ブール論理
ブール論理ではブール代数で形式化され2値の意味論を与えられた命題論理である。
述語論理
述語論理では、さらに原子項、及び
- 項から関数記号によって項を作る文法
- 項から述語記号によって論理式を作る文法
によって定められる。
具体的には n 個の項 x1, x2, ..., xn と n 変数関数記号 f によって項 f(x1, x2, ..., xn) が、そして、n 変数述語記号 p によって論理式 p(x1, x2, ..., xn) が作られる (n = 0, 1, 2, ...)。
さらに論理式 A, B, ... から論理記号 ∀(「すべての」を意味する), ∃(「存在する」を意味する) によって ∀x A(すべてのxでAが真), ∃x A(Aが真となるxが存在する) なる論理式が作られる(量化)。
様相論理
様相論理では、さらに様相記号を用いる。
論理式から論理式を導き出す推論規則として、たとえば論理式 A と A → B とから B を導くことができる。これは三段論法の一種である。三段論法とは、F → G, G → H から F → H を導く推論規則で、より正確には
- ∀ x {(G(x) ⇒ H(x)) ∧ (F(x) ⇒ G(x))} ⇒ {F(x) ⇒ H(x)}
すなわち「すべての x で、F ならば G、かつ、 G ならば H が真ならば、F ならば H は真である」ということである。これは集合を用いれば
- ({x|G(x)} ⊆ {x|H(x)}) ∧ ({x|F(x)} ⊆ {x|G(x)}) ⇒ ({x|F(x)} ⊆ {x|H(x)})
と表せる。
他
数理論理学の諸分科
数理論理学の各分科での研究課題は、大きく証明論・意味論に分けられる。
証明論
証明論とは数学における証明を記号列と見なす立場(つまり syntax の立場)からの研究であり、20世紀初頭にヒルベルトにより数学の基礎付けを目的として創始された。この方面での重要な成果としては、ゲンツェンによる LK の基本定理、すなわち「式 S が LK で provable ならば、S は LK で三段論法なしでも provable である」があげられる。この定理は「対偶や背理法のような間接証明法を用いて証明できる命題は、間接証明法を用いなくても証明できる」というようなことを一般化した、論理について成り立つ非常に美しい法則である。基本定理の応用としては、命題論理・述語論理の無矛盾性、そして命題論理の決定可能性がある。また、この方面の研究としては同じくゲンツェンによる自然数論の無矛盾性の証明があげられる。
意味論
意味論では、論理式で記述される命題の「意味」を、何らかの数学的対象に写像した上で、これらの数学的対象を研究する。述語論理における意味の与え方の一例としては、実在物 (Entity) の全体の集合 E と真偽の集合 {0, 1} との直和を世界と定め、素項の集合から E への写像 f の各々に述語言語から世界への意味写像 f ∗ を対応させる規則を然るべく定め、 意味写像を用いて論理式の真偽の概念を定める等々の方法がある。この方面での重要な成果としてはゲーデルの完全性定理があげられる。これはどのような意味の与え方によっても真となる述語論理の論理式と、述語論理の体系から provable となる論理式は、一致するというものである。
関連項目
脚注