数理論理学 数理論理学の概要

数理論理学

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/09/22 07:17 UTC 版)

数理論理学の主な目的は形式論理の数学への応用の探求や数学的な解析などであり、共通課題としては形式的体系の表現力や形式証明系の演繹の能力の研究が含まれる。

数理論理学はしばしば集合論モデル理論再帰理論証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学(とくにACM Classification英語版に現れるもの)における数理論理学の役割の詳細はこの記事には含まれていない。詳細は計算機科学におけるロジック英語版を参照。

この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学代数学解析学に対する公理的枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか(逆数学のように)ということに焦点を当てている。

下位分野

Handbook of Mathematical Logic は数理論理学を大まかに次の4つの領域に分類している:

  1. 集合論
  2. モデル理論
  3. 再帰理論
  4. 証明論と構成的数学 (これらはひとつの領域の2つの部分と見做される)

それぞれの領域は異なる焦点を持っているものの、多くの技法や結果はそれら複数の領域の間で共有されている。これらの領域を分かつ境界線や、数理論理学と他の数学の分野とを分かつ境界線は、必ずしも明確ではない。ゲーデルの不完全性定理は再帰理論と証明論のマイルストーンであるだけではなく、様相論理におけるレープの定理英語版を導く。強制法の手法は集合論、モデル理論、再帰理論のほか直観主義的数学の研究などでも用いられる。

圏論の分野では多くの形式公理的方法を用いる。それには圏論的論理英語版の研究も含まれる。しかし圏論は普通は数理論理学の下位分野とは見做されない。圏論の応用性は多様な数学の分野に亙っているため、ソーンダース・マックレーンを含む数学者らは、集合論とは独立な数学のための基礎体系としての圏論を提案している。これはトポスと呼ばれる古典または非古典論理に基づく集合論の成す圏に類似の性質を持つ圏を基礎に置く方法である。

歴史

数理論理学は、19世紀の中頃、伝統的論理学とは独立な数学の下位分野として登場した(Ferreirós 2001, p. 443)。これが登場する以前、論理学は修辞学また哲学とともに、三段論法を通じて研究されていた。20世紀の前半は数学の基礎に関する活発な議論とともに、基本的な多くの結果が見られる。

初期の歴史

論理に関する理論は多くの文化と歴史の中で発展してきた。その中には中国インドギリシャイスラーム世界が含まれる。18世紀のヨーロッパでは、形式論理の演算子を記号的または代数的な方法の中で取り扱おうという試みが、哲学的数学者によってなされた。その中にはゴットフリート・ライプニッツランベルトが含まれる。しかし彼らの仕事は孤立して残っているばかりでよく知られていない。

19世紀

19世紀中葉、ジョージ・ブールとそしてオーガスタス・ド・モルガンは体系的で数学的な論理の取り扱いを与えた。彼らの仕事は、ジョージ・ピーコックなどの代数学者の仕事の上に打ち立てられたものであり、アリストテレスの伝統的論理学を数学基礎論の研究に十分な枠組みに拡張した(Katz 1998, p. 686)。

チャールズ・サンダース・パースはブールの研究の上に関係と量化子のための論理体系を作り上げた。彼の1870年から1885年に出版されたいくつかの論文において為された。

ゴットロープ・フレーゲは1879年に出版された彼の概念記法において、量化子を含む論理の独自の開発を提示した。この仕事は論理の歴史におけるターニングポイントを特徴づけるものであると一般に考えられている。フレーゲの仕事は、この世紀の変わり目にバートランド・ラッセルがそれを宣伝するまで、日の目を見なかった。フレーゲの2次元的な表記法は広くは受け入れられず同時代のテキストでも使用されていない。

1890年から1905年、エルンスト・シュレーダーは Vorlesungen über die Algebra der Logik を3つの巻に出版した。彼の仕事はブール、ド・モルガン、パースらの仕事をまとめ、拡張し、19世紀終わりに理解されていた記号論理学の包括的なリファレンスとなった。

基礎理論

数学が正確な基礎の上に築かれていなかったことへの不安が、算術、解析、幾何のような数学の基礎的な領域に対する公理系の開発をもたらした。

ロジックにおいて、算術自然数の理論を意味する[注 3]ジュゼッペ・ペアノ1889)は後に彼の名前で呼ばれることになった(ペアノの公理)算術の公理系を発表した。これはブールとシュレーダーの論理体系の変種を用いているが、量化記号が追加されている点で異なる。ペアノはこのときフレーゲの仕事を知らなかった。同時期にリヒャルト・デデキントは自然数の全体はそれらの帰納法の性質によって一意的に特徴づけられることを示した。デデキント(1888)は別の特徴付けを提案した。それはペアノの公理にあったような形式論理的な性格を欠いていた。しかしながらデデキントの仕事はペアノの公理においては到達できない定理を証明していた。それには自然数の集合の(同型を除いた)一意性と、加法と乗法の後者関数と数学的帰納法に基づく再帰的定義が含まれる。

