原始再帰算術

原始再帰算術( PRA ) は、自然数の量指定子を使用しない形式化です。これはノルウェーの数学者スコーレム (1923) ^{[1]により、}算術の基礎に関する彼の有限主義的概念の形式化として初めて提案され、PRA のすべての推論は有限主義的であることが広く認められています。また、有限主義のすべてが PRA によって取り込まれると信じている人も多くいますが^{[2] 、有限主義は原始再帰を超えて、}ペアノ算術の証明論的順序数であるε ₀ [ ^3]までの再帰形式に拡張できると考える人もいます。PRA の証明論的順序数は ω ^ωで、 ω は最小の超限順序数です。 PRAはスコーレム算術と呼ばれることもありますが、これ^は別の意味もあります。スコーレム算術を参照してください。

PRA言語は、自然数と任意の原始再帰関数を含む算術命題（加算、乗算、べき乗演算を含む）を表現できます。PRAは自然数の定義域を明示的に量化することはできません。PRAは、証明論、特にゲンツェンによる一階算術の無矛盾性証明などの無矛盾性証明における基本的なメタ数学的形式体系としてしばしば用いられます。

言語と公理

PRA の言語は次のもので構成されています。

可算無限個の変数x、y、z、....
命題接続詞;
等号記号=、定数記号 0 、および後続記号S ( 1 を加算することを意味する)。
各プリミティブ再帰関数のシンボル。

PRA の論理公理は次のとおりです。

命題論理のトートロジー;
同値関係としての等式の通常の公理化。

PRAの論理規則は、可能性法と変数置換です。
非論理的な公理は、まず以下のとおりです。

$S(x)\neq 0$ ;
$S(x)=S(y)\to x=y,$

ここでは常にの否定を表すので、たとえばは否定された命題となります。 $x\neq y$ $x=y$ $S(0)=0$

さらに、あらゆる原始再帰関数に対する再帰的定義方程式は、必要に応じて公理として採用することができる。例えば、原始再帰関数の最も一般的な特徴付けは、射影、合成、および原始再帰に関して閉じた0定数および後続関数としての特徴付けである。したがって、n位基底関数gと( n + 2)位反復関数h上の原始再帰によって定義された( n +1)位関数fに対しては、以下の定義方程式が成立する。

$f(0,y_{1},\ldots ,y_{n})=g(y_{1},\ldots ,y_{n})$
$f(S(x),y_{1},\ldots ,y_{n})=h(x,f(x,y_{1},\ldots ,y_{n}),y_{1},\ldots ,y_{n})$

特に：

$x+0=x\$
$x+S(y)=S(x+y)\$
$x\cdot 0=0\$
$x\cdot S(y)=x\cdot y+x\$
... 等々。

PRA は、一階算術の帰納法の公理スキームを(量指定子のない) 帰納法の規則に置き換えます。

とから、任意の述語に対してを推論します。 $\varphi (0)$ $\varphi (x)\to \varphi (S(x))$ $\varphi (y)$ $\varphi .$

第一階算術において、明示的に公理化する必要がある原始再帰関数は加算と乗算のみです。その他の原始再帰述語はすべて、これら2つの原始再帰関数とすべての自然数に対する量化を用いて定義できます。PRAでは量化子がないため、このように原始再帰関数を定義することはできません。

論理のない計算

PRAを論理接続詞を全く持たない形で形式化することも可能です。つまり、PRAの文は2つの項の間の方程式に過ぎません。この設定では、項は0個以上の変数を持つ原始的な再帰関数です。Curry (1941)はこのような体系を初めて提示しました。Curryの体系における帰納法の規則は特異なものでした。その後、Goodstein (1954)によって改良が提示されました。Goodsteinの体系における帰納法の規則は次のとおりです。

{F(0)=G(0)\quad F(S(x))=H(x,F(x))\quad G(S(x))=H(x,G(x)) \over F(x)=G(x)}.

ここで、xは変数、Sは後続演算、F、G、Hは任意の原始再帰関数であり、これらは示されているもの以外のパラメータを持つ可能性があります。グッドスタインの推論体系におけるその他の推論規則は、以下の置換規則のみです。

{F(x)=G(x) \over F(A)=G(A)}\qquad {A=B \over F(A)=F(B)}\qquad {A=B\quad A=C \over B=C}.

