数理の世界 数学の考え方

数理の世界 数学の考え方

         ゲーデルの不完全性定理 形式的証明，体系の無矛盾性と完全性， 第

回の講義

渕野 昌

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

神戸大学年後期の講義 於 教室，月曜

"# $

述語論理の体系

復習

・ トートロジーから得られた恒真な 論理式，

・ 等号の公理

! " ! " ! "

#! $ ! $ !

!

$

! $

!

・ 代入公理 を 論理式として， 変数記号， を 項と するとき，^!の形の論理式で，変数の「からまり」

のないもの

言語 に対する体系 の推論規則 三段論法

存在推論

ただし， は には自由変数としては現 れないものとする．

述語論理の体系

復習

・ トートロジーから得られた恒真な 論理式，

・ 等号の公理

! " ! " ! "

#! $ ! $ !

!

$

! $

!

・ 代入公理 を 論理式として， 変数記号， を 項と するとき，^!の形の論理式で，変数の「からまり」

のないもの

言語 に対する体系 の推論規則 三段論法

存在推論

ただし， は には自由変数としては現 れないものとする．

述語論理の体系

復習

・ トートロジーから得られた恒真な 論理式，

・ 等号の公理

! " ! " ! "

#! $ ! $ !

!

$

! $

!

・ 代入公理 を 論理式として， 変数記号， を 項と するとき，^!の形の論理式で，変数の「からまり」

のないもの

言語 に対する体系 の推論規則 三段論法

存在推論

ただし， は には自由変数としては現 れないものとする．

述語論理の体系

復習

論理式の集合 ^%と 論理式 に対し， 論理式の列

& $

が の ^% からの での 証明である，とは 次の ^! と^! が成り立つこととする

!

&"

! すべての に対し，次が成り立つ

!

%であるか， または，

!

は の論理公理であるか， または，

! が存在して，

が 三段論法 になってい るか， または，

#! が存在して，

が 存在推論 になっているかの いずれかである．

% からの の証明が存在するとき，これを ^% とあらわす．

が の^%からの証明のとき，これを ^% とあらわす．

述語論理の体系

復習

論理式の集合 ^%と 論理式 に対し， 論理式の列

& $

が の ^% からの での 証明である，とは 次の ^! と^! が成り立つこととする

!

&"

! すべての に対し，次が成り立つ

!

%であるか， または，

!

は の論理公理であるか， または，

! が存在して，

が 三段論法 になってい るか， または，

#! が存在して，

が 存在推論 になっているかの いずれかである．

% からの の証明が存在するとき，これを ^% とあらわす．

が の^%からの証明のとき，これを ^% とあらわす．

述語論理の体系

復習

論理式の集合 ^%と 論理式 に対し， 論理式の列

& $

が の ^% からの での 証明である，とは 次の ^! と^! が成り立つこととする

!

&"

! すべての に対し，次が成り立つ

!

%であるか， または，

!

は の論理公理であるか， または，

! が存在して，

が 三段論法 になってい るか， または，

#! が存在して，

が 存在推論 になっているかの いずれかである．

% からの の証明が存在するとき，これを ^% とあらわす．

が の^%からの証明のとき，これを ^% とあらわす．

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

$ $$

を並べた， ^&

$

は，

' の ⁽⁾からの証明になっている．

' ' ! 代入公理

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ' トートロジー

'

' ' !

三段論法

' ' !

' ' ! トートロジー

' ' !

三段論法

' ' ! 存在推論

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

での証明の例

' ' !

' ' ! トートロジー

' ' !

三段論法

'

'

三段論法

'

三段論法

() では，^!$!!$!!! を，数表記 ^$$$ のこと と考えられるのだった．

演習問題． ^{() !} となることを示せ．

理論の無矛盾性

文の集まり を 理論 とよぶことにする．

たとえば ⁽⁾は

理論である．

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

理論の無矛盾性

文の集まり を 理論 とよぶことにする．

たとえば ⁽⁾は

理論である．

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

理論の無矛盾性

文の集まり を 理論 とよぶことにする．

たとえば ⁽⁾は

理論である．

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

理論の無矛盾性

文の集まり を 理論 とよぶことにする．

たとえば ⁽⁾は

理論である．

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

理論の無矛盾性

文の集まり を 理論 とよぶことにする．

たとえば ⁽⁾は

理論である．

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

定理 を 理論とするとき，次は同値である

"

すべての 論理式 に対し， が成り立つ．

証明． は明らかである．

を仮定して， を の からの証明と する．

を任意の 論理式とするとき， に次の ^$

$

とをつ なげた列は の からの証明になる

トートロジー

等式の公理 ^!

三段論法

三段論法

理論の無矛盾性

同様の証明で，上の ^$ は次とも同値になるこが示せる

ある 論理式 に対し かつ

理論 が または^*かつ ^{$ !} を満たすとき， は 矛盾 する という．そうでないとき， は 無矛盾である，という．

を無矛盾な 理論とするとき， が完全 であるとは，すべて の 文に対し， か のどちらか片方が必ず成り 立つこととする．

理論の無矛盾性

同様の証明で，上の ^$ は次とも同値になるこが示せる

ある 論理式 に対し かつ

理論 が または^*かつ ^{$ !} を満たすとき， は 矛盾 する という．そうでないとき， は 無矛盾である，という．

を無矛盾な 理論とするとき， が完全 であるとは，すべて の 文に対し， か のどちらか片方が必ず成り 立つこととする．

理論の無矛盾性

同様の証明で，上の ^$ は次とも同値になるこが示せる

ある 論理式 に対し かつ

理論 が または^*かつ ^{$ !} を満たすとき， は 矛盾 する という．そうでないとき， は 無矛盾である，という．

を無矛盾な 理論とするとき， が完全 であるとは，すべて の 文に対し， か のどちらか片方が必ず成り 立つこととする．

理論の無矛盾性

同様の証明で，上の ^$ は次とも同値になるこが示せる

ある 論理式 に対し かつ

理論 が または^*かつ ^{$ !} を満たすとき， は 矛盾 する という．そうでないとき， は 無矛盾である，という．

を無矛盾な 理論とするとき， が完全 であるとは，すべて の 文に対し， か のどちらか片方が必ず成り 立つこととする．

理論の無矛盾性

同様の証明で，上の ^$ は次とも同値になるこが示せる

ある 論理式 に対し かつ

理論 が または^*かつ ^{$ !} を満たすとき， は 矛盾 する という．そうでないとき， は 無矛盾である，という．

を無矛盾な 理論とするとき， が完全 であるとは，すべて の 文に対し， か のどちらか片方が必ず成り 立つこととする．

第１不完全性定理

以上で第１不完全性定理を厳密に述べることが可能になった 定理 第１不完全性定理，ゲーデル 昭和 ロッサー

昭和

() を含み，矛盾しない，具体的に与えられた^! どんな理論 も完全でない．

第１不完全性定理から，特に ⁽⁾自身も完全でないことがわかる．

第１不完全性定理

以上で第１不完全性定理を厳密に述べることが可能になった 定理 第１不完全性定理，ゲーデル 昭和 ロッサー

昭和

() を含み，矛盾しない，具体的に与えられた^! どんな理論 も完全でない．

第１不完全性定理から，特に ⁽⁾自身も完全でないことがわかる．

クルト・ゲーデル

明治 昭和

昭和年の写真