19世紀中頃、ユークリッドの幾何学の公理の欠陥が世に知られるようになった (Katz 1998, p. 774)。1826年にニコライ・ロバチェフスキーによって確立された平行線公準の独立性 (Lobachevsky 1840) に加え、数学者達は、ユークリッドが明らかと考えていた幾つかの定理が、実際には彼の公理からは証明できないことを発見した。それらの中には、直線は少なくとも二点を含むという定理や、同じ半径を持ち中心が半径と同じ距離だけ離れている二つの円は交わらねばならないという定理がある。ヒルベルト (1899) はパッシュの先行研究 (1882) のもとに、完全な幾何学の公理英語版の集合を開発した。幾何学の公理化の成功はヒルベルトに他の数学の分野(自然数や数直線など)の完全な公理化の探求するよう動機付けた。これが20世紀前半の主要な研究領域となることが分かる。

20世紀

20世紀の最初の10年における研究の主領域は集合論と形式論理であった。非形式的な集合論におけるパラドックスの発見は、数学それ自身が無矛盾であるのかを疑わせるものであり、無矛盾性の証明の必要に迫られた。

1900年、ダフィット・ヒルベルトヒルベルトの23の問題の幾つかを次の世紀へと提出した。その最初の2つは連続体仮説の解決と初等算術(実数論)の無矛盾性の証明であった。第10番は整数上の多変数多項式からなる方程式(ディオファントス方程式)が解を持つかを決定する手続きを求めるものであった。これらの問題を解くための次なる仕事は、数理論理学の方向性を決定づけ、1928年に提出されたヒルベルトのEntscheidungsproblem英語版(決定問題)を解決する努力へと向かわせた。この問題は与えられた形式化された数学的言明について、それが真か偽かを決定する手続きを問うた。

集合論とパラドックス

エルンスト・ツェルメロ1904)は任意の集合が整列可能であることの証明を与えた。この結果はゲオルク・カントールには得ることができなかったものである。ツェルメロはその証明を完成させるために選択公理を導入した。これは数学者と集合論の先駆者達の間の激しい論戦と研究を引き起こすことになる。即座に浴びた批判から、ツェルメロは自身の結果の第2の解説を出版した(Zermelo 1908a)。この論文は彼の証明に対する批判に直接対処するものであり、これによって数学界において選択公理が広く受け入れられることになった。

選択公理に関する疑念は最近の素朴集合論におけるパラドックスの発見により強化された。チェザーレ・ブラリ・フォルティ(1897)は集合論のパラドックスについて述べた最初の人である:ブラリ・フォルティのパラドックスは全ての順序数からなる集まりが集合を成さないことを示す。その直後に、バートランド・ラッセルは1901年にラッセルのパラドックスを、ジュール・リシャール1905)はリシャールのパラドックスを発見した。

ツェルメロ(1908b)は集合論に対する最初の公理化を与えた。それらの公理にアドルフ・フレンケルによる置換公理を加えたものは今日ではツェルメロ=フレンケル集合論(ZF)の名で知られる。ツェルメロの公理にはラッセルのパラドックスを回避する為のサイズの制限の原理が組み込まれた。

1910年にアルフレッド・ノース・ホワイトヘッドバートランド・ラッセルによる プリンキピア・マテマティカ の第一巻が出版された。この重要な著作は、関数と基数に関する理論を型理論の完全に形式的な枠組みの中で展開した。型理論はパラドックスを回避するラッセルとホワイトヘッドの努力のもとに開発されたものである。型理論の枠組みは数学の基礎理論として普及しなかったけれども(Ferreirós 2001, p. 445)、プリンキピア・マテマティカ は20世紀の最も影響力のある研究のひとつと見做されている。

フレンケル(1922)は選択公理が原子英語版付きツェルメロ集合論の残りの公理からは証明できないことを証明した。後のポール・コーエン(1966)による仕事は、(その証明には)原子の追加が不要であって、選択公理はZFにおいて証明不可能であることを示した。コーエンの証明は強制法の手法を生み、今日では集合論における独立性結果英語版を確立する為の重要なツールとなっている[注 4]

記号論理

レオポルト・レーヴェンハイム英語版1915)とトアルフ・スコーレム1920)はレーヴェンハイム-スコーレムの定理を得た。これは一階述語論理は無限構造の濃度を制御できないことを述べる。スコーレムは、この定理を一階で形式化された集合論へ適用でき、そのいかなる形式化も可算モデルを持つことが導かれる、ということに気付いた。この直観に反する結果はスコーレムのパラドックスとして知られることになった。

