ゲーデルの不完全性定理ゲーデル数化と第２不完全性定理，第

(1)

数理の世界

数学の考え方

ゲーデルの不完全性定理ゲーデル数化と第２不完全性定理，第

回の講義

渕野昌

神戸大学大学院システム情報学研究科

講義関連資料

神戸大学

年後期の講義

於

教室，月曜

!"

(2)

ゲーデル数化

^!" ^#$

とは，ゲーデルが不完全性定理の証明で導入した，記号列を数にコードしするテクニックのことを言う．

記号列に関する述語や言明を，ペアノの算術

^%&

を公理系とする形式的体系

^'

第

⁽

回の講義を参照

^$

での論理式や文に翻訳することが目標である．

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

(3)

ゲーデル数化

^{数理の世界}

ゲーデル数化

^!" ^#$

とは，ゲーデルが不完全性定理の証明で導入した，記号列を数にコードしするテクニックのことを言う．

記号列に関する述語や言明を，ペアノの算術

^%&

を公理系とする形式的体系

^'

第

⁽

回の講義を参照

^$

での論理式や文に翻訳することが目標である．

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

(4)

ゲーデル数化

^!" ^#$

とは，ゲーデルが不完全性定理の証明で導入した，記号列を数にコードしするテクニックのことを言う．

記号列に関する述語や言明を，ペアノの算術

^%&

を公理系とする形式的体系

^'

第

⁽

回の講義を参照

^$

での論理式や文に翻訳することが目標である．

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

(5)

ゲーデル数化

^{数理の世界}

ゲーデル数化

^!" ^#$

とは，ゲーデルが不完全性定理の証明で導入した，記号列を数にコードしするテクニックのことを言う．

記号列に関する述語や言明を，ペアノの算術

^%&

を公理系とする形式的体系

^'

第

⁽

回の講義を参照

^$

での論理式や文に翻訳することが目標である．

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

(6)

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

しかし，

*

項

#回

$ $$

を数

の表記として使える．数

に対応するこの項を

の数表記とよび

と表すことにする．

%&

では指数関数を定義する論理式を作ることができる．つまり，

の論理式

⁺ ^$

で，任意の数

^,^,

に対して，

%& $ + Ò

となるようなものが作れる

これはかなり複雑な論理式になるし，

その論理式が上の性質を持つことを示すには，「中国の剰余定理」という数論の定理が必要になる．

^$

以下では，

^Ò

の形の表現を，

^$

という形の論理式の略

記のことと思って，自由に使うことにする．

(7)

ゲーデル数化

^{数理の世界}

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

しかし，

*

項

#回

$ $$

を数

の表記として使える．数

に対応するこの項を

の数表記とよび

と表すことにする．

%&

では指数関数を定義する論理式を作ることができる．つまり，

の論理式

⁺ ^$

で，任意の数

^,^,

に対して，

%& $ + Ò

となるようなものが作れる

これはかなり複雑な論理式になるし，

その論理式が上の性質を持つことを示すには，「中国の剰余定理」という数論の定理が必要になる．

^$

以下では，

^Ò

の形の表現を，

^$

という形の論理式の略

記のことと思って，自由に使うことにする．

(8)

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

しかし，

*

項

#回

$ $$

を数

の表記として使える．数

に対応するこの項を

の数表記とよび

と表すことにする．

%&

では指数関数を定義する論理式を作ることができる．つまり，

の論理式

⁺ ^$

で，任意の数

^,^,

に対して，

%& $ + Ò

となるようなものが作れる

これはかなり複雑な論理式になるし，

その論理式が上の性質を持つことを示すには，「中国の剰余定理」という数論の定理が必要になる．

^$

以下では，

^Ò

の形の表現を，

^$

という形の論理式の略

記のことと思って，自由に使うことにする．

(9)

ゲーデル数化

^{数理の世界}

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

しかし，

*

項

#回

$ $$

を数

の表記として使える．数

に対応するこの項を

の数表記とよび

と表すことにする．

%&

では指数関数を定義する論理式を作ることができる．つまり，

の論理式

⁺ ^$

で，任意の数

^,^,

に対して，

%& $ + Ò

となるようなものが作れる

これはかなり複雑な論理式になるし，

その論理式が上の性質を持つことを示すには，「中国の剰余定理」という数論の定理が必要になる．

^$

以下では，

^Ò

の形の表現を，

^$

という形の論理式の略

記のことと思って，自由に使うことにする．

(10)

%&

の言語には定数記号や関数記号として，

，

)

，だけしか用意されていない．

しかし，

*

項

#回