ここで、 A、B、Cは任意の項（0個以上の変数を持つ原始再帰関数）です。最後に、上記のスコーレムの体系と同様に、任意の原始再帰関数には対応する定義式を持つ記号が存在します。

このようにして、命題論理を完全に排除することができます。論理演算子は完全に算術的に表現できます。例えば、2つの数値の差の絶対値は、原始的な再帰によって定義できます。

{\begin{aligned}P(0)=0\quad &\quad P(S(x))=x\\x{\dot {-}}0=x\quad &\quad x{\mathrel {\dot {-}}}S(y)=P(x{\mathrel {\dot {-}}}y)\\|x-y|=&(x{\mathrel {\dot {-}}}y)+(y{\mathrel {\dot {-}}}x).\\\end{aligned}}

したがって、方程式x = yとu = v は同値である。したがって、方程式とは、それぞれ方程式x = yとu = vの論理積と論理和を表す。否定はと表すことができる。 $|x-y|=0$ $|x-y|+|u-v|=0$ $|x-y|\cdot |u-v|=0$ $1{\dot {-}}|x-y|=0$

参照

注記

^ van Heijenoort に翻訳で再版 (1967)
^ テイト 1981年。
^ クライゼル 1960.
^ Feferman (1998、p. 4 (個人ウェブサイト版)); しかし、Feferman はこの拡張を「もはや明確に有限なものではない」と呼んでいます。

参考文献

カリー、ハスケル B. (1941). 「再帰的算術の形式化」.アメリカ数学ジャーナル. 63 (2): 263– 282. doi :10.2307/2371522. JSTOR 2371522. MR 0004207.

Goodstein, RL (1954). 「再帰的算術の論理フリー形式化」. Mathematica Scandinavica . 2 : 247–261 . doi : 10.7146/math.scand.a-10412 . MR 0087614.

クライゼル, ゲオルク(1960). 「順序論理と非公式証明概念の特徴づけ」(PDF) .国際数学者会議紀要, 1958.ニューヨーク: ケンブリッジ大学出版局. pp. 289– 299. MR 0124194. 2017年5月10日時点のオリジナル(PDF)からのアーカイブ。

スコレム、ソラルフ(1923)。 "Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich" [無限領域にわたる見かけの変数を使用せずに、再帰的思考モードによって確立された初等算術の基礎] (PDF)。Skrifter Utgit av Videnskapsselskapet I クリスティアニア。私、Matematisk-naturvidenskabelig Klasse (ドイツ語)。6：1～ 38。
- スコーレム、トラルフ (1967) [1923]. 「無限領域にわたる見かけ上の変数を用いることなく、再帰的思考様式によって確立された初等算術の基礎」ジャン・ヴァン・ヘイエノールト編『フレーゲからゲーデルへ』ハーバード大学出版局 pp. 302– 333. MR 0209111. （印刷障害のある利用者もアクセス可能）
テイト, ウィリアム・W. (1981). 「有限主義」. 『哲学ジャーナル』 . 78 (9): 524– 546. doi :10.2307/2026089. JSTOR 2026089.

テイト、ウィリアム・W. (2012年6月). 「原始的再帰算術と算術の基礎におけるその役割：歴史的・哲学的考察」(PDF) .認識論対存在論. pp. 161– 180. doi :10.1007/978-94-007-4435-6_8. 2024年5月24日時点のオリジナル(PDF)からのアーカイブ。

フェファーマン、ソロモン(1998). 「何が何に基づいているのか？数学の証明理論的分析」(PDF) .論理の光の中で. doi :10.1093/oso/9780195080308.003.0010.

追加の読み物

彼、ローズ (1961 年)。「再帰的算術の一貫性と決定不能性について」。数学論理と数学に関する研究。7 ( 7–10 ): 124–135 .土井:10.1002/malq.19610070707。MR 0140413。

[1] van Heijenoort に翻訳で再版 (1967)

[FOOTNOTETait1981-2] テイト 1981年。

[FOOTNOTEKreisel1960-3] クライゼル 1960.

[4] Feferman (1998、p. 4 (個人ウェブサイト版)); しかし、Feferman はこの拡張を「もはや明確に有限なものではない」と呼んでいます。