ゲーデルの不完全性定理の証明について簡単に触れたいと思います. 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において,「形式的体系が無矛盾である」という命題を表現する論理式の選び方は一通りではありません.
by yojisekimoto
| 2010-02-26 14:51
| 数学
|
プロフィール
横浜在住。ナマケモノ倶楽部、TCX会員。参加している地域通貨は、Q(ID名は6463749)、三鷹seeds、鴨川安房マネー、多摩COMO、千姫プロジェクト(IDは「ヨウジ」)、千葉ピーナッツ、ccsp各種(IDはyojisekimoto)です。
フォロー中のブログ
カテゴリ
全体 研究 歌詞 書評 日記 柄谷行人 歴史 ヘーゲル マルクス ハイデガー 地域通貨 環境問題 プルードン パーソンズ フロイト くじ引き カント 横浜 スピノザ ライプニッツ ニーチェ 映画 SBS 旅 老子 スポーツ 数学 ディラン 黒澤明 音楽 インド哲学 文学 科学 心理学 ドゥルーズ 原発 仏教 百人一首 孔子 哲学 未分類 以前の記事
2016年 10月 2016年 03月 2015年 05月 2015年 03月 2015年 02月 2015年 01月 2014年 11月 2014年 10月 2014年 06月 2014年 05月 2014年 01月 2013年 12月 2013年 11月 2013年 10月 2013年 09月 2013年 08月 2013年 07月 2013年 06月 2013年 05月 2013年 04月 2013年 02月 2013年 01月 2012年 12月 2012年 11月 2012年 10月 2012年 09月 2012年 08月 2012年 07月 2012年 05月 2012年 04月 2012年 03月 2012年 02月 2012年 01月 2011年 12月 2011年 11月 2011年 10月 2011年 09月 2011年 08月 2011年 07月 2011年 06月 2011年 05月 2011年 04月 2011年 03月 2011年 02月 2011年 01月 2010年 12月 2010年 11月 2010年 10月 2010年 09月 2010年 08月 2010年 07月 2010年 06月 2010年 05月 2010年 04月 2010年 03月 2010年 02月 2010年 01月 2009年 12月 2009年 11月 2009年 10月 2009年 09月 2009年 08月 2009年 06月 2009年 05月 2009年 04月 2009年 03月 2009年 02月 2009年 01月 2008年 12月 2008年 11月 2008年 10月 2008年 09月 2008年 08月 2008年 07月 2008年 06月 2008年 05月 2008年 04月 2008年 03月 2008年 02月 2008年 01月 2007年 12月 2007年 11月 2007年 10月 2007年 09月 2007年 08月 2007年 07月 2007年 06月 2007年 05月 2007年 04月 2007年 03月 2007年 02月 2007年 01月 2006年 12月 2006年 11月 2006年 10月 2006年 09月 2006年 08月 2006年 06月 2006年 05月 2006年 04月 2006年 03月 2006年 02月 2006年 01月 2005年 12月 2005年 09月 2005年 08月 2005年 06月 2005年 05月 2005年 04月 2005年 03月 2005年 02月 2005年 01月 2004年 06月 検索
タグ
その他のジャンル
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||