$ $$

を数

の表記として使える．数

に対応するこの項を

の数表記とよび

と表すことにする．

%&

では指数関数を定義する論理式を作ることができる．つまり，

の論理式

⁺ ^$

で，任意の数

^,^,

に対して，

%& $ + Ò

となるようなものが作れる

これはかなり複雑な論理式になるし，

その論理式が上の性質を持つことを示すには，「中国の剰余定理」という数論の定理が必要になる．

^$

以下では，

^Ò

の形の表現を，

^$

という形の論理式の略

記のことと思って，自由に使うことにする．

(11)

ゲーデル数化

^{数理の世界}

記号

や記号列や記号列の列

を，それらをコードする数

-$,- $,-$

に規則的に対応させる方法のことをゲーデル数化

^!"^#$

とよぶ．

-$,- $,-$

の数表記を，

^,^,

とあらわすことにする．

ゲーデル数化は色々のやり方が考えられるが，たとえば，次のようにして実現することができる．

まず，使う記号を記号のカテゴリーごとに一列にならべておく．たとえば，論理記号として使う有限個の記号を

^,^,^,

とならべ，

変数記号として使うことにする

無限個の

^$

記号を

,

とならべ

^,

と続ける．

記号

が

番目のカテゴリーの

番目の記号のとき，この記号の

ゲーデル数を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であ

ることに注意する．

(12)

記号

や記号列や記号列の列

を，それらをコードする数

-$,- $,-$

に規則的に対応させる方法のことをゲーデル数化

^!"^#$

とよぶ．

-$,- $,-$

の数表記を，

^,^,

とあらわすことにする．

ゲーデル数化は色々のやり方が考えられるが，たとえば，次のようにして実現することができる．

まず，使う記号を記号のカテゴリーごとに一列にならべておく．たとえば，論理記号として使う有限個の記号を

^,^,^,

とならべ，

変数記号として使うことにする

無限個の

^$

記号を

,

とならべ

^,

と続ける．

記号

が

番目のカテゴリーの

番目の記号のとき，この記号の

ゲーデル数を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であ

ることに注意する．

(13)

ゲーデル数化

^{数理の世界}

記号

や記号列や記号列の列

を，それらをコードする数

-$,- $,-$

に規則的に対応させる方法のことをゲーデル数化

^!"^#$

とよぶ．

-$,- $,-$

の数表記を，

^,^,

とあらわすことにする．

ゲーデル数化は色々のやり方が考えられるが，たとえば，次のようにして実現することができる．

まず，使う記号を記号のカテゴリーごとに一列にならべておく．たとえば，論理記号として使う有限個の記号を

^,^,^,

とならべ，

変数記号として使うことにする

無限個の

^$

記号を

,

とならべ

^,

と続ける．

記号

が

番目のカテゴリーの

番目の記号のとき，この記号の

ゲーデル数を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であ

ることに注意する．

(14)

記号

や記号列や記号列の列

を，それらをコードする数

-$,- $,-$

に規則的に対応させる方法のことをゲーデル数化

^!"^#$

とよぶ．

-$,- $,-$

の数表記を，

^,^,

とあらわすことにする．

ゲーデル数化は色々のやり方が考えられるが，たとえば，次のようにして実現することができる．

まず，使う記号を記号のカテゴリーごとに一列にならべておく．たとえば，論理記号として使う有限個の記号を

^,^,^,

とならべ，

変数記号として使うことにする

無限個の

^$

記号を

,

とならべ

^,

と続ける．

記号

が

番目のカテゴリーの

番目の記号のとき，この記号の

ゲーデル数を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であ

ることに注意する．

(15)

ゲーデル数化

^{数理の世界}

記号

や記号列や記号列の列

を，それらをコードする数

-$,- $,-$

に規則的に対応させる方法のことをゲーデル数化

^!"^#$

とよぶ．

-$,- $,-$

の数表記を，

^,^,

とあらわすことにする．

ゲーデル数化は色々のやり方が考えられるが，たとえば，次のようにして実現することができる．

まず，使う記号を記号のカテゴリーごとに一列にならべておく．たとえば，論理記号として使う有限個の記号を

^,^,^,

とならべ，

変数記号として使うことにする

無限個の

^$

記号を

,

とならべ

^,

と続ける．

記号

が

番目のカテゴリーの

番目の記号のとき，この記号の

ゲーデル数を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であ

ることに注意する．

(16)

記号

や記号列や記号列の列

を，それらをコードする数

-$,- $,-$

に規則的に対応させる方法のことをゲーデル数化

^!"^#$

