ゲーデルの不完全性定理:メモ

a0024841_184736.jpg

 ゲーデルの不完全性定理の証明について簡単に触れたいと思います.
 http://mathematics.web.infoseek.co.jp/column/incomplete.html

 証明における主なステップは,次の通りです.

1. 数学を形式的に表現することに関して,「各自然数ごとに表現可能」という概念を導入する.
2. 「原始帰納的」と呼ばれる関数が各自然数ごとに表現可能であるという,「表現定理」を証明する.
3. 数学の証明の一部を 「ゲ ー デ ル 数」と呼ばれる数に対応させることで証明をある意味で計算できるようにする.

           ___
          |   |
          |超数学|
          |___|
      1    /  \↓ 算術化 3
   超数学的考察↑ /    \(ゲーデル数)
   ______/_    _\ _    ______ 
  |形式的自然数論を|  |超算術的|  |原始帰納的 |2
  |含んだ形式的体系|←→| 体系 |←ー|関数(述語)|
  |________|2 |____|  |______| 
           表現定理    形式的体系の有限    
                   の立場での記述    
           図5.1全体の構図

http://www.sanynet.ne.jp/~norio-n/NIKKI/45.html
< 若干の蛇足。足立恒雄著『たのしむ数学10話』に、ライプニッツが命題に文字をあてはめた(命題変数を導入した)最初の人であったこと、「それどころか、原始的概念に素数を割り当て、合成数に積を割り当て、「論証を数の計算に還元する」という驚くべき構想まで書き残して」いたこと、そしてこの「論証の算術化」という構想の実現は二十世紀のゲーデルをまたなければならなかったことが書かれている。>


4. カントールの 対 角 線 論 法 のアイデアを用いて, 「対角化定理」と呼ばれる,論理式における不動点定理のようなものを証明する.

補足:
            内容
   | 1,  2,  ・ ・ ・,  n,  ・ ・ ・
___|____________________
f1(y) |f1(1) f1(2)  ・ ・ ・ f1(n) ・ ・ ・
f2(y) |f2(1) f2(2)  ・ ・ ・ f2(n) ・ ・ ・   
・  |・   ・   ・     ・
・  |・   ・     ・   ・
・  |・   ・       ・ ・
fn(y) |fn(1) fn(2)  ・ ・ ・ fn(n) ・ ・ ・
・  |・   ・         ・  ・  
・  |・   ・         ・     ・ 
・  |・   ・         ・       ・

< ¬は否定だから最後につけ加えればよいから、ヨxP(x,n,n)について考えてみよう。これは、「ゲーデル数がnである一変数 y を含む命題(すなわちfn(y) )の変数 y に数nを代入した命題の形式証明のゲーデル数となる x が存在する」という内容を持ち、したがって¬∃xP(x,n,n)はこれの否定、すなわち繰り返しを嫌わずに書けば「ゲーデル数がnである一変数 y を含む命題の変数yに数nを代入した命題の形式証明のゲーデル数となる x が存在しない」となる。
 ところが、ゲーデル数nを持つ一変数を持つ一変数yを含む命題とは fn(y)のことであり、fn(y)とはすなわち¬ヨxP(x,y,y)であった。すなわち上の文章を簡単に書けば,「¬∃xP(x,n,n)の形式証明は存在しない」ということで「¬∃xP(x,n,n)は証明できない」ということになる。ところが、この「 」内の命題こそ¬∃xP(x,n,n)に他ならない!
 ついにわれわれは「この命題は証明できない」のきちんとした数学的表現を入手することに成功したのである。
(略)
 ここで用いられた論法が一種の対角線論法であることに十分注意を払ってもらいたい。一変数の命題をすべて一列に並べ、f1(y) ,f2(y) ,・・・とし f1(1) , f1(2) ,・・・f n(n),・・・を考察するというのはまさしく対角線論法そのものである。カントールによって集合の階層構造を引き出すために考案された一線論法は,集合論内のパラドックスと絡まりあいながら、ゲーデルによる決定不能命題の発見という20世紀数最高の結果の一つを生み出すにいたったのである。>

