20世紀の数理論理学 ― ゲーデルとタルスキを中心に
ヒルベルトの問題提起から不完全性定理、真理の定義、モデル理論の誕生、そして独立性の時代へ。20世紀に数理論理学がどのように形づくられたかを、クルト・ゲーデルとアルフレト・タルスキの業績を軸にたどる。
1900年代
ヒルベルト、パリ国際数学者会議で23の問題を提示
第2問題として算術の公理系の無矛盾性の証明を、第10問題としてディオファントス方程式の可解性を判定する手続きを求めた。20世紀の数学基礎論の出発点となる。
アルフレト・タルスキ誕生
ワルシャワに生まれる（出生名はアルフレト・タイテルバウム）。
ラッセル、フレーゲにパラドックスを伝える
「自分自身を要素として含まない集合全体の集合」が矛盾を生むことを手紙で指摘。素朴集合論とフレーゲの論理体系の破綻が明らかになり、基礎の見直しが始まる。
クルト・ゲーデル誕生
オーストリア＝ハンガリー帝国のブリュン（現チェコのブルノ）に生まれる。
ツェルメロの公理的集合論とラッセルの型理論
ツェルメロが集合論の公理系を発表し、ラッセルは型の理論によってパラドックスの回避を図った。パラドックスへの二つの代表的な処方箋が出揃う。
1910年代
ホワイトヘッドとラッセル『プリンキピア・マテマティカ』（〜1913年）
数学全体を論理から導こうとした大著。後にゲーデルの不完全性定理の論文が直接の対象とする体系となる。
レーヴェンハイムの定理
可算な言語の一階の文が無限モデルを持つなら可算モデルも持つことを示す。1920年にスコーレムが一般化し、レーヴェンハイム＝スコーレムの定理となる。
1920年代
ZF 集合論の成立へ
フレンケルとスコーレムがツェルメロの公理系に置換公理を補い、今日の標準である ZF 集合論の形が整う。
バナッハ＝タルスキのパラドックス
選択公理を用いると、三次元の球を有限個の部分に分割して並べ替え、元と同じ大きさの球を2つ作れることを示した。同年、タルスキはワルシャワ大学で博士号を取得している。
ヒルベルトとアッケルマン『理論論理学の基礎』
一階述語論理の完全性（正しい論理式はすべて証明できるか）を未解決問題として提示した。同時期にヒルベルトは決定問題（Entscheidungsproblem）を定式化する。
プレスブルガー算術の決定可能性
タルスキのゼミの学生プレスブルガーが、加法だけの自然数の理論は決定可能であることを量化子消去で示す。乗法を加えると状況が一変することは、後にゲーデルによって明らかになる。
ゲーデル、完全性定理を証明
ウィーン大学の博士論文（指導教員ハンス・ハーン）で、一階述語論理では意味論的に正しい論理式がすべて証明可能であることを示した。ヒルベルトとアッケルマンの問いへの肯定的な解答で、1930年に出版された。
1930年代
タルスキがウィーンで講演、ゲーデルと出会う
メンガーの招きでウィーンを訪れ、メタ数学について講演した。ゲーデルはこの講演を聴いて議論を交わしたとされ、二人の長い交流が始まる。
ケーニヒスベルク会議で第一不完全性定理を予告
数学基礎論の会議の最終日の討論で、ゲーデルは無矛盾な形式体系には証明も反証もできない算術の命題があることを短く述べた。その場で意義を理解したのはフォン・ノイマンだったと伝えられる。
不完全性定理の論文が出版される
「『プリンキピア・マテマティカ』および関連する体系における形式的に決定不能な命題について I」。第一不完全性定理（十分に強い無矛盾な体系は不完全である）と第二不完全性定理（その体系は自らの無矛盾性を証明できない）を示し、ヒルベルト計画に根本的な限界を突きつけた。ゲーデル数化と対角化の手法は後の計算理論の基礎となる。
タルスキ「形式化された言語における真理概念」
形式言語の文について「真である」ことを厳密に定義し、規約T（「雪は白い」が真であるのは雪が白いときに限る）を定式化した。さらに、十分に強い言語の真理述語はその言語自身の中では定義できないこと（真理の定義不可能性定理）を示し、対象言語とメタ言語の区別を確立する。1935年のドイツ語版で国際的に広まった。
ゲーデルのプリンストン講義と一般帰納的関数
プリンストン高等研究所での講義で、エルブランの示唆をもとに一般帰納的関数を定式化した。「計算可能な関数とは何か」を定義する試みの一つとなる。
チャーチとチューリング、決定問題を否定的に解決
チャーチはλ計算を用いて、チューリングはチューリングマシンを用いて、一階述語論理の正しさを判定する一般的な手続きが存在しないことを示した。不完全性定理の発想は、計算の限界の理論へと受け継がれる。
ゲンツェン、算術の無矛盾性を証明
ε₀ までの超限帰納法を用いて、ペアノ算術の無矛盾性を証明した。第二不完全性定理と矛盾しない形で、どのような原理を使えば無矛盾性を示せるかを明らかにした。
ロッサーによる不完全性定理の強化
ゲーデルの第一不完全性定理で必要だったω無矛盾性の仮定を、単なる無矛盾性へと弱めた（ロッサーのトリック）。
タルスキ「論理的帰結の概念について」
文の集まりから文が論理的に帰結することを、前提を真にするすべての解釈で結論も真になること、として定義した。今日のモデル理論的な帰結関係の原型となる。
ゲーデル、選択公理と連続体仮説の無矛盾性を証明
構成可能集合の宇宙 L を導入し、ZF が無矛盾なら ZF に選択公理と一般連続体仮説を加えても無矛盾であることを示した（詳細は1940年のモノグラフ）。連続体仮説は否定できないことが分かった。
タルスキ、アメリカへ渡る
ハーバード大学で開かれる統一科学会議に出席するため渡米した直後、ドイツがポーランドに侵攻した。帰国できなくなったタルスキはそのままアメリカに留まり、家族とは戦後まで離ればなれとなる。
1940年代
ゲーデル、プリンストン高等研究所へ
ナチス併合後のオーストリアを離れ、シベリア鉄道と太平洋航路を経てアメリカへ移住した。以後、生涯をプリンストンで過ごし、アインシュタインと親交を深める。
タルスキ、カリフォルニア大学バークレー校へ
バークレー校に職を得て、ここを世界有数の論理学研究の拠点に育て上げていく。
ゲーデル「カントールの連続体問題とは何か」
連続体仮説は ZF から独立である可能性が高いと予想し、新しい公理による解決を論じた。数学的対象の実在を重んじるゲーデルのプラトン主義的な立場がよく表れている。
タルスキ『初等代数と初等幾何の決定法』
実閉体の一階の理論（実数の加法・乗法・大小関係の理論）が量化子消去によって決定可能であることを示した。1930年頃に得ていた結果で、RAND の報告書として刊行された。自然数では決定不能になる問題が、実数では機械的に判定できる。
ヘンキンによる完全性定理の新証明
理論を極大無矛盾に拡張し、項そのものからモデルを作るという証明を与えた。現在の教科書の標準的な証明法で、ヘンキンは後にバークレーでタルスキの同僚となる。
ゲーデルの回転宇宙
アインシュタインの70歳記念論文集に向け、一般相対性理論の方程式の解として、過去へ戻る時間的閉曲線を持つ宇宙モデルを示した。
1950年代
タルスキ、モストフスキ、ラファエル・ロビンソン『決定不能な理論』
本質的決定不能性の概念を導入し、ごく弱い算術（ロビンソン算術 Q）でさえ決定不能であることを示した。決定不能性を他の多くの理論に移す方法を体系化した。
タルスキ「モデルの理論への寄与」（〜1955年）
形式言語の文と、それを満たす構造（モデル）の関係を研究する分野を「モデル理論」と名付け、数学の一分野として確立した。
タルスキの不動点定理
完備束上の単調関数は不動点を持ち、不動点全体もまた完備束をなすことを示した。後にプログラム意味論や抽象解釈の基礎として広く使われる。
ゲーデルがフォン・ノイマンに送った手紙
証明の長さに関する判定問題が、入力の長さの1次や2次程度の手間で解けるかを問うた。今日の P 対 NP 問題を先取りした内容として、1980年代末に再発見される。
ゲーデルのディアレクティカ解釈
雑誌『ディアレクティカ』で、直観主義算術を有限型の計算可能な汎関数の体系に翻訳する方法を示した。証明から計算内容を取り出す研究（証明論的解析）の源流の一つとなる。
1960年代
アブラハム・ロビンソンの超準解析
モデル理論を用いて無限小を厳密に扱う方法を与え、ライプニッツ流の微積分を正当化した。タルスキ以降のモデル理論が数学の他分野に応用された代表例となる。
コーエン、強制法で連続体仮説の独立性を証明
強制法を考案し、ZF が無矛盾ならば、ZFC に連続体仮説の否定を加えた体系も、ZF に選択公理の否定を加えた体系も無矛盾であることを示した。ゲーデルの1938年の結果と合わせ、連続体仮説は ZFC から、選択公理は ZF から独立であることが確定する。
モーリーの範疇性定理
可算言語の理論が、ある非可算濃度で範疇的（モデルが同型を除いて一つ）ならば、すべての非可算濃度で範疇的であることを示した。後のシェラによる分類理論へとつながる。
1970年代
ヒルベルトの第10問題の否定的解決
マチャセビッチが、デイヴィス、パトナム、ジュリア・ロビンソンの研究を完成させ、ディオファントス方程式の可解性を判定する一般的な手続きは存在しないことを示した（MRDP 定理）。ジュリア・ロビンソンはバークレーでタルスキの指導を受けた研究者である。
ヘンキン、モンク、タルスキ『シリンドリック代数』第1部
一階述語論理を代数的に捉える枠組みであるシリンドリック代数を体系的にまとめた。論理を代数として扱う研究の到達点の一つ。
パリス＝ハリントンの定理
ラムゼー理論の自然な組合せ論の命題が、ペアノ算術では証明できないことを示した。不完全性定理が人工的な命題に限らないことを示した重要な例となる。
ゲーデル死去
プリンストンで亡くなる。享年71。
1980年代
タルスキ死去
バークレーで亡くなる。享年82。