とよぶ．

-$,- $,-$

の数表記を，

^,^,

とあらわすことにする．

ゲーデル数化は色々のやり方が考えられるが，たとえば，次のようにして実現することができる．

まず，使う記号を記号のカテゴリーごとに一列にならべておく．たとえば，論理記号として使う有限個の記号を

^,^,^,

とならべ，

変数記号として使うことにする

無限個の

^$

記号を

,

とならべ

^,

と続ける．

記号

が

番目のカテゴリーの

番目の記号のとき，この記号の

ゲーデル数を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であ

ることに注意する．

(17)

ゲーデル数化

^{数理の世界}

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(18)

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(19)

ゲーデル数化

^{数理の世界}

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(20)

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(21)

ゲーデル数化

^{数理の世界}

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(22)

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(23)

ゲーデル数化

^{数理の世界}

記号

が

番目のカテゴリーの

番目の記号のとき，この記号のゲーデル数

^-^$

を

^Ñ ^Ò

とする．

^,^,

は最初の

つの素数であることに注意する．

たとえば，変数記号が

番目のカテゴリーの記号としてならべられているときには，

^.

数

は

^Ò

という形の数に分解される

^/

ということを表現するの論理式

⁺ ^$

を考えると，この論理式は，

^.

は

番目の変数記号のコードである

^/

と主張する論理式になっているとみなすことができる．

記号列

^Ò

に対し，このゲーデル数

^- ^Ò ^$

を，

数

^×^× Ò

×

のこととする．ただし，

Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデ

ル数の因数の最初の

は，この数が記号列をコードしていること

を表現するために使われている．

(24)

記号列

Ò

に対し，このゲーデル数

^-

Ò

$

を，

数

^×^× ^Ò^×

のこととする．ただし，

^Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデル数の因数の最初の

は，この数が記号列をコードしていることを表現するために使われている．

たとえば，

^.

は記号列をコードしている

^/

は，

.

を因数分解したときの

の指数は

で，因数の全体は素数列の最初の部分になっていて

以外の因数の指数はすべて記号をコードする数である

^/

を表す

*

論理式によって表現できる．

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

(25)

ゲーデル数化

^{数理の世界}

記号列

Ò

に対し，このゲーデル数

^-

Ò

$

を，

数

^×^× ^Ò^×

のこととする．ただし，

^Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデル数の因数の最初の

は，この数が記号列をコードしていることを表現するために使われている．

たとえば，

^.

は記号列をコードしている

^/

は，

.

を因数分解したときの

の指数は

で，因数の全体は素数列の最初の部分になっていて

以外の因数の指数はすべて記号をコードする数である

^/

を表す

*

論理式によって表現できる．

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

(26)

記号列

Ò

に対し，このゲーデル数

^-

Ò

$

を，

数

^×^× ^Ò^×

のこととする．ただし，

^Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデル数の因数の最初の

は，この数が記号列をコードしていることを表現するために使われている．

たとえば，

^.

は記号列をコードしている

^/

は，

.

を因数分解したときの

の指数は

で，因数の全体は素数列の最初の部分になっていて

以外の因数の指数はすべて記号をコードする数である

^/

を表す

*

論理式によって表現できる．

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

(27)

ゲーデル数化

^{数理の世界}

記号列

Ò

に対し，このゲーデル数

^-

Ò

$

を，

数

^×^× ^Ò^×

のこととする．ただし，

^Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデル数の因数の最初の

は，この数が記号列をコードしていることを表現するために使われている．

たとえば，

^.

は記号列をコードしている

^/

は，

.

を因数分解したときの

の指数は

で，因数の全体は素数列の最初の部分になっていて

以外の因数の指数はすべて記号をコードする数である

^/

を表す

*

論理式によって表現できる．

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

(28)

記号列

Ò

に対し，このゲーデル数

^-

Ò

$

を，

数

^×^× ^Ò^×

のこととする．ただし，

^Ò

は

番目の素数とする．

+,

+, +0,

である．ゲーデル数の因数の最初の

は，この数が記号列をコードしていることを表現するために使われている．

たとえば，

^.

は記号列をコードしている

^/

は，

.

を因数分解したときの

の指数は

で，因数の全体は素数列の最初の部分になっていて

以外の因数の指数はすべて記号をコードする数である

^/

を表す

*

論理式によって表現できる．

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

(29)

ゲーデル数化

^{数理の世界}

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

^*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

.

は自由変数

,,

Ò

を持つ論理式をコードしていて，

,,

Ò

は

*

項のコードで，

は，

のコードする論理式の変数

,,

Ò

に