(『はじめての現代数学』瀬山士郎著、講談社現代新書p161-163より。早川文庫より復刊)

5. 決定不可能な論理式,つまり自分自身もその否定も体系内では証明できないような論理式 U を構成する.(第一 不 完 全 性 定 理)
6. 「体系は無矛盾である」という命題を体系内の論理式として表現する. その論理式を C とおく.
7. 「 C が体系内で証明できるならば U も体系内で証明できる」ということを証明する. このとき, U は体系内では証明できない論理式だから, C もまた体系内では証明できない論理式である. (第 二 不 完 全 性 定 理)

           ___
          |   |
          | U |
          |___|
      1    /  \↓ 算術化 3
   超数学的考察↑ /    \(ゲーデル数)
   ______/_    _\ _    ______ 
  |形式的自然数論を|  |    |  |原始帰納的 |2
  |含んだ形式的体系|←→| C  |←ー|関数(述語)|
  |________|2 |____|  |______| 
           表現定理    形式的体系の有限    
                   の立場での記述    
           図5.1全体の構図



///////////

           ___
          |   |
          |超数学|
          |___|
           /  \↓ 算術化 3
   超数学的考察↑ /1   \(ゲーデル数)
   ______/_    _\ _    ______ 
  |形式的自然数論を|  |超算術的|  |原始帰納的 |2
  |含んだ形式的体系|←→| 体系 |←ー|関数(述語)|
  |________|4 |____|  |______| 
           表現定理    形式的体系の有限    
                   の立場での記述    
           図5.1全体の構図

 次に不完全性定理の証明の概略を説明しておこう。問題になる公理系は自然数論を実質
的に含む形式的体系でなくてはならない。

そこでまず第1に、自然数論の形式的体系をみることにする。このような形式的体系、す
なわち自然数論でのさまざまな記号や記号の列や証明図を扱うのが超数学であるが、これ
は直観的数論をもとに記号を扱う一種の算術、いわば超算術的体系ということができる。

そこで第2に、前章で定義した原始帰納的関数(述語)や一般帰納的関数(述語)がいず
れもこの超算術的体系の中に展開できることをみる。原始帰納的述語は有限の立場にもと
づいていたものであるが、一般帰納的述語は必ずしもそうではない。

不完全性定理の証明には原始帰納的関数(述語)だけが使われる。

第3に、超数学で扱う対象の算術化、すなわちゲーデル数化によって超算術的体系を考え、
必要な述語の定義をおこなう。

そして第4に、超算術的体系での帰納的述語が形式的体系の論理式として表現できること
をみる。こうして形式的体系と超数学と超算術的体系との問の対応づけによって、証明
の準備が完了し、前述した決定不可能な論理式を構成し、不完全性定理の証明がおこな
われることになる。全体の構図は図5.1のようになる。

『ゲーデルの世界』(海鳴社p114より。図は番号を振り左右を反転した。)



不完全性定理の証明は、対角線論法とゲーデル数のアイデアの意義だけ解ればOK

超初心者には以下がお勧め
不完全性定理 ―数学的体系のあゆみ 野崎 昭弘 著 ちくま学芸文庫
はじめての現代数学 (講談社現代新書) (新書) 瀬山 士郎 (著)


            内容
   | 1,  2,  ・ ・ ・,  n,  ・ ・ ・
___|____________________
f1(y) |f1(1) f1(2)  ・ ・ ・ f1(n) ・ ・ ・
f2(y) |f2(1) f2(2)  ・ ・ ・ f2(n) ・ ・ ・   
・  |・   ・   ・     ・
・  |・   ・     ・   ・
・  |・   ・       ・ ・
fn(y) |fn(1) fn(2)  ・ ・ ・ fn(n) ・ ・ ・
・  |・   ・         ・  ・  
・  |・   ・         ・     ・ 
・  |・   ・         ・       ・

 ¬は否定だから最後につけ加えればよいから、ヨxP(x,n,n)について考えてみよう。これは、
