おそらく全機能 $\mathsf{Q}$
私は帰納と再帰の関係に興味があったので、（とにかく私の心に）自然な質問は、帰納に訴えることなくどれだけ証明できるか、つまりどの関数が証明可能に再帰的であるかということでした $\mathsf{Q}$（ロビンソン算術）。要約すると、関数$f$ 算術理論ではおそらく再帰的です $T$ ある場合 $\Sigma_1$ 式 $\phi$ の言語で $T$ そのような（i） $f(n)=m$ iff $T \vdash \phi(n, m)$ および（ii） $T \vdash \forall x \exists !y \phi(x, y)$。
さて、関数はおそらく再帰的だと思いました$\mathsf{Q}$再帰関数である場合。私の推論は次のとおりでした。関数は、で表現できる場合は再帰的です$\mathsf{Q}$、および、これはよく知られている結果です（を参照してください）。 https://arxiv.org/pdf/1907.00658.pdf）その表現可能性 $\mathsf{Q}$ の強力な表現可能性に相当します $\mathsf{Q}$ これは、 $\mathsf{Q}$。
しかし、FairtloughとWainer（ "Provably Recursive Functionsの階層"）を正しく理解していれば、の証明可能な再帰関数が $\mathsf{I}\Sigma^0_1$まさに原始再帰関数です。以来$\mathsf{I}\Sigma^0_1$ 拡張します $\mathsf{Q}$、それよりも強い $\mathsf{Q}$、したがって、合計が少ない関数であることを証明することはできません。混乱を増すために、私はネルソンがそれを主張したことを覚えています（しかし、覚えていないかもしれません）$\mathsf{Q}$べき乗が合計であることを証明することはできません。もしそうなら、明らかに$\mathsf{Q}$すべての再帰関数が合計であることを証明することはできません。しかし、繰り返しになりますが、私はネルソンの主張を誤って覚えているかもしれません。
したがって、一方では、すべての再帰関数は確かに合計であるように見えます $\mathsf{Q}$、しかし、一方で、すべての原始再帰関数でさえすべてではないようです $\mathsf{Q}$。明らかに私はどこかで間違っていました。
質問1：だから、何している証明可能合計機能では、$\mathsf{Q}$？
そして、この質問への答えに応じて、私はどちらか一方のさらなる質問があります：
質問A：もし$\mathsf{Q}$すべての再帰関数について、それが合計であることを証明するわけではありません。それでは、表現可能性の間の同等性について私が誤解したことは何ですか。$\mathsf{Q}$ 確かに合計ですか？
質問2B：すべての再帰関数は場合である証明可能合計で$\mathsf{Q}$、それでは私は何について誤解しましたか $\mathsf{I}\Sigma^0_1$？プレイ中の証明可能な合計の異なる定義はありますか？
これを整理するのに助けがあれば大歓迎です。
回答
ここでの問題は、「証明可能な全体性」（Salehiの意味で）と「証明可能な再帰性」という2つの概念の微妙な違いです。前者は再帰性と一致しますが、後者は一致しません。その結果、私の経験では（これは上記の括弧で説明しています）、「おそらく合計」と「おそらく再帰的」の両方が、より狭いクラスの関数を指すために使用されます。
関連する定義は次のとおりです。
機能 $f$である（Salehi-）が証明可能合計 （これらは機能Salehiで説明されている）、いくつかの式があるときに限り$\eta$ そのような：
$T\vdash$ 「それぞれについて $x$ ちょうど1つあります $y$ そのような $\eta(x,y)$。」
それぞれについて $a\in\mathbb{N}$ 我々は持っています $T\vdash\eta(\underline{a},\underline{f(a)})$。
上記が一部に当てはまる場合、関数はおそらく再帰的です （これらは、OPで説明する関数です）。$\Sigma^0_1$ 式 $\eta$。
Salehiが与える議論は、すべての総再帰関数が $\mathsf{Q}$。しかし、それは証明可能な再帰性について同じことを示しておらず、実際、証明可能な再帰性と（本物の）総再帰性は、そのような理論の証明に対して常に対角化できるため、合理的な理論では決して一致しません。
同様に、さまざまな表現可能性の概念を「太字」と「」に分割できることに注意してください。$\Sigma^0_1$"バージョン。ただし、これは実際には何も変更されていません（これを確認することをお勧めします）。
上記の一致のために、Salehiの意味での証明可能な全体性はあまり面白くありません。したがって、最近（少なくとも私の経験では）「確かに合計」は通常「おそらく再帰的」の同義語として使用されます。たとえば、を参照してくださいhttps://projecteuclid.org/euclid.pl/1235421933 または https://www.jstor.org/stable/4617258?seq=1#metadata_info_tab_contents。特に、「$\mathsf{I\Sigma_1}$ 原始再帰関数です」と、証明可能な再帰性について言及しています。
では、証明可能な再帰関数は正確には何ですか？$\mathsf{Q}$？まあ、私は実際にこの質問に対する答えを見つけることができないようです。しかし、これはそれほど驚くべきことではないと思います。$\mathsf{Q}$ 非常に弱いので、これはより強力な算術理論よりも興味深い質問ではありません。
そうは言っても、これが私が知っていることです（簡単にするために、適切ではなく関数を参照します $\Sigma^0_1$数式）。しましょう$\mathfrak{Q}$ のクラスになります $\mathsf{Q}$-おそらく再帰関数。の最も明白なメンバー$\mathfrak{Q}$ は「用語のような関数」であり、それによって私はフォームの関数を意味します $$f(x)=\begin{cases} p_1(x) & \mbox{ if }\varphi_1(x)\mbox{ holds }\\ p_2(x) & \mbox{ if }\varphi_2(x)\mbox{ holds}\\ ...\\ p_n(x) & \mbox{ if }\varphi_n(x)\mbox{ holds}\\ \end{cases}$$ いくつかのシーケンスのために $p_1,..., p_n$ 多項式といくつかのシーケンスの $\varphi_1,...,\varphi_n$ の $\Delta^0_1$ 数式 $\mathsf{Q}$宇宙を分割することを証明します。自明な各用語のような関数は$\mathsf{Q}$-おそらく再帰的。
しかし、これは尽きません $\mathfrak{Q}$：私たちはある程度の弱点を回避することができます $\mathsf{Q}$飼いならされた初期セグメントを見ることによって。基本的に、その数を言う$x$「十分な算術」が以下に当てはまる場合は飼いならされます$x$ （例えば、すべてのために $y,z<x$ 私たちはそれを持っています $y^z$が定義されています-ここで十分な飼いならしの概念を特定することは良い練習です）。飼いならしは$\Delta_1$ プロパティ、および $\mathsf{Q}$飼いならされた数のセットが宇宙の最初のセグメントであることを証明します。したがって、関数を定義できます$g$ 「飼いならされた部分」では、用語のような機能に対して対角線上にあり、常に $0$「野生の部分」について。すべての標準的な自然数は飼いならされているので、実際にはそれがあります$g$ 用語のようではありません。
もちろん、これはこれ以来かなりばかげています $g$で、最終的に等しいtermlike機能へ。では、飛躍しましょう。
ために $T$ 算術の理論には、単なるより多くの機能記号が含まれている可能性があります $+$ そして $\times$ （例えば $\mathsf{PRA}$ または $\mathsf{PA}$ +べき乗のプリミティブ）、次のように言います $T$-おそらく再帰関数 $f(x_1,...,x_n)$ です $T$-すべての用語の特別なiff$t(x_1,..., x_n, y_1,...,y_k)$ 我々は持っています $$T\vdash\forall a_1,...,a_k\exists b\forall c_1>b, ..., c_n>b[f(c_1,...,c_n)\not=t(c_1,...,c_n, a_1,...,a_k)].$$ 基本的に、 $T$-特殊関数は、最終的に各項関数とは明らかに異なる関数です（パラメーターが許可されています）。書く "$\mathfrak{Spec}(T)$「のセットのために $T$-特別な機能。
先に進む前に、いくつかの簡単な観察をさせてください。
「cofinallymanuly」を「coboundlymanuly」に置き換えるとどうなるかを調べることもできますが、これは自然なことではないようです。 $T=\mathsf{PA}$ 関数送信 $x$ に $2^x$ もし $x$ でさえあります $0$ そうでなければ、この後者の定義では特別なものとして数えられますが、私の意見では明らかにそうすべきではありません。
解釈には注意が必要です $\mathfrak{Spec}(T)$：控えめな拡張が可能 $S$ の $T$ と $\mathfrak{Spec}(S)\subsetneq\mathfrak{Spec}(T)$（定義による拡張を検討してください）。だから治療するために$\mathfrak{Spec}(T)$ の強さの尺度として $T$、注意を単一の言語に制限する必要があります-たとえば、 $\{+,\times\}$。しかし、一度それを行うと、$T$ そして $S$ 同じ言語の理論です $T\subseteq S$ 意味する $\mathfrak{Spec}(T)\subseteq\mathfrak{Spec}(S)$。
私の意見では、のような限られた言語の中で $\{+,\times\}$特別な機能の不足は、合理的に一種の弱点と見なすことができます。したがって、これは自然な疑問を提起します。
しますか $\mathfrak{Spec}(\mathsf{Q})=\emptyset$？
私はこの質問に対する肯定的な答えを、その正確な意味として暫定的に解釈します。$\mathsf{Q}$-証明可能な再帰性はかなり些細なことです。しかし、これが実際に当てはまるかどうかはわかりません。面白そうなので聞いてみましたhttps://math.stackexchange.com/questions/3802162/can-all-mathsfq-provably-recursive-functions-be-frequently-termlike。