^,,^Ò

を代入して得られる

^*

論理式をコードしている

^/

が記号列

,

Ò

の列のとき，

^-$

を

Ø

Ò Ø

のこととする．

.

は記号列の列をコードする数である

^/

を表現する

^*

論理式を作ることができる．

.

は記号列の列をコードする数で，

は

^*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

論理式を作ることができる．

(30)

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

^*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

.

は自由変数

,,

Ò

を持つ論理式をコードしていて，

,,

Ò

は

*

項のコードで，

は，

のコードする論理式の変数

,,

Ò

に

^,,^Ò

を代入して得られる

^*

論理式をコードしている

^/

が記号列

,

Ò

の列のとき，

^-$

を

Ø

Ò Ø

のこととする．

.

は記号列の列をコードする数である

^/

を表現する

^*

論理式を作ることができる．

.

は記号列の列をコードする数で，

は

^*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

論理式を作ることができる．

(31)

ゲーデル数化

^{数理の世界}

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

^*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

.

は自由変数

,,

Ò

を持つ論理式をコードしていて，

,,

Ò

は

*

項のコードで，

は，

のコードする論理式の変数

,,

Ò

に

^,,^Ò

を代入して得られる

^*

論理式をコードしている

^/

が記号列

,

Ò

の列のとき，

^-$

を

Ø

Ò Ø

のこととする．

.

は記号列の列をコードする数である

^/

を表現する

^*

論理式を作ることができる．

.

は記号列の列をコードする数で，

は

^*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

論理式を作ることができる．

(32)

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

^*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

.

は自由変数

,,

Ò

を持つ論理式をコードしていて，

,,

Ò

は

*

項のコードで，

は，

のコードする論理式の変数

,,

Ò

に

^,,^Ò

を代入して得られる

^*

論理式をコードしている

^/

が記号列

,

Ò

の列のとき，

^-$

を

Ø

Ò Ø

のこととする．

.

は記号列の列をコードする数である

^/

を表現する

^*

論理式を作ることができる．

.

は記号列の列をコードする数で，

は

^*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

論理式を作ることができる．

(33)

ゲーデル数化

^{数理の世界}

もう少し複雑なトリックがいくつか必要になるが，同様に次を表現する

^*

論理式を作ることができる

.

は

*

項となっている記号列をコードしている

^/

.

は

*

論理式となっている記号列をコードしている

^/

.

は自由変数

,,

Ò

を持つ論理式をコードしていて，

,,

Ò

は

*

項のコードで，

は，

のコードする論理式の変数

,,

Ò

に

^,,^Ò

を代入して得られる

^*

論理式をコードしている

^/

が記号列

,

Ò

の列のとき，

^-$

を

Ø

Ò Ø

のこととする．

.

は記号列の列をコードする数である

^/

を表現する

^*

論理式を作ることができる．

.

は記号列の列をコードする数で，

は

^*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

論理式を作ることができる．

(34)

.

は記号列の列をコードする数で，

は

*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

*

論理式を作ることができる．

上のような

*

論理式を，

$

と書くことにする．この論理式は次のような意味で，上の

^./

をよく表現するものとしてとることができる

%&

È

なら，

^%&

$

である．逆に

^%& ^È

でないなら，

^%&

$

である．

上に用意したことと

^1#1" ^{2 1}

を用いると，第１不完全性定

理が証明できることを前回見た．

^1#1" ^{2 1}

の証明は講義の

資料としてあげた，執筆中の本の，原稿の一部を参照．

(35)

ゲーデル数化

^{数理の世界}

.

は記号列の列をコードする数で，

は

*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

*

論理式を作ることができる．

上のような

*

論理式を，

$

と書くことにする．この論理式は次のような意味で，上の

^./

をよく表現するものとしてとることができる

%&

È

なら，

^%&

$

である．逆に

^%& ^È

でないなら，

^%&

$

である．

上に用意したことと

^1#1" ^{2 1}

を用いると，第１不完全性定

理が証明できることを前回見た．

^1#1" ^{2 1}

の証明は講義の

資料としてあげた，執筆中の本の，原稿の一部を参照．

(36)

.

は記号列の列をコードする数で，

は

*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

*

論理式を作ることができる．

上のような

*

論理式を，

$

と書くことにする．この論理式は次のような意味で，上の

^./

をよく表現するものとしてとることができる

%&

È

なら，

^%&

$

である．逆に

^%& ^È

でないなら，

^%&

$

である．

上に用意したことと

^1#1" ^{2 1}

を用いると，第１不完全性定

理が証明できることを前回見た．