「ゲーデル数がnである一変数 y を含む命題(すなわちfn(y) )の変数 y に数nを代入した命題
の形式証明のゲーデル数となる x が存在する」という内容を持ち、したがって¬∃xP(x,n,n)は
これの否定、すなわち繰り返しを嫌わずに書けば「ゲーデル数がnである一変数 y を含む命題
の変数yに数nを代入した命題の形式証明のゲーデル数となる x が存在しない」となる。
 ところが、ゲーデル数nを持つ一変数を持つ一変数yを含む命題とは fn(y)のことであり、
fn(y)とはすなわち¬ヨxP(x,y,y)であった。すなわち上の文章を簡単に書けば,「¬∃xP(x,n,n)の形式
証明は存在しない」ということで「¬∃xP(x,n,n)は証明できない」ということになる。ところ
が、この「 」内の命題こそ¬∃xP(x,n,n)に他ならない!
 ついにわれわれは「この命題は証明できない」のきちんとした数学的表現を入手すること
に成功したのである。
(略)
 ここで用いられた論法が一種の対角線論法であることに十分注意を払ってもらいたい。一変数
の命題をすべて一列に並べ、f1(y) ,f2(y) ,・・・とし f1(1) , f1(2) ,・・・f n(n),・・・を考察
するというのはまさしく対角線論法そのものである。カントールによって集合の階層構造を引き出
すために考案された一線論法は,集合論内のパラドックスと絡まりあいながら、ゲーデルによる
決定不能命題の発見という20世紀数最高の結果の一つを生み出すにいたったのである。

(『はじめての現代数学』瀬山士郎著、講談社現代新書p161-163より。早川文庫より復刊)

http://www.sanynet.ne.jp/~norio-n/NIKKI/45.html
 若干の蛇足。足立恒雄著『たのしむ数学10話』に、ライプニッツが命題に文字を
あてはめた(命題変数を導入した)最初の人であったこと、「それどころか、原始
的概念に素数を割り当て、合成数に積を割り当て、「論証を数の計算に還元する」
という驚くべき構想まで書き残して」いたこと、そしてこの「論証の算術化」とい
う構想の実現は二十世紀のゲーデルをまたなければならなかったことが書かれてい
る。

http://mathematics.web.infoseek.co.jp/column/incomplete.html
 ゲーデルの不完全性定理の証明について簡単に触れたいと思います.

 証明における主なステップは,次の通りです.

1. 数学を形式的に表現することに関して,「各自然数ごとに表現可能」という概念を導入する.
2. 「原始帰納的」と呼ばれる関数が各自然数ごとに表現可能であるという,「表現定理」を証明する.
3. 数学の証明の一部を 「ゲ ー デ ル 数」と呼ばれる数に対応させることで証明をある意味で計算できるようにする.
4. カントールの 対 角 線 論 法 のアイデアを用いて, 「対角化定理」と呼ばれる,論理式における不動点定理のようなものを証明する.
5. 決定不可能な論理式,つまり自分自身もその否定も体系内では証明できないような論理式 U を構成する.(第一 不 完 全 性 定 理)
6. 「体系は無矛盾である」という命題を体系内の論理式として表現する. その論理式を C とおく.
7. 「 C が体系内で証明できるならば U も体系内で証明できる」ということを証明する. このとき, U は体系内では証明できない論理式だから, C もまた体系内では証明できない論理式である. (第 二 不 完 全 性 定 理)

 上の証明のステップ6において,「形式的体系が無矛盾である」という命題を表現する論理式の選び方は一通りではありません.
[PR]
by yojisekimoto | 2010-02-26 14:51 | 数学


<< スポーツと国家 ヘーゲル「討論テーゼ」 >>