平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)『数学』を数学的に考える
照井 一成
京都大学数理解析研究所
teruikurims.kyoto-u.a .jp

1

はじめに

数学にはいったい何ができて何ができないのだろうか。その可能性と限界を知りたい。
そのために数学者の行う活動（定理を証明したり、反例を考案したり）を数学的に分析するのがメタ数学、ないしは数学基礎論と呼ばれる分野である。本講義では、当分野における古典的な成果であるゲーデルの不完全性定理とその周辺について概説する。それが示唆するのは数学の本質的な限界であると同時に開かれた可能性であり、確固たる土台の非存在であると同時に諸理論が織りなす空間の豊饒さである。本講義で解説できるのはほんの
序段の部分、すなわち算術（自然数論）についてのみであるが、不完全性という現象の核
心はすでに初等的な算術において現われているので、雰囲気をつかむのには十分であろう。
方針としては算術階層に重点をおき、算術の不完全性、真理述語の定義不能性、述語論
理の決定不能性などの結果をその中に位置づけていくことにする。
以下の論述においては、直感的なわかりやすさを重視し、数学的な厳密さをある程度犠
牲にしている部分がある。証明は全て概略的である。ここで与えられる定義や証明のいく
odel らのオリジナルのものとは異なっているが、特に新しいも
つかは、Tarski, Chur h, G
のではない。本稿を執筆するにあたっては、 [6, 11, 12℄ などを参考にした。

2

自然数としての論理式

本章では、まず算術の論理式とその真偽の定義をする。以下、自然数 0; 1; 2; : : : 全体の集合を により表す。

N

定義 1 (算術の項) 算術の項を次のように帰納的に定義する。

1. 変数 x; y; z; : : : および 0 は算術の項である。
2. t; u が算術の項ならば、 S (t); t + u; t  u も算術の項である。
特に 0; S (0); SS (0); SSS (0); : : : という形の算術の項を数項とよび、このリストにおける n
番目の数項を n により表す。変数を含まない項を閉項と呼ぶ。
定義 2 (算術の論理式) 算術の論理式を次のように帰納的に定義する。

1. t; u が算術の項ならば、 t = u は算術の論理式である。

1

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

2. A; B が算術の論理式ならば、:A; A ^ B; 8xA も算術の論理式である。ここで x は任意の変数。
以下、算術の論理式のことを単に論理式と呼ぶ。特に自由変数を一つも含まない論理式のことを閉論理式または文（senten e）と呼ぶ。自由変数を高々一つだけ含む論理式 A(x)を一変数論理式と呼ぶ。

!

_

9

: ^ 8

含意 、選言 , 存在 等は 、 、 を用いて用いて定義することができる。さらに以下の省略表現を用いることにする：

tu
8x  t:A
9x  t:A

 9x(t + x = u)
 8x(x  t ! A)
 9x(x  t ^ A)

ただし x は t; u に含まれない変数であるとする。算術の論理式は（というよりもどんな記
号表現も）、ゲーデル符号化により、自然数を用いて表すことができる（たとえば、論理式 A をコンピュータのエディタ上でタイプせよ。たとえディスプレイ上でどんなに複雑に見えようとも、コンピュータにとってはそれは 0 と 1 の列、すなわち二進数にすぎない）。
を一つ固定し、論理式 A に対応する自然数 A
今後、そのような符号化の方法
を A のゲーデル数と呼ぶことにする。論理式とは形式的な対象であり、それが実際に何であるのかが重要なのではない。大事なのはその使用法であり、解釈である。使用法や解釈が明確に定まっている限り、それはどのような対象であってもかまわない。特にそれが自然数であったとしても、一向に構わない。ゆえに我々は以下の重要な規約を採用すること
にする。

d e

d e2N

 算術の論理式をそれに対応するゲーデル数と同一視する1 。
例えば、算術の論理式 8x:0 = x を、そのゲーデル数 d8x:0 = xe と同一視する。今後、論理
式とは、ある種の性質を満たす自然数のことであるとする。ある数が偶数であったり素数であったりするのと正確に同じ意味で、ある数は閉論理式であったり一変数論理式であったりする。この同一視により、算術の理論（\自然数に関する" 理論）において、論理式を直接に取り扱うことが可能となる。
次に、算術の論理式が「（標準モデルにおいて）真である」とはどういうことかを正確に定めておくことにする。
定義 3 (算術の項の値) 任意の閉項 t について、t の値とは以下のように定義される自然数のことである。

1. 項 0 の値は自然数 0 である。
2. 項 t の値が自然数 n のとき、項 S (t) の値は自然数 n + 1 である。
3. 項 t; u の値がそれぞれ自然数 n; m のとき、項 t + u の値は自然数 n + m である。
1

このような規約は、例えば [4, 3, 6℄ 等に見られる。

2

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

4. 項 t; u の値がそれぞれ自然数 n; m のとき、項 t  u の値は自然数 n  m である。
特に数項 n の値は n である。
定義 4 (算術の論理式の真偽) 任意の閉論理式 A について、A が（標準モデルにおいて）真であるのは、以下の場合である。

1. 原子論理式 t = u が真であるのは、 t の値と u の値が等しいときである。
2. t  u が真であるのは、 t の値が u 以下の場合である。
3. :A が真であるのは、 A が真でないときである。
4. A ^ B が真であるのは、 A と B が両方とも真であるときである。
5. 8x  t:A が真であるのは、t の値よりも小さい全ての数 n について、A[n=x℄ が真となる場合である。

6. 9x  t:A が真であるのは、t の値よりも小さいある数 n が存在して、A[n=x℄ が真となる場合である。

7. 8xA が真であるのは、全ての数 n について、A[n=x℄ が真となる場合である。
8. 9xA が真であるのは、ある数 n が存在して、A[n=x℄ が真となる場合である。

N j= A と書く。また、集合 TA を

閉論理式 A が（標準モデルにおいて）真であるとき、TA =fA j A は真な閉論理式 gにより定義する。前述の規約により、 TA は自然数の集合となる。

3

算術階層

自然数の集合は非可算無限に存在する。それらのうちの大部分は、いかなる定義をも受け付けない混沌たるものであるが、中には算術の論理式により定義できるような集合も存在する。例えば、偶数の集合は y (2 y = n) を満たす自然数 n の集合と同一視することができる。そのような集合は算術の論理式により記述可能である、と言われる。ここでは、算術の論理式により記述可能な集合全体の集まりは、算術階層 (arithmeti al hierar hy) と呼ばれる階層性を成すことを示す。
算術階層は、集合の複雑さを表す尺度とみなすことができる。この尺度は、論理式の複雑さによって定義される純論理的性格のものであるが、興味深いことに、計算論的な複雑さの概念に正確に対応することが知られている。本章の最後では、そのような論理と計算論の関係の一端を示す定理を紹介する。

9

定義 5 (限定論理式) 限定論理式を次のように帰納的に定義する。

1. t; u が算術の項ならば、 t = u は限定論理式である。

3

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

2. A; B が限定論理式ならば、:A; A ^ B; 8x  t:A; 9x  t:A も限定論理式である。ここで x は任意の変数、 t は算術の項である。

89

8  t; 9x  t の形になっ

すなわち、量化子 ; が用いられる際には、常に限定量化子 xているような論理式が限定論理式である。

定義 6 (i 論理式, i 論理式) 0 論理式とは限定論理式のことに他ならない。同様に、
0 論理式とは限定論理式のことに他ならない。各 i = 1; 2; : : : について i 論理式、i 論
理式を次のように帰納的に定義する。

1. A が i 1 論理式ならば、9x1    9xn A は i 論理式である。
2. A が i 1 論理式ならば、8x1    8xn A は i 論理式である。
ここで n2 N は任意であり、特に n = 0 の場合も含める。

定義 7 (集合の記述) A(x) を一変数論理式とするとき、集合 XA

Nを

XA = fn j A(n) は真である gと定義する。集合 X
述できるという。

 N に対して X = XA となるとき、X は一変数論理式 A により記

定義 8 (算術階層) 何らかの i 論理式により記述できるような集合のことを i 集合と呼ぶ。同様に、i 論理式により記述できる集合を i 集合と呼ぶ。 i 集合であり、かつ i
集合でもあるような集合を i 集合と呼ぶ。

i 集合全ての集まりのことを単に i と書く。i、i についても同様である。
例えば、偶数の集合は 1 論理式 9y (x = 2  y ) により記述できるので 1 集合である。
実際には、Even(x)  9y  x(x = 2  y ) という限定論理式（＝ 0 論理式、0 論理式）によっても記述できるので、 0 集合であるとも言える。また、素数の集合もDiv(y; x)Prime(x) 9z  x(y  z = x)
 2  x ^ (8y  x:Div(y; x) ! (y = 1 _ y = x))というように限定論理式により記述できるので、 0 集合である。

2N

!

補題 9
1. 各 iについて、i , i , i は以下の包含関係にある。（ここでは包含関係 を表す。例えば、i
i は、集合 X が i 集合ならば、それは i 集合
でもあるということを表す。）



!

i+1

 I

i
i
I


i

4

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

2. 集合 X  N が何らかの算術の論理式 A(x) により記述できるならば、X は算術階層

2 n である。
3. X 2 i () X C 2 i （ここで X C は N に関する X の補集合を表す。）に属する。即ち、ある n について X

証明

1. 定義より、i  i , i  i 。また、i  i+1 （i  i+1 ）である。さらに
i  i+1 （i  i+1 ）であることは、i に関する帰納法により証明することができる。ゆえにi  i+1 \ i+1 = i+1 (i  i+1 \ i+1 = i+1 ):2. Prenex 標準形定理（のヴァリエーション）により、A(x) は Q1 x1 Q2 x2    Qn xn A0という形の論理式と同値である（ここで各 Qi は 8 または 9、A0 は 0 論理式）。
Q1 ; : : : ; Qn における 8 と 9 の交替の回数が k 回であるとすると、それは k+1 論理式である。ゆえに A(x) が表す集合は k+1 集合である。
3. ドモルガンの法則より。例えば X が 2 論理式 9y8z:A により記述できるならば、
X C は :9y8z:A により記述できるが、後者は 2 論理式 8y9z::A と論理的に同値である。

N ! N に対して次のような 1 論理式 Ff (x; y) が存在する

定義 10 (1 関数) 関数 f :とき、f は 1 関数であるという： 任意の n 2 N について、f (n) = m () Ff (n; m) は真である。
上の性質を満たす 1 論理式 Ff が与えられれば、同じ性質を満たす 1 論理式を構成することが常に可能である。 f が 1 ではなく 1 関数と呼ばれるのはそのためである。
補題 11 X を i 集合、f を 1 関数とすると、X の f による逆像 f 1 (X ) は i 集合である。同様に、X を i 集合（i 1）、f を 1 関数とすると、f 1 (X ) は i 集合である。



証明 集合 X が i 論理式 A(x) により記述され、関数 f が 1 論理式 F (x; y ) により記述されるとき、集合 f 1 (X ) は論理式 y (F (x; y ) A(y )) により記述される。実際、任意のnについて以下が成り立つ：

92N

n 2 f 1(X )^() ある m について f (n) = m かつ m 2 X() ある m について F (n; m) は真、かつ A(m) は真() 9y(F (n; y) ^ A(y)) は真。

この論理式が i 論理式と同値であることは容易に確かめることができる。
次にいくつかの計算論的な概念を導入する。
定義 12 (決定可能集合、計算可能関数、半決定可能可能集合)5

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

 X  N が決定可能 (de idable) である () 自然数 n 2 N が与えられたとき、n 2 X

かどうかを有限時間で判定するアルゴリズムが存在する（すなわち、入力 n に対して、n X のときには \yes" を、n X のときには \no" を有限時間内に出力する
コンピュータプログラムが存在する）。

262

 関数 f : N ! N が計算可能 ( omputable) である () 自然数 n 2 N が与えられた
とき、f (n) = m となる m を有限時間で出力するアルゴリズムが存在する。

 X  N が半決定可能 (semi-de idable) である () 自然数 n 2 N が与えられたとき、
n 2 X () 有限時間内に \yes" を出力するを満たすアルゴリズムが存在する。（n 62 X のときには有限時間内に \no" を出力するとは限らない。）
決定可能集合、計算可能関数、半決定可能集合は、それぞれ再帰的関数論における再帰的集合 (re ursive sets)、再帰的関数 (re ursive fun tions)、再帰的枚挙可能集合 (re ursively
enumerable sets) と同一視される（Chur h のテーゼ）。これらの計算論的概念と算術階層の間には以下の対応がある。
定理 13

1. X が決定可能である () X が 1 集合である。

2. f が計算可能である () f が 1 関数である。
3. X が半決定可能である () X が 1 集合である。

(

証明 ここでは 3 の = のみを示す。（残りについては、 [10, 8℄ 等の標準的な教科書を参照してほしい。）まず、閉限定論理式の真偽は有限時間で判定可能であることに注意する。
たとえば、n1 + n2 = n3 の真偽を判定するには、n1 + n2 を計算して、その結果を n3 と比べればよい。また、 x t:A(x) の真偽を調べるためには、まず t の値を計算する。仮にそれが n だとすると、 x t:A(x) の真偽は

8 
8 

A(0) ^ A(1) ^    ^ A(n)の真偽と一致するから、 A(0); : : : ; A(n) の真偽をそれぞれ帰納的に確かめてゆけばよい。
さて、X を 1 集合とすると、nが与えられたとき、n X が成り立つかどうかの判定は、何らかの閉 1 論理式 x:A(x)（ここで A(x) は限定論理式）の真偽の判定に帰着する。後者を判定するための半決定的アルゴリズムは次のようにして与えることができる：まず A(0) の真偽を判定し、もし真ならば \yes" を出力する。さもなければ A(1) の真偽を判定し、もし真ならば \yes" を出力する。さもなければ A(2) の真偽を判定する。このようにして、

92N

2A(0); A(1); A(2); : : :と真偽判定のプロセスを続けていく。各 A(n) は閉限定論理式だから、その真偽は有限時間で判定可能である。また、 x:A(x) は、ある kについて A(k ) が真のとき、またそのときに限り真である。ゆえに、上記のアルゴリズムは x:A(x) が真のとき、またそのときに限り \yes" を有限時間内に出力する。

9

2N

6

9

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

4

算術階層の厳密性

本章では、前章で導入された算術階層が厳密であることを示す。即ち、クラス間の包含関係 が、実際には であることを示す。証明はカントールの対角線論法による。
1 集合とは 1 論理式により定義される集合のことであった。一変数 1 論理式は、（ゲー
デル数が小さいほうから順番に数えることで） 0 番目の一変数 1 論理式、1 番目の一変
数 1 論理式というように全て枚挙することができる。ゆえに（重複を無視すれば）1 集
合も



(

X0 ; X1 ; X2 ; : : :f j 2 Xng によというように枚挙することができるはずである。いま、集合 K を K = n nり定義する。すると次の性質が成り立つ。
補題 14 (1 対角化)

(1) K 2 1(2) K 62 1
証明(1) 任意の n 2 N が与えられたとき、 n 2 K が真かどうかを調べるためには n 2 Xn が真かどうかを調べればよい。Xn は 1 集合だから、このことを調べるための半決定的アルゴリズムが存在する。ゆえに K 自身も半決定可能であり、よって K は 1 集合である。

(2) 仮に K が 1 集合であるとすると、補題 9 により K C は 1 集合となる。ゆえにある k について Xk = K C となるはずであるが、k 62 K C () k 2 K () k 2 Xk () k 2 K Cとなり矛盾する。

ここで用いられた論法が対角線論法と呼ばれることの理由は、以下のように説明することができる。
自然数の集合 Xが与えられたとき、

N

xi = 1 i 2 X のとき= 0 i 62 X のときとおく。すると X に対して、0 と 1 から成る無限列

x0 ; x1 ; x2 ; : : :を対応させることができる。例えば、偶数の集合 Even =1; 0; 1; 0; 1; 0; : : :7f0; 2; 4; : : :g には平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)が対応し、素数の集合 P rime =f2; 3; 5; 7; 11 : : : g には0; 0; 1; 1; 0; 1; 0; 1; 0; 0; 0; 1; : : :が対応する。逆にこのような無限列が与えられたら、そこから自然数の集合 X を一意に復元することができる。
さて、本章の最初で定義した 1 集合の列 X0 ; X1 ; X2 ; : : : の各要素 Xi に対して上のよ
うに 0,1 の無限列を対応させると、次のような表を得ることができる。


X0


X1
X2

X3

     
0
0
0
0
1

1
0
1
0
0

2
1
1
1
1

3
1
0
0
0

この表の対角線 0; 1; 1; 0; : : : をとると、それ自体 0,1 の無限列になっている。集合 K はこの無限列に相当する。そしてその補集合 K C は、対角線の 0,1 を逆にして得られる無限列
1; 0; 0; 1; : : : に相当する。補題 14 が示しているのは、K はこの表の中に何らかの Xk として現れるが、K C はこの表の中には現れないということである。（なぜならばいかなる Xk
についても、K C と Xk は、その k 番目の要素について異なっているからである。）
補題 14 およびその一般形から、次の定理 [7℄ が帰結する。
定理 15 (算術階層の厳密性)

1. 1 6 1 、1 6 1
2. 1 ( 1 、1 ( 1
3. 1 ( 2 、1 ( 2
4. 一般に算術階層は厳密である。すなわち、各 i について包含関係

i+1

 I

i
i
I


i

は厳密である。

2

証明 (1) については、補題 14 より、K 1 かつ K
かつ K C 1 であることから。
(2),(3) は (1) から容易に示すことができる。
(4) は以上の事柄の一般化である。

62

8

62 1 であること、また逆に K C 2 1

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

5

真理述語の定義不能性

本章では、算術階層の厳密性の第一の帰結として、真理述語の定義不能性（Tarski）を証明する。
第２章で導入した規約により、論理式とはある性質を満たす自然数のことである。ゆえに、一変数論理式 A(x) が与えられたとき、任意の nに対して論理式 A(n) を割り当てる操作は から への関数 fA と考えることができる。適切なゲーデル符号化のもとでは、この関数は計算可能である（1 関数である）と仮定しても差し支えない。また fA 1 (TA)は、A(x) により記述される集合 XA と一致する。実際、

N

2N

N

n 2 XA () A(n) は真() A(n) 2 TA () n 2 fA 1(TA)が成り立つ。
定理 16 (真理述語の定義不能性) 算術の論理式に関して「真である」という性質は、算術の論理式によっては定義することができない。すなわち、真な閉論理式の集合 TA は算術の論理式によっては記述することができない。
証明 仮に TA が算術の論理式によって記述可能であるとすると、補題 9 により、TA はある k について k 集合となるはずである。ゆえに補題 11 により任意の一変数論理式 A(x)について XA = fA 1 (TA) も k 集合となるはずである。よって算術階層に属する全ての集合が k 集合となり、算術階層は崩壊してしまう。しかしこのことは算術階層の厳密性に反する。
よって、算術の論理式一般に関する真理概念は算術の言語によっては定義することができない。一方、各 n については、このことは可能であることが知られている（ f. [6℄）。



0 について、真な閉 n 論理式全体
定理 17 (各層ごとの真理述語の定義可能性) 各 nの集合 TAnは n 論理式により記述可能である。

N

6

形式的理論について

以下では、形式的数学理論について一連の性質を証明していくが、本章ではその準備として、一階述語論理の証明系ならびにそれに付随する基本概念を定義し、形式的理論の例
として算術の理論 Q と PA を導入する。
論理的推論を形式的に記述するに当たっては、論理式そのものよりも、論理式の拡張表
現であるシークエントを基本単位とするほうが都合がよい。 を論理式の有限集合, A を論理式とするとき、A の形の表現をシークエントという。直感的には、A は「前提 を仮定すれば結論 A が成り立つ」ことを表す。以下、集合A のことを単に ; Aと書くことにする。また、便宜上「矛盾」を表す論理式 を考えることにする（ は例えばAA, 0 = 1 などの論理式により定義できる）。
シークエントA が与えられたとき、次の性質を満たすシークエントの有限列 1
A の証明という。
A1 ; : : : ; n An のことを

`

?

^:

`

`

[f g

`

?

`

`

9

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

 ` A  n ` An
 各 1  i  n について、Ai 2 i であるか、あるいは i ` Ai はそれに先行するシー
クエント j1 ` Aj1 ; : : : ; jk ` Ajk から導出可能である（j1 ; : : : ; jk < i）。
ここで導出関係は以下の推論規則により定義されるものとする。

`A `B
`A^B
`A^B
`A^B
`A
`B
` A _ B ;A ` C ;B ` C
`B
`A
`A_B
`A_B
`C
;A ` B`A!B `A
`?
`A!B
`B
`A
;A ` ?
; :A ` ?
` :A ` A` :A`?
`A` 8xA(x)` A(x) ()` 8xA(x)` A(t)` A(t)` 9xA(x) ; A(x) ` C ()` 9xA(x)`C
ただし、() のついた規則においては、 の中で x は自由変数として現れないものとする。
上の諸規則の読み方についてであるが、たとえば最初の規則は、「 ` A ^ B の形のシー
クエントは二つのシークエント ` A および ` B から導出可能である」と読む。
定義 18 (証明可能性) 論理式の集合のことを理論 (theory) または公理系と呼ぶ。論理式
A が理論 T において証明可能であるとは、T のある有限部分集合
T について、Aの証明が存在することをいう。A が理論 T において証明可能であることを、 T A により表す。T において証明可能な論理式全体からなる集合を ProvT により表す。これは の部分集合となる。

N`` ? ?2`

N

定義 19 (無矛盾、再帰、拡大) 理論 Tにおいて T （Prov T ）が成り立たな
いとき、T は無矛盾 ( onsistent) であるという。T が決定可能集合（1 集合）のとき、Tは再帰的 (re ursive) であるという。二つの理論 S; T について Prov T
Prov S が成り立
つとき、S は T の拡大 (extension) である、または T は S の縮小であるという。



例として、算術の理論 Q と PA を導入する。
定義 20 (Q, PA) 理論 Q は、以下の論理式（の全称閉包）から成る。

1. x = x
2. x = y ^ x = z ! y = z
3. x1 = y1 ^ x2 = y2 ! x1 + x2 = y1 + y2

10

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

4. x1 = y1 ^ x2 = y2 ! x1  x2 = y1  y2
5. x = y ! S (x) = S (y )6. S (x) = S (y ) ! x = y
7. S (x) 6= 0
8. x 6= 0 ! 9y (x = S (y ))9. x + 0 = x
10. x + S (y ) = S (x + y )11. x  0 = 0
12. x  S (y ) = (x  y ) + x
理論 PA とは、Q に次の形の論理式（数学的帰納法の公理）を全て加えたものである。

A(0) ^ 8x(A(x) ! A(S (x))) ! 8yA(y)Q も PA も明らかに再帰的である。PA が無限集合であるのに対して、Q は有限集合であることに注意。
Q の拡大と PA の縮小に関しては、以下の（部分的な）完全性定理および健全性定理が成り立つ。
定理 21 (Q の 1 完全性) 任意の閉 1 論理式 A について

A が真 =)`Q A:
証明 A の構造に関する帰納法による。
よって T が Q の拡大ならば、T も 1 完全である。特に PA も 1 完全である。
定理 22 (PA の健全性) 任意の閉論理式 A について

`PA A =) A が真:`証明 証明図の大きさに関する帰納法による。シークエント B1 ; : : : ; Bn A が（標準モデルにおいて）真であることを B1
Bn A が真であることと定義した上で、次の二つを示せばよい。

^^!

1. 真なシークエントから推論規則により導かれるシークエントは真である。
2. 公理は（標準モデルにおいて）真である。

よって T が PA の縮小ならば、 T も健全である。特に Q も健全である。健全性よりも弱い性質として、次の 1 健全性を考えることができる。

11

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

定義 23 (1 健全性) 理論 T が 1 健全であるとは、任意の閉 1 論理式 A について

`T A =) A が真が成り立つことである。

1 健全性は無矛盾性を含意する。もしも T が 1 健全であり、かつ `T ? であるとすると、? は 1 論理式なので真となるはずであるが、 ? は定義により偽だからである2 。

1 弱表現可能性と理論の決定不能性

7

一変数論理式 A(x) が与えられたとき、真であるという概念を通して、集合 XA = fA 1 (TA)= nA(n ) は真である を定めることができる。他方で、証明可能であるという概念を通して、別の集合 f 1 (Prov T ) = n
A(n ) は T において証明可能である を定めることもできる。両者は一体どのような関係にあるのだろうか？前章においては、Q の拡
大の 1 完全性を示したが、ここではその直接の帰結として、もしも理論 T が十分に強力（Q T ）かつ自然（1 健全）ならば、少なくとも閉 1 論理式に関しては上の二つは一致することを示す。別の言い方をすれば、証明可能性述語 T は閉 1 論理式に関しては
真理述語と見なすことができるということである。
結果として、T における証明可能性は決定不能となり、さらにそこから、一階述語論理
は（等号を含んでも含まなくても）決定不能であるということが帰結する。後に第 10 章
で、ここでの 1 健全性の仮定を無矛盾性に弱めても類似の性質が成り立つことを見る。

f 2 Njg

f 2 Njg`

定理 24 (1 弱表現可能性) 理論 T が Q の拡大であり、かつ 1 健全であるとすると、任意の一変数 1 論理式 A(x) について

n 2 XA () A(n) は真 ()`T A(n)証明 T の 1 健全性および 1 完全性より。

`

定理 25 (決定不能性) 理論 T が Q の拡大であり、かつ 1 健全であるとすると、 T は決定可能ではない。すなわち、T において証明可能な論理式全体からなる集合 ProvT は 1
集合ではない。
証明 定理 24 により、任意の一変数 1 論理式 A(x) について

n 2 XA ()`T A(n) () A(n) 2 ProvT () n 2 fA 1(ProvT )が成り立つ。仮に Prov T が 1 集合であるとすると、補題 11 により fA 1 (Prov T ) = XA
も 1 集合となる。よって全ての 1 集合は 1 集合であることになってしまうが、このこ
2

1 健全性は [5℄ における ! 無矛盾性の仮定を弱めたものである。（理論 T が ! 無矛盾であるのは、`T 9x:A(x) かつ全ての n 2 N について `T :A(n) となるような論理式 A(x) は存在しないときである。）まとめると、以下の含意関係が成り立つ：) ! 無矛盾性 =)  健全性 =) 無矛盾性

健全性 =

1

12

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)とは算術階層の厳密性に反する。

``

特に Q も PA も健全であるから、 Q も PA も決定不能である。さらに Q が有限集合であることから、次のことが帰結する（Chur h [1℄）。
系 26 (一階述語論理の決定不能性) 一階述語論理における証明可能性ない。
証明 Q の公理を全て連言により結んで得られる論理式を`Q A () `^` は決定可能では

V Q と書く。すると、

Q!Aが成り立つ。ゆえに、もしも一階述語論理が決定可能ならば、Q における証明可能性も決定可能となってしまうが、これは上の定理に反する。

8

証明可能性の算術階層における位置づけと算術の第一不完全性`前章では、適切な仮定の下では証明可能性述語 T は 1 ではないということを証明した。本章では、その一方で再帰的理論における証明可能性述語は 1 であるという事実を
odel[5℄ によるこの洞察は、形式的理論一般の性質として決定的に重要である。特示す3 。Gに、第一不完全性定理 [5℄ はこのことと算術の 1 完全性から直接に帰結する。
メタ数学的概念である証明可能性述語が算術階層の、しかも 1 というごく低い層に位置づけられるという事実は、真理述語は算術階層のうちに位置づけることはできない（定理 16）という事実と対照的である。
定理 27 (証明可能性

2 1) 理論 T が再帰的ならば、ProvT は 1 集合である。

証明 任意の論理式 A、任意の証明図  について、「 は T における A の証明図である」という関係は有限時間で判定可能であり、ゆえに（ を自然数と見なすならば）、ある 1
論理式 Proof T (A;  ) により記述することができる。このとき、「A は T において証明可能である」という性質は、 y:Proof T (A; y ) により記述することができる。

9

定理 28 (1 不完全性) 理論 T が Q の無矛盾な再帰的拡大ならば、真でありかつ T で証明不可能な閉 1 論理式が存在する。
証明 T が無矛盾ならば、 T は 1 健全である。なぜならば、ある閉 1 論理式 A が証明可能でありなおかつ偽であるとすると、 A は真な閉 1 論理式（と論理的に同値）であり、ゆえに 1 完全性により証明可能なはずである。よって T は矛盾することになるからである。

:

Craig [2℄ は全ての再帰的枚挙可能理論（1 理論）についてそれと同等な再帰的理論が存在するという定理を証明した。この結果により、以下の諸定理は「再帰的」を「再帰的枚挙可能」と読み替えても、全て成立
する。
3

13

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

いま、さらに T が 1 完全であるとすると、任意の 1 論理式 A(x)、任意の n
いてn XAA(n) は真fA 1(ProvT )T A(n)

2

()

()`

()

となる。ここで fA 1 (ProvT ) は補題 11 により 1 集合であるから、1が、このことは算術階層の厳密性に反する。

2 N につ 1 が帰結する

次の定理が一般にゲーデルの第一不完全性定理と呼ばれるものである。この定理は 1
健全性（! 無矛盾性を弱めたもの）という仮定に基づいているが、後に第 10 章で、この仮定を単なる無矛盾性に弱めても同じ性質が成り立つことを示す。

:

系 29 (第一不完全性) 理論 T が Q の再帰的拡大であり、かつ 1 健全ならば、A も Aも証明不可能であるような閉 1 論理式 A が存在する。

:

証明 1 不完全性定理により、真でありかつ証明不可能な 1 論理式 A が存在する。 Aは偽な 1 論理式（と論理的に同値）であるから、1 健全性により A は T では証明不可
能である。

:

9

形式化された対角線論法

本稿のこれまでの流れを振り返ってみると、まず我々は対角線論法を用いて算術階層の厳密性を示し、そのことに基づいて、真理述語の定義不能性、一階述語論理の決定不能性、算術の第一不完全性などを証明してきた。特に算術階層の厳密性が確立されたあとでは、
対角線論法を用いる必要は一切なかった。
しかし 1 弱表現可能性定理（定理 24）や第一不完全性定理における 1 無矛盾性の仮定を単なる無矛盾性に弱めようとすると、どうしても形式的体系の内部で対角線論法を用いることが必要になってくる。その理由は、単なる無矛盾性の仮定だけでは、1 論理式の成立・不成立が標準モデルにおける真偽と必ずしも一致しなくなるため、標準モデルの内部にあるところの算術階層の厳密性を形式的体系に反映させることができなくなるからである。また、第二不完全性定理を証明するためには、1 不完全性定理の議論を形式的体系の内部で行う必要がある。そのためにも、対角線論法を形式的体系の内部で行うことが必要になってくる。ここでは形式的体系の内部における対角線論法の一般的な帰結として、対角化定理（任意の論理式に対してその不動点が存在する）を紹介する。
インフォーマルには、対角化定理（不動点定理）は以下のように示すことができる。
まず、ゲーデル数 n の一変数論理式を An (x) により表すことにする（n が一変数論理式に対応しないときは未定義とする）。次に、関数 g :を次のように定義する：

N !Ng(n) = fAn (n) = An (n)（のゲーデル数）
g は明らかに計算可能であるから 1 関数である。

14

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

さて、X を算術の論理式により記述可能な集合とすると、 g 1 (X ) もやはり算術の論理式により記述可能である（補題 9、補題 11 より）。g 1 (X ) を記述する論理式（のゲーデ
ル数）を k とする。すなわち、Ak (x) が g 1 (X ) を記述するものとする。すると、Ak (k ) は真 () k 2 g 1 (X ) () g(k) 2 X () Ak (k) 2 X:

ゆえに算術の論理式により定義可能などんな集合 X についても、ある閉論理式 A が存在し、A が真 () A 2 Xが成立する。これが対角化定理の内容である4 。
以上の論証を体系 Q において形式化すると、次のことが成立する。（2 は 1 の一般化である。）
定理 30 (対角化定理)

1. 任意の一変数論理式 B (x) に対して、ある閉論理式 A が存在し、`Q A ! B (A):
2. 任意の二変数論理式 B (x; y ) に対して、ある一変数論理式 A(y ) が存在し、`Q A(n) ! B (A(n); n)(n 2 N ):対角化定理を用いれば、第一不完全性定理に対してより直接的な証明を与えることができる。
理論 T が Q の再帰的拡大であり、かつ無矛盾であるとする。すると、定理 27 により集合 ProvT は 1 である。即ち、1 論理式 ProvT (x) により記述可能である。いま、論理式
ProvT (x) に対して対角化定理を適用すると、:`T G ! :ProvT (G)を満たす論理式 G を得ることができる。論理式 G は一般にゲーデル文と呼ばれる。その
直感的意味は「私は証明できない」といったものである。
定理 31 (第一不完全性)

1. 理論 T が Q の再帰的拡大であり、無矛盾ならば、 6`T G。
2. さらに T が 1 健全ならば、6`T :G。
証明

1. もしも `T G であるとすると、`T :ProvT (G) となり、T の無矛盾性により 6`T
ProvT (G) である。ゆえに 1 完全性定理により ProvT (G) は偽である。よって 6`T Gとなり、矛盾する。

2. もしも `T :G であるとすると、`T ProvT (G) となり、T の 1 健全性により Prov T (G)は真である。ゆえに
4`T G となる。これは T の無矛盾性に反する。

A は X の不動点（ xed point）と呼ばれる。

15

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

10

一般 1 表現可能性

第 7 章では、1 健全な Q の再帰的拡大においては、全ての 1 集合が弱表現可能であること（定理 24）を証明した。ここでは 1 健全性の仮定を無矛盾性の仮定で置き換えても同様のことが成立することを証明する（Ehrenfeu ht-Feferman [3℄）。また、その帰結として、Q の本質的決定不能性（定理 25 の一般化）、ゲーデル=ロッサーの不完全性定理（系
29 の一般化）を示す。
定理 32 (一般 1 表現可能性) 理論 T が Q の再帰的拡大であり、かつ無矛盾であるとす
ると、任意の 1 集合 X に対してある一変数論理式 B (x) が存在し、

n 2 X ()`T B (n)が成り立つ。
定理 24 の場合とは異なり、ここで論理式 B (x) は X を記述する論理式であるとは限らないことに注意。

9

証明 X は 1 論理式 y:A(x; y )（ここで A は 0 ）により記述され、ProvT は 1 論理
式 y:Proof T (x; y ) により記述されるものとする。このとき、二項論理式

98y(Proof T (x; y) ! 9z  y:A(w; z))を考えると、対角化定理により、ある一変数論理式 B が存在して、任意の n について`T B (n) ! 8y(Proof T (B (n); y) ! 9z  y:A(n; z))を満たす。これが求める論理式であることを示すには、次の２点を証明すればよい。

1. n 2 X =)`T B (n)。
2. `T B (n) =) n 2 X 。

次の系は定理 25 と同様にして証明できる。
定理 33 (Q の本質的決定不能性) 理論 T が Q の無矛盾な再帰的拡大であるとすると、 Tにおける証明可能性 T は決定可能ではない。

`

最後に第一不完全性定理の改良版であるゲーデル=ロッサーの定理を証明する（Rosser[9℄）。
定理 34 (ゲーデル＝ロッサー不完全性) 理論 T が Q の無矛盾な再帰的拡大であるとすると、A も A も証明不可能であるような閉 1 論理式 A が存在する。

:

16

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)`` :証明 仮に T が完全であるとする。すなわち、どんな論理式 A についても、 T A か T Aのどちらかが成り立つとする。いま、1 集合 X が与えられたとき、その補集合 X C は 1集合であり、ゆえに定理 32 によりある一変数論理式 B (x) が存在し、

n 2 X C ()`T B (n):
一方、T の無矛盾性および完全性の仮定により

6`T B (n) () `T :B (n):以上のことから、

n 2 X () n 62 X C ()6`T B (n) () `T :B (n)よって 1 1 が帰結するが、これは算術階層の厳密性に反する。

第一不完全性定理同様、ゲーデル=ロッサーの不完全性定理にも直接的な証明方法がある。Disproof T (x; y ) を「y は T における (x) の証明である」を意味する論理式とし、一
変数論理式

:

8y(Proof T (x; y) ! 9z  y:Disproof T (x; z))に対角化定理を適用して得られる論理式を R とする。すると 6`T R かつ 6` :R であることが直接的に証明できる（R は一般にロッサー文と呼ばれる）。定理 32 における論理式 B (x)の構成法はこのロッサー文の構成法を一般化したものになっている。

11

第二不完全性理論 T を Q の再帰的拡大とする。このとき、1 不完全性定理は次の性質をもつ論理式
A が存在することを主張する：

1. T が無矛盾ならば A が成り立つ。
2. T が無矛盾ならば 6`T A。
1 不完全性定理に至るまでの証明を注意深く検討すれば、この A は具体的に構成することが可能である（あるいは定理 31 における G をとればよい）。そして、そのような具体的な A に話を制限すれば、算術を超え出るような超越的な論法は一切用いずに 1 不完全性定理は証明可能である5 。ゆえに理論 T として十分強力な算術の体系（例えば PA）をとれば、1 不完全性の議論は全て T の内部で遂行することができる。特に上記の 1 を形式化することで、次のことが証明できる：

1' `T ConT ! A
5

PA の健全性（定理

これまでに用いた論法の全てが算術において形式化可能なわけではない。例えば、

22）を示すためには、任意の論理式に関する真理述語が必要であるが、そのような述語が算術的には定義不能であることは、定理 16 で見た通りである。

17平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催):?

ここで ConT は T の無矛盾性を表す論理式 ProvT ( ) である。上記 1',2 の論理的帰結として、もしも T ConT ならば T は矛盾することになる。言い換えれば、`

 T が無矛盾ならば、6`T ConT 。
すなわち、十分強力かつ無矛盾な理論は、自分自身の無矛盾性を証明することができない。
これがゲーデルの第二不完全性定理の主張の骨子である。以下、第二不完全性定理の証明のあらましを見ていくことにする。
次の定理は定理 27 の改良版である。
定理 35 理論 T が PA の再帰的な拡張ならば、集合 Prov T を記述し、かつ次の性質を満たす一変数 1 論理式 ProvT (x) が存在する：

1. 形式化された Modus Ponens： 任意の論理式 A について、`T ProvT (A) ^ ProvT (A ! B) ! ProvT (B ):2. 形式化された 1 完全性： 任意の閉 1 論理式 A について、`T A ! ProvT (A):実際、Prov T (x) を \自然に" 記述すれば、上記の性質 1 は、自ずと満たされる（ただし注意深い論証が必要である）。性質 2 は、PA が 1 完全性定理の証明を遂行するのに十分な証明能力を持っているという事実に基づいている6 。
以下、上の定理の性質を満たす Prov T (x) を一つ固定し、ConT
ProvT ( ) と定義する。

:

?

補題 36

1. `T A ならば `T ProvT (A)。
2. `T ProvT (A) ! ProvT (ProvT (A))。7
3. `T ProvT (A) ! B ならば `T ProvT (A) ! ProvT (B )。
証明

1. `T A ならば ProvT (A) が真。ゆえに 1 完全性定理により `T ProvT (A)。
2. 定理 35 の 2 で、A として 1 論理式 ProvT (A) をとればよい。
3. まず、形式化された Modus Ponens により、次の FMP が成り立つことに注意する：`T ProvT (A ! B )`T ProvT (A) ! ProvT (B ) F MP
これと上記の 1,2 を用いて、

PA

実際には、
ほど強力な証明能力は必要ではなく、高々1 論理式に関する帰納法が使用できれば十分である。
7定理 35 の 1 および補題 36 の 1,2 を合わせて可導性条件 (derivability onditions) と呼ぶ。第二不完全性定理はこれら３つの条件および対角化定理から帰結する。
618

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)`T ProvT (A) ! B
1`T ProvT (ProvT (A) ! B )2
F MP`T ProvT (A) ! ProvT (ProvT (A)) `T ProvT (ProvT (A)) ! ProvT (B)`T ProvT (A) ! ProvT (B )6`

定理 37 (第二不完全性) 理論 T が PA の再帰的拡大であり、かつ無矛盾ならば、 T ConT 。
証明 論理式:ProvT (x) に対角化定理を適用することにより、` G $ :ProvT (G)` : $ (G ! ?) に注意すれを満たす論理式 G（ゲーデル文）を得ることができる。 T Gば、以下のように T ConT
G を導出することができる：`!

`T ProvT (G) ! :G
`T ProvT (G) ! (G ! ?)`T ProvT (G) ! ProvT (G ! ?) 補題 36 の 3`T ProvT (G) ! ProvT (G) ^ ProvT (G ! ?)定理 35 の 1
`T ProvT (G) ! ProvT (?)`T ConT ! :ProvT (G)`T ConT ! G
一方、T は無矛盾なので、定理 31 により 6`T G。よって、6`T ConT 。
しかし一方で、PA の無矛盾性に関しては、いくつかの部分的な肯定的結果が知られている（ f. [6℄）。いま、理論 T が有限公理化可能（ nitely axiomatizable）であるとは、ある有限集合 T 0 が存在して、Prov T = Prov T 0 が成り立つこととする。
定理 38 (局所的な無矛盾性の証明可能性) 理論 T
ConT 。

 P A が有限公理化可能ならば、 `PA

特に、T としてどのように大きな公理の集合を取ったとしても、それが有限である限り、
PA はその無矛盾性を証明することができる。系として、次のことが帰結する。
系 39 (PA の本質的無限性) PA は有限公理化不可能である。



次に、任意の n 1 について、理論 I n とは、Q に n 論理式に関する数学的帰納法の公理を全て付け加えることにより得られる理論のことであるとする。当然、I n P A である。これらの PA の部分理論については、次のことが知られている。



定理 40 (各層ごとの有限公理化可能性) 任意の nである。
よって、次のことが成り立つ。

19

 1 について、 I n は有限公理化可能平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

系 41 (各層ごとの無矛盾性の証明可能性) 任意の n 1 について、`PA ConI n .

どのように大きな n をとったとしても、このことは成立する。特に、通常の数学において用いられる数学的帰納法を全て包含するほどに大きな n を取ったとしても、PA は、その無矛盾性を証明することができるのである。

12

おわりに

本稿においては、メタ数学における否定的成果（真理述語の定義不能性、算術や一階述語論理の決定不能性、第一不完全性など）に対して統一的説明を与えることを試みた。方
針としては、まず算術階層の概念を導入し、対角線論法を用いてその厳密性を示し、その上で上記の否定的成果をそこに帰着させる、という道筋をとった。この方針により、それぞれの否定的成果が成り立つことは以下のように説明される：

1. 算術の論理式に関する真理述語が算術の論理式で定義可能であるとすると、算術階層の全体がある n へと崩壊してしまう（定理 16、真理述語の定義不能性）。
2. Q より強力かつ自然な理論 T をとると、証明可能性述語 `T は、1 論理式に関する
真理述語を定義しているものと見なすことができる（定理 24、1 表現可能性）。ゆえにもしも `T が決定可能、すなわち 1 だとすると、1 が 1 へと崩壊してしまう（定理 25、算術の決定不能性）。
3. 証明可能性述語 `T は、1 論理式で定義可能である（定理 27）。もしも `T が 1 完
全であるとすると、`T は、1 論理式に関する真理述語を定義することになり、 1
が 1 へと崩壊してしまう（定理 28、1 不完全性）。
よって全ては算術階層の厳密性に起因するものと見なすことができる（第二不完全性を除く）。このように算術階層を機軸に据えることにより、メタ数学における様々な成果の関係について、よりよい見通しが得られる。

参考文献[1℄ A. Chur h. A note on the Ents heidungsproblem, Journal of Symboli Logi , Vol.
1, 1936, pp. 40{41.
[2℄ W. Craig. Bases for rst order theories and subtheories, Journal of Symboli Logi ,Vol. 25, 1960, pp. 97{142.
[3℄ A. Ehrenfeu ht and S. Feferman. Representability of re ursively enumerable sets informal theories, Ar h. Math. Log., Vol. 5, 1959, pp. 37{41.
[4℄ S. Feferman. Arithmetization of metamathemati s in a general setting, Fundamenta
Mathemati ae, Vol. 49, 1960, pp. 35{92.
20平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

[5℄ K. Godel. Uberformal unents heidbare Satze der Prin ipia mathemati a und verwandter Systeme I, Monatshefte fur Mathematik und Physik, Vol. 38, pp. 173{198.
[6℄ P. Hajek and P. Pudlak, Metamathemati s of First-Order Arithmeti , Perspe tives
in Mathemati al Logi , Springer, 1994.
[7℄ S. C. Kleene. Re ursive fun tions and predi ates, Trans. Amer. Math., Vol. 53,
1943, pp. 41{73.
[8℄ P. G. Odifreddi, Classi al Re ursion Theory, Elsevier, 1989.
[9℄ J. B. Rosser, Extensions of some theorems of Godel and Chur h's theorem, Journalof Symboli Logi , Vol. 4, 1939, pp. 53{60.
[10℄ J. R. Shoen eld, Mathemati al Logi , Addison-Wesley, 1967.
[11℄ R. M. Smullyan. Godel's In omplete Theorems. Oxford University Press, 1992. （邦訳：『ゲーデルの不完全性定理』、丸善株式会社、 1996.）[12℄ 田中一之（編・著）、『数学基礎論講義』、日本評論社、1997.

21