^1#1" ^{2 1}

の証明は講義の

資料としてあげた，執筆中の本の，原稿の一部を参照．

(37)

ゲーデル数化

^{数理の世界}

.

は記号列の列をコードする数で，

は

*

論理式をコードする数で，

のコードする記号列の列は

のコードする論理式の

^%&

からの証明である

^/

を表現する

*

論理式を作ることができる．

上のような

*

論理式を，

$

と書くことにする．この論理式は次のような意味で，上の

^./

をよく表現するものとしてとることができる

%&

È

なら，

^%&

$

である．逆に

^%& ^È

でないなら，

^%&

$

である．

上に用意したことと

^1#1" ^{2 1}

を用いると，第１不完全性定

理が証明できることを前回見た．

^1#1" ^{2 1}

の証明は講義の

資料としてあげた，執筆中の本の，原稿の一部を参照．

(38)

上で導入した

$

と同様の論理式を，具体的に書くことのできる理論

に対しても

Ì

$

として書くことができる．

Ì

$

を

Ì

$

と書くことにする．

Ì

$

は，

のコードする論理式が

で証明できることを主張する

*

論理式となっている．

Ì

$

を考えると，これは

が矛盾しない

^$

ことを主張する

*

文になっていることがわかる．この文のことを

Ì

と書くことにする．

定理

第２不完全性定理

．

^%&

を含む

あるいは

^%&

がそこで解釈できる

^$

具体的に与えられた理論

が無矛盾なら，

Ì

は

で証明できない．

(39)

第２不完全性定理

^{数理の世界}

上で導入した

$

と同様の論理式を，具体的に書くことのできる理論

に対しても

Ì

$

として書くことができる．

Ì

$

を

Ì

$

と書くことにする．

Ì

$

は，

のコードする論理式が

で証明できることを主張する

*

論理式となっている．

Ì

$

を考えると，これは

が矛盾しない

^$

ことを主張する

*

文になっていることがわかる．この文のことを

Ì

と書くことにする．

定理

第２不完全性定理

．

^%&

を含む

あるいは

^%&

がそこで解釈できる

^$

具体的に与えられた理論

が無矛盾なら，

Ì

は

で証明できない．

(40)

上で導入した

$

と同様の論理式を，具体的に書くことのできる理論

に対しても

Ì

$

として書くことができる．

Ì

$

を

Ì

$

と書くことにする．

Ì

$

は，

のコードする論理式が

で証明できることを主張する

*

論理式となっている．

Ì

$

を考えると，これは

が矛盾しない

^$

ことを主張する

*

文になっていることがわかる．この文のことを

Ì

と書くことにする．

定理

第２不完全性定理

．

^%&

を含む

あるいは

^%&

がそこで解釈できる

^$

具体的に与えられた理論

が無矛盾なら，

Ì

は

で証明できない．

(41)

第２不完全性定理

^{数理の世界}

上で導入した

$

と同様の論理式を，具体的に書くことのできる理論

に対しても

Ì

$

として書くことができる．

Ì

$

を

Ì

$

と書くことにする．

Ì

$

は，

のコードする論理式が

で証明できることを主張する

*

論理式となっている．

Ì

$

を考えると，これは

が矛盾しない

^$

ことを主張する

*

文になっていることがわかる．この文のことを

Ì

と書くことにする．

定理

第２不完全性定理

．

^%&

を含む

あるいは

^%&

がそこで解釈できる

^$

具体的に与えられた理論

が無矛盾なら，

Ì

は

で証明できない．

(42)

上で導入した

$

と同様の論理式を，具体的に書くことのできる理論

に対しても

Ì

$

として書くことができる．

Ì

$

を

Ì

$

と書くことにする．

Ì

$

は，

のコードする論理式が

で証明できることを主張する

*

論理式となっている．

Ì

$

を考えると，これは

が矛盾しない

^$

ことを主張する

*

文になっていることがわかる．この文のことを

Ì

と書くことにする．

定理

第２不完全性定理

．

^%&

を含む

あるいは

^%&

がそこで解釈できる

^$

具体的に与えられた理論

が無矛盾なら，

Ì

は

で証明できない．

(43)

指数関数が

^%&

で論理式で表せることの説明で「中国の剰余定理」について触れた．ゲーデルはウィーン大学の学部生のころ，

^%

フルトヴェングラー

34

明治

^$ ⁴⁵

昭和

^$,

指揮者フルトヴェングラーのいとこ

^$

ゲーデルの不完全性定理 ゲーデル数化と第２不完全性定理， 第

数理の世界

数学の考え方