ゲーデルは自身の博士論文(1929)において完全性定理を示した。これは一階論理における構文論と意味論の間の対応を確立する。ゲーデルは完全性定理をコンパクト性定理の証明に用いた。これは一階の論理的帰結の有限性を立証する。これらの結果は一階論理を数学者にとって支配的な論理として確立することを助けた。

1931年、ゲーデルはプリンキピア・マテマティカとそれに関連する体系において形式的に決定不可能な命題について英語版を出版した。ここでは、十分に強く、実効的な一階理論が不完全(完全性定理のそれとは異なる意味である)であることを示されている。この結果はゲーデルの不完全性定理として知られ、数学の公理的基礎の厳密な限界を示すものであり、ヒルベルト・プログラムに大きな打撃を与えた。これは算術の無矛盾性をいかなる算術の形式理論においても証明できないことを示している。しかしながら、ヒルベルトは、不完全性定理の重要性を、あるときまで認めなかった。

ゲーデルの定理は、十分に強く、実効的な公理系の無矛盾性の証明は、それが無矛盾である限り、それ自身からも、それよりも弱い体系からも、得られないことを示す。これはいま考えている体系で形式化できないような無矛盾性証明の可能性については未解決のまま残す。ゲンツェン(1936)は算術の無矛盾性を超限帰納法の原理を持つ有限的な体系を用いて証明した。ゲンツェンの結果はカット除去と証明論的順序数の概念を生み出し、これらは証明論における主要な道具となった。ゲーデル(1958)は別の無矛盾性証明を与えた。これは古典算術の無矛盾性を高階直観主義算術の無矛盾性に還元することで為された。

他の分科の始まり

アルフレッド・タルスキモデル理論の基礎を発展させた。

1935年初頭、著名な数学者らは網羅的な数学の教科書のシリーズを出版するためにニコラ・ブルバキというペンネームで集結した。これらの教科書は禁欲的かつ公理的に記述されており、厳格な記述と集合論的な基礎を強調した。これらの教科書から生まれた用語、例えば全単射単射全射や、教科書で採用された集合論的な基礎は、広く数学に採用された。

計算可能性の研究は再帰理論として知られるようになった。これはゲーデルとクリーネによる計算可能性の初期の定式化が関数の再帰的定義に基づいていたことによる[注 5]。それらの定義がチューリングによるチューリング機械を用いた定式化と同値であることが示されたことで、計算可能関数という新しい概念が見出され、またこの定義が多数の独立な特徴付けを許すようなロバスト性を持つことが明らかになった。1931年の不完全性定理に関するゲーデルの仕事において、彼は実効的な形式的体系の厳格な概念(規定)を欠いていた。彼は計算可能性の新しい定義が不完全性定理の設定の一般化に使えることに気付いた。

再帰理論における多くの結果は1940年代にスティーヴン・コール・クリーネエミール・ポストによって得られた。クリーネ(1943)は相対的計算可能性と算術的階層の概念を導入した。前者はチューリング(1939)で暗示されていたものである。クリーネは後に再帰理論を高階汎関数へ一般化した。クリーネとクライゼルは形式的な直観主義数学、とくに再帰理論の文脈でのそれを研究した。


注釈

  1. ^ 以下、『岩波 数学入門辞典』からの引用[3]

    数理論理学
     mathematical logic

     数学の理論を展開する際にその骨格となる論理の構造を研究する分野をいう.数学基礎論とほぼ同義である.[3]
  2. ^ 以下、『岩波 数学入門辞典』からの引用[4]

    数学基礎論
     foundations of mathematics

     数理論理学や超数学とほぼ同じ意味で,論理を扱う数学の一分野である. … ゲーデルの不完全性定理有限の立場(形式主義)で数学の無矛盾性を証明することはできないことを示した.ゲンツェン(Gentzen)は,有限の立場より緩い制限のもとで自然数論の無矛盾性を証明した.
     数学基礎論は計算機科学〔コンピュータ科学〕とも密接に結びついている.[4]
  3. ^ これに反してヒルベルトの第2問題における「算術」は実数論のことであって自然数論のことではない。
  4. ^ See also Cohen 2008.
  5. ^ この用語に関する詳しいサーベイはSoare (1996)による。
  6. ^ Ferreirós (2001) surveys the rise of first-order logic over other formal logics in the early 20th century.

出典

  1. ^ a b 『日本大百科全書』
  2. ^ a b 『世界大百科事典 第2版』
  3. ^ a b c d 青本 et al. 2005, p. 297.
  4. ^ a b c d e 青本 et al. 2005, p. 294.
  5. ^ Undergraduate texts include Boolos, Burgess, and Jeffrey (2002), Enderton (2001), and Mendelson (1997). A classic graduate text by Shoenfield (2001) first appeared in 1967.


「数理論理学」の続きの解説一覧




固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

数理論理学のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



数理論理学のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの数理論理学 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2022 GRAS Group, Inc.RSS