ペアノ算術と不完全性定理
2009SE082 石井大介
指導教員：佐々木克巳

1

はじめに理式の列である．この真であることが認められる論理式を公理と呼ぶ．PA では，以下の論理式も公理と約束している．
不等号に関する公理（不等号の再帰的な定義）∀x¬(x < 0)∀x∀y((x < S(y)) ↔ ((x < y) ∨ (x = y))
帰納法の公理∀⃗y ((φ(0, ⃗y ) ∧ ∀x(φ(x, ⃗y ) → φ(S(x), ⃗y )))→ ∀xφ(x, ⃗y ))田中 [1] を読むことで不完全性定理というものに興味をもった．そして，本研究では，[1] にしたがって不完全性定理の理解をふかめていく．
不完全性定理の理解は，[1] の第 I 部「第一不完全性定理と第二不完全性定理」の第１章〜第４章を用いた．そして，そこで紹介されている定理の証明において，省略されている部分を成田 [2] を参考にしながら補った．とくに，第２章「ペアノ算術」と第３章「第一不完全性定理」の証明を補った．その中で，定理 2.1（[1] では定理 2.3）
この節で扱う定理は以下である．と定理 3.6（[1] では定理 3.10）に力をいれた．具体的に，
定理 2.1（[1] の定理 3.3） つぎが成り立つ．
定理 2.1 では不等号に関する公理や後者関数の定義など(a) 任意の自然数 n に対して，との関係をうまく使いながら証明した．定理 3.6 では，１PA⊢ (∀x < n + 1)(x = 0 ∨ x = 1̄ ∨ · · · ∨ x = n̄)．
変数述語 AxiomT と２変数述語 ProvT の定義とゲーデ(b) 任意の自然数 n に対して，ル文を理解した上で証明を行った．
PA⊢ ∀x(x = 0 ∨ x = 1̄ ∨ · · · ∨ x = n̄ ∨ n̄ < x)．
本稿では，上に挙げた定理 2.1 と定理 3.6 を以下の２つ証明 (a) を示す．書き換えるとつぎのようになる．の節でそれぞれ扱う．次の２節では，定理 2.1 に関連し任意の自然数 n に対して，てペアノ算術の導入も行う．
PA ⊢ ∀x((x < n + 1) → (x = 0 ∨ x = 1̄ ∨ · · · ∨ x = n̄))
これを n に関する帰納法で示す．
2 ペアノ算術(i)n= 0 のとき
この節では，不完全性定理の議論のベースに用いられPA⊢ ∀x((x < 0 + 1) → (x = 0 ∨ · · · ∨ x = 0̄))
ることの多い，算術の理論の形式体系の１つである，ペつまりアノ算術 (Peano arithmetic ; PA) を，[1] にしたがってPA ⊢ ∀x((x < 1̄) → (x = 0))導入する．そして，その中の１つの定理（定理 2.1）に対を示せばよい．
し，[1] の証明の省略部分を補った結果を示す．
不等号に関する公理の２つ目よりこの理論 PA の対象は算術の理論の「証明」である．そPA ⊢ (x < S(0)) ↔ ((x < 0) ∨ (x = 0))の「証明」は論理の列として定められる．以下に論理式
不等号に関する公理の１つ目と 1̄ の定義である S(0) ≡ 1̄と「証明」を導入する．
を用いてPA ⊢ (x < 1̄) → (x = 0)
論理式の構成に使う要素は数学のどんな分野を考えて(ii)「PA⊢ ∀x((x < k + 1) → (x = 0 ∨ x = 1̄ ∨ · · · ∨ x =いるかで異なってくる．ここでは，自然数の算術を考えk̄))」が成り立つと仮定して「PA⊢ ∀x((x < S(k + 1)) →るので，つぎのものを用意する．
(x = 0 ∨ x = 1̄ ∨ · · · ∨ x = S(k̄)))」を示す．
・自然数を表す変数
帰納法の仮定より・不等号 : ＜・関数記号 : S,+,・PA ⊢ (x < k + 1) → (x = 0 ∨ · · · ∨ x = k̄) (1)・等号 : =
ここで，数項の定義より
・定数 : 0PA ⊢ (x = k + 1) → (x = S(k̄))(2)
・論理記号 : ¬ , ∧ , ∨ , → , ↔ , ∃ , ∀以上の記号を組み合わせてできる記号列で，自然数を表(1),(2) よりすものを項という．論理式は，これらのようないくつか
PA ⊢ (x < k + 1 ∨ x = k + 1) → (x = 0 ∨ · · · ∨ x =の要素を，適切に組み合わせてできる文字列のことであk̄ ∨ x = S(k̄))
る．
よって，不等号に関する公理の１つ目より定数が 0 しかないので，自然数 0,1,2,... を項で表現しPA ⊢ (x < S(k + 1)) → (x = 0 ∨ · · · ∨ x = S(k̄))
たいときには，0,S(0),S(S(0)),... を用いる．これらの項
つまりのことを数項と呼び，0̄,1̄,2̄,... と表記する．
PA ⊢ ∀x((x < S(k + 1)) → (x = 0 ∨ · · · ∨ x = S(k̄)))以上 (i),(ii) より (a) は示された．
「証明」とは，真であることが自明に認められる論理(b) を n に関する帰納法で示す．
式から始まって，適切なプロセスによって続いていく論(i)n = 0 のとき

定義 3.2 理論 T に対して，自然数上の２変数述語PA ⊢ ∀x(x = 0̄ ∨ · · · ∨ x = 0̄ ∨ 0̄ < x)
ProvT をつぎで定義する．
つまりProvT (n, m) ⇔ m は論理式（φ とする）のゲーデ
PA ⊢ ∀x(x = 0 ∨ 0 < x)を示せばよい．x = 0 ∨ 0 < x を P (x) とおいて，PA ⊢ ル数であって，n は「T における φ の証明」のゲーデル数である．
∀xP (x) を示す．
補題 3.3 述語 AxiomT が計算可能ならば ProvT も(i-i)PA⊢ P (0) を示す．等号の公理より計算可能になる．さらに，ProvT が計算可能ならばつぎPA ⊢ 0 = 0の条件を満たす Σ1 論理式 ProvT (y, x) の存在がいえる．
よって任意の自然数 n,m についてPA ⊢ (0 = 0) ∨ (0 < 0)
(1) ProvT (n, m) が成り立つときにはすなわちPA⊢ ProvT (n̄, m̄)PA ⊢ P (0)(2) ProvT (n, m) が成り立たないときには(i-ii)「PA⊢ P (y)」が成り立つと仮定して，「PA⊢ P (S(y))」PA⊢ ¬ProvT (n̄, m̄)を示す．仮定より
こ の ProvT (y, x) に よって つ く ら れ た Σ1 論 理 式
PA ⊢ (y = 0) ∨ (0 < y)∃yProvT (y, x) のことを T の証明可能性述語と呼び，こよって，不等号に関する公理の２つ目よりれを PrT (x) と表記する．
PA ⊢ 0 < S(y)定理 3.4（対角化定理） φ(x) が x 以外の自由変数をつまり含まない論理式ならばつぎの条件を満たす文 ψ が存在すPA ⊢ (S(y) = 0) ∨ (0 < S(y))
る．
すなわちPA ⊢ ψ → φ(⌈ψ⌉)
PA ⊢ P (S(y))
ただし，⌈ψ⌉ は ψ のゲーデル数である．
以上で (i-ii) が示された．
定義 3.5
PrT (x) が理論 T の証明可能性述語で，文(i-ii) よりGがPA ⊢ P (y) → P (S(y))
T ⊢ G → PrT (⌈G⌉)
つまりを満たすとき，G は T のゲーデル文であるという．
PA ⊢ ∀y(P (y) → P (S(y)))(3)
この節で扱う定理は以下である．
したがって，(i-i)，(3)，帰納法の公理より，PA⊢ ∀xP (x)定理 3.6 理論 T が PA の計算可能拡大ならば，T のは示せた．
ゲーデル文が存在する．
(ii)「PA⊢ ∀x(x = 0 ∨ · · · ∨ x = k̄ ∨ k̄ < x)」が成り立つと証明 理論 T が PA の計算可能拡大なので，定義 3.1
仮定して「PA⊢ ∀x(x = 0 ∨ · · · ∨ x = S(k̄) ∨ S(k̄) < x)」
よりつぎの２条件が成り立つ．
を示す．
(a) T の公理の中には PA のすべての公理が含まれる．
不等号に関する公理と帰納法の公理よりつぎを証明で(b) 述語 AxiomT (n) は計算可能である．
きる．
(b) と補題 3.3 より，T の証明可能性述語 PrT (x) が存在
PA ⊢ k̄ < x ↔ (S(k̄) = x ∨ S(k̄) < x)(4) する．ここで，¬P rT (x) は x 以外の自由変数を含まない論理式であるので定理 3.4 より
仮定と (4) よりPA ⊢ ψ ↔ ¬PrT (⌈ψ⌉)
PA ⊢ (x = 0) ∨ · · · ∨ (S(k̄) < x)を満たす文 ψ が存在する．いま文 ψ を G とおくと
つまりPA ⊢ G ↔ ¬PrT (⌈G⌉)
PA ⊢ ∀x(x = 0 ∨ · · · ∨ x = S(k̄) ∨ S(k̄) < x)(a) より，理論 T が PA の拡大となるので
以上 (i),(ii) より，(b) は示せた．
T ⊢ G ↔ ¬PrT (⌈G⌉)
つまり定義 3.5 より，G は T のゲーデル文である．

3第一不完全性定理

この節では，第一不完全性定理を証明するための１つ 4 おわりにの定理（定理 3.6）に対し，[1] の省略部分を補った結果
本研究では，ゲーデルの不完全性定理について理解すを示す．まず，そのためのいくつかの概念を導入し，そ ることができた．本研究を進めるにつれて，ゲーデルにの性質を述べる．
関連する歴史的背景に興味をもったので今後，不完全性定義 3.1 以下の２条件 (a),(b) が成り立つとき，理論 定理の歴史的経緯についてふれていきたい．
T は PA の計算可能拡大であるという．また，以下の条 参考文献
件 (a) が成り立つとき，理論 T は PA の拡大であるとい[1] 田中一之，ゲーデルと 20 世紀の論理学 不完全性定う．
理と算術の体系，東京大学出版会，東京，2007．
(a) T の公理の中には PA のすべての公理が含まれる．
[2] 成田一平，不完全性定理とその展開，南山大学数理情(b) 述語 AxiomT は計算可能である．
報学部情報システム数理学科 2009 年度卒業論文，2010.