プレスバーガー算術は本質的なのか？

ゲーデルの不完全性定理にあらわれる「ある程度の初等算術が実行できる」という表現を、ひとまず、ＰＡ算術と考えれば、この１階算術では足し算と掛け算が実行できる。最低限の算術として、足し算と掛け算がやれなかったら、初歩的な自然数論の結果すら使えないということになるわけで、そんなことは当たり前じゃないか、と思われるわけだが、実は以下のことが知られている：

• プレスバーガー算術（足し算のみのＰＡ） ... 完全
• スコーレム算術（掛け算のみのＰＡ） ... 完全
• 実閉体（一階の実数算術） ... 完全
• 複素閉体（一階の複素数算術） ... 完全

つまり、これら四つの理論では、ゲーデルの不完全性定理が成り立たない。それは、これらが条件の「ある程度の初等算術が実行できる」を満たしていないからであるわけだが、これがなんなのかを最初に聞かされたときは、よく飲み込めなかったものである。

現代の公理論的な立場でも、関数の追加はできるが、それは定義による拡大によってのみ行われる（3.4節参照）。つまり、「Ｔから「∀x∃1yφ(x,y)」が証明される」が成り立つとき ∀x∀yφ(x,y) ⇔ f(x)=y となる関数 f を理論 Ｔ に追加できる。しかし、掛け算がない体系（PA-A5-A6）では、掛け算 xy=z を足し算だけの論理式 φ(x,y,z) で表せないので、PA-A5-A6 は PA より真に弱い体系である。同様なことは、掛け算をもち、足し算をもたない体系についてもいえるが、そもそも足し算なしに掛け算の公理を記述することは容易でない。

数の体系と超準モデル

普通に考えると、掛け算は足し算から「定義」できるような感じがする。しかし、もしも定義できてしまうと、ゲーデルの不完全性定理により矛盾となるので、どちらかも定義できないことが分かる（なるほど、プレスバーガー算術でゲーデルの不完全性定理が成り立たないのは、ゲーデル数が定義できないからだな、と思った人は鋭いが、本質はそこになる、ということ）。なぜ、こんなことになるのか？　それはよく考えてみると、この場合に考えているのは、「1,1+1,1+1+1,...」となる「自然数の集合」をイメージしていることが分かる。確かに、プレスバーガー算術は先の数を体系の中に含んでいる。しかし、それ以外が含まれていないかどうかは、この理論からだけでは導けない。つまり、この場合の「自然数の集合」を定義できないことが、この事情をもたらしている、ということになるのであろう。
同じことは、実閉体、複素閉体についても言える（これらの定義は、足し算、割り算を含む体に、それぞれの、代数方程式の元の存在定理を付加したものになる）。

不完全性定理は、あらゆる無矛盾な形式体系が不完全であることを意味するものではない。それどころか、完全で無矛盾な形式体系もたくさんある。数学的な立場でとくに興味ある例は、「実数の初等理論」である。（別の例として、プレスバーガー算術として知られる理論について、第７章で述べる。）この理論の言語は、算術の言語と同様で、数の加算と乗算について語ることができる。しかし、今度は自然数でなく実数に関するものである。

ゲーデルの定理――利用と誤用の不完全ガイド

実数の完全な理論は、このような種類の言明を証明する。上の例からも明らかなように、この理論は取るに足りないようなものでは決してなく、それは電子工学、計算幾何学、最適化理論、その他の分野で、多数の応用をもっている。
自然数全体は実数の部分集合を構成するので、自然数の理論が不完全であるのぬい、実数の理論が完全になることは奇妙に思われるかもしれない。けれども、自然数の理論の不完全性が実数の理論に転移するわけではない。というのは、すべての自然数全体が実数の部分集合であっても、私たちは実数の理論の言語だけを使って自然数全体実数の部分集合として定義できないからだ。例えば実数の理論では、「0 より大きな自然数 m,n,k が存在して、m^3+n^3=k^3 である」という言明は表現することができないのだ。他方、「0 より大きな実数 r,s,t が存在して、r^3+s^3=t^3 である」という言明なら実数の理論で表現できるし、そしてこれを簡単に証明することもできる。
ふつう私たちはどのようにして自然数を実数の部分集合として定義しているだろうか？　実数 0 と 1 は、対応する自然数と同一視でき、そして実数の加算を使って、自然数全体は、0,1,1+1,1+1+1 などからなる実数の部分集合として認知することができる。しかしながら、この「などからなる」は、実数の理論の言語で表現できないのだ。自然数の定義を定式化するもうひとつの方法は、自然数は、次の条件を満たすすべての実数集合Ａに属する実数とするものである。実数集合Ａは、0 を含んでいて、1 を足す操作の下で閉じている。すなわち x がＡに属するときは必ず x+1 もＡに属するという条件である。この定義は、実数の集合に言及することが可能な２階の言語を使っている。実数の初等理論［１階理論と同様］の言語は、初等算術の言語と同様に、数について述べることが可能なだけで、数の集合について言及することはできない。
ゲーデルの定理――利用と誤用の不完全ガイド

なーんだ、と思ったのではないか。くっだらない、と。だって、ここでの差異って「集合が定義できるかできないか」の違いでしかなかったじゃん、と。それを「禁止」していたか、していなかったか、でしかなかった、と。、そりゃあ、いろいろ「禁止」すれば、違った結果にはなるだろうけど、それってなんの意味があるの？、と。
確かにこれは、ゲーデルの不完全性定理を中心に考えると、つまらない話にしか聞こえないかもしれないが、よく考えてみると、大変なことなのだ。
だって、上記の４つの理論は、「完全」なのだから、（この場合の）「ヒルベルトのプログラム」が実現できている、ということなのだから！　つまり、コンピュータで、（ある種の）「自動計算」アルゴリズムが作れるわけで、おそらくは、こういったプログラムが、さまざまな応用的な分野で活躍することが予想されるだろう...。
（さて。上記の４つの算術であるが、スコーレム算術を除いては、
数の体系と超準モデル
がまず、網羅的に書いてある。以下はこの本で参照されているが、スコーレム算術は
Craig Smorynski「Logical Number Theory I: An Introduction」
に紹介されている（こちらは、素数の公理など、かなり多くの公理を作ってましたが、ちょっと考えただけでも、足し算を使わないで掛け算系の定理を証明するって、大変そうですわね）。
また、実閉体は、

数学基礎論の世界―ロジックの雑記帳から

でも詳しく紹介されている。）