2008年 10月 04日 ( 1 )

形式システムにおける証明の概念

『ゲーデル、エッシャー、バッハ』(ダグラス・R・ホフスタッター著、白揚社)という本の第2章「数学における意味と形」に「pqシステム」と呼ばれる形式システムが紹介されている。この本は、ゲーデルの不完全性定理の「うまい説明」を語るものだが、そのためには700ページ以上の文章を必要としている。この形式システムの説明では、形式システムにおける「証明」ということが、一般的に日常言語で語られている「証明」とどのように違っているかが説明される。ゲーデルの不完全性定理の理解には、この区別を理解することが必要なのだ。

この章では、普通の意味での「証明」の例として素数が無限に存在するということを証明する「ユークリッドの定理」が紹介されている。これとの比較で形式システムの「証明」を考えると分かりやすいかもしれない。素数というのは中学校程度の数学の知識で理解できるし、ユークリッドの証明もおそらく中学程度の数学の理解があれば判ると思うからだ。

素数は「1とその数自身以外に約数を持たない数」と定義される。具体的には

  2,3,5,7,11,13,17,19,23,29,……

というような数が素数になる。1は素数の中に入れない。これは素因数分解の一意性を保証するためである。1を素数に入れてしまえば、因数としての1は何回でも使えるので素因数分解がただ一つに決定しなくなってしまう。

More
[PR]
by ksyuumei | 2008-10-04 20:20 | 論理