べき乗と乗算のための原始再帰述語
私は以下の非公式に述べられ、弱く保持された信念を持っています、それらのいくつかはさらに熟考すると私には矛盾しているように見えます。私の思考の誤りの原因はどこにあるのだろうかと思っています。基本的な定義の誤りは確かな可能性です。
整数の1次理論では、加算と乗算を使用して量化記号消去法を実行することはできません。（これは、私が知る限り、最初の不完全性定理のわずかに強力なバージョンです。）
加算と乗算を使用した整数の1次理論では、べき乗の原始再帰述語を定義することができます。（べき乗の述語とは、「次のように動作するものを意味します」$Fabc\text{ just when }a^b = c.$"）
2つの演算で整数の1次理論で量化記号消去法を実行することが可能です$a \oplus b = \min(a, b)$ そして $a \otimes b = a + b$（つまり、通常の整数の加算）。素数が実際に量化記号消去法を実行するには、分割可能述語と乗算演算子も必要であることを私は知っています。
演算を伴う整数の一階理論では $\oplus$ そして $\otimes$、乗算の原始再帰述語を定義することができます（上記のべき乗の述語とほぼ同じ方法で）。
大まかに言えば、「通常の作戦塔」との類似性が崩れているようです。 $(+, \times, \hat{\phantom{n}}, \cdots)$ と「熱帯の作戦塔」 $(\min, +, \times, \cdots)$。
より具体的には、（4）と（3）が真である場合、なぜ乗算述語を自由に使用できないのか理解できず、（（3）を介して）量化記号消去法を実行でき、実行できない状況になります。量化記号消去法（（1）による）。（2）が真であるが、（4）が真でなかった場合、私は非常に驚きます。また、（2）が偽である場合、さらに驚きます。
べき乗述語が何を意味するのかを完全には理解していないのではないかと思います（つまり、私の非公式な定義 $Fabc$ が正しくないか、「乗算述語を自由に使用する」ことに関して、私が気付いていない詳細がいくつかあります。
回答
あなたの主張 $(1), (2)$、および $(3)$それぞれ正しいです。請求$(4)$ただし、正しくありません。確かに、乗算が定義可能である場合$(\mathbb{N};\max,+)$ その後、理論 $Th(\mathbb{N};\max,+)$ と同じくらい複雑になります $Th(\mathbb{N};+,\times)$。しかし、前者は再帰的ですが、後者は算術的に定義することさえできません。
問題は、加算に関する乗算の「明白な」定義が実際には1次ではないことです。再帰的定義は、1次論理が実行できる先験的なものではありません。十分に豊富な構造では、再帰的定義を一次的に実行する方法を見つけることができます。実際、それは$Th(\mathbb{N};+,\times)$この意味で、ゲーデルの不完全性を可能にしますが、加算だけではこの機能を実現するのに十分な力はありません。重要なのは、加算と乗算の両方がある場合、個々のナチュラルによってナチュラルの有限シーケンスを「コード化」できることです（たとえば、$\beta$関数）など、再帰的な構造については、「段階的な動作」をコーディングするシーケンスについて説明しますが、加算だけでは、個々の数値で数値のペアをコーディングすることもできません。
その最後の文を詳しく説明し、あなたの主張に戻ります $(2)$、これは、1次の方法で加算と乗算を使用してべき乗を定義する方法の概要です。
我々は持っています $a^b=c$ シーケンスとして解釈されたときに長さがであるいくつかの数がある場合 $b$、第1期 $a$、前期 $c$、および $i+1$等しい第3項 $a$ 倍 $i$第3期。
これは、「再帰的プロセス」による定義ではなく、「一度に」の定義であることに注意してください。有限シーケンスを数値でコーディングする詳細を法として、個々の数値を定量化し、基本的なプロパティをチェックするだけです。順序論理で実行できます。一次的な方法で有限シーケンスを個々の数としてコーディングする機能がない-これ$(\mathbb{N};\max,+)$ 欠けている-私たちは通常の非一次定義で立ち往生するでしょう。
- 余談ですが、これが理論上の「検証可能な定義」であることが重要です。 $\mathsf{Q}$、これは完全な理論の小さな断片です $Th(\mathbb{N};+,\times)$、それぞれにそれがあります $a,b,c$ で省略された文 $$\underline{a}^{\underline{b}}=\underline{c}$$ （どこ $\underline{k}$ 自然数を表す数字です $k$）で証明可能 $\mathsf{Q}$ もし $a^b=c$ で反証可能です $\mathsf{Q}$ もし $a^b\not=c$。これは表現可能性と呼ばれ、ゲーデルの証明の重要なアイデアの1つです。実際、すべての再帰関数は表現可能です。