Skip to main content
fixed grammar
Source Link
Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39

Actually, for the case $\mathbb A$=$\mathbb H$$Y$$P_{\mathfrak M}$ (which seems, if I am understanding your question correctly, what you are referring to), since $\mathbb H$$F_{\mathfrak M}$$\subseteq$$\mathbb H$$Y$$P_{\mathfrak M}$, the generalization of primitive recursive function you get (rather than want, possibly) isare the primitive computable functions of Moschovakis which are defined in his papers "Abstract First-Order Computability, I" and "Abstract First-Order computability, II". In fact, Thm. 2.6 in Chapter II of Barwise's book states that the $\Sigma_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are semi-search computable on $\mathfrak M$ and the $\Delta_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are the search-computable relations on $\mathfrak M$ (the search-computable relations being Moschovakis' generalization of the general recursive functions on $\mathfrak N$=(N,+,$\cdot$)) so what you seem to require, that is, that there exists a special class of "provably total" $\Sigma_1$ functions on $\mathbb A$ which reduces to the class of primitive recursive functions when $\mathbb A$=$\mathbb H$$F_{\mathfrak M}$ does not exist. That is why I asked those particular questions in my comment to you. If you believe my observation is incorrect, please be so kind as to show me how the class of functions you are interested in can exist.

Actually, for the case $\mathbb A$=$\mathbb H$$Y$$P_{\mathfrak M}$ (which seems, if I am understanding your question correctly, what you are referring to), since $\mathbb H$$F_{\mathfrak M}$$\subseteq$$\mathbb H$$Y$$P_{\mathfrak M}$, the generalization of primitive recursive function you get (rather than want, possibly) is the primitive computable functions of Moschovakis which are defined in his papers "Abstract First-Order Computability, I" and "Abstract First-Order computability, II". In fact, Thm. 2.6 in Chapter II of Barwise's book states that the $\Sigma_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are semi-search computable on $\mathfrak M$ and the $\Delta_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are the search-computable relations on $\mathfrak M$ (the search-computable relations being Moschovakis' generalization of the general recursive functions on $\mathfrak N$=(N,+,$\cdot$)) so what you seem to require, that is, that there exists a special class of "provably total" $\Sigma_1$ functions on $\mathbb A$ which reduces to the class of primitive recursive functions when $\mathbb A$=$\mathbb H$$F_{\mathfrak M}$ does not exist. That is why I asked those particular questions in my comment to you. If you believe my observation is incorrect, please be so kind as to show me how the class of functions you are interested in can exist.

Actually, for the case $\mathbb A$=$\mathbb H$$Y$$P_{\mathfrak M}$ (which seems, if I am understanding your question correctly, what you are referring to), since $\mathbb H$$F_{\mathfrak M}$$\subseteq$$\mathbb H$$Y$$P_{\mathfrak M}$, the generalization of primitive recursive function you get (rather than want, possibly) are the primitive computable functions of Moschovakis which are defined in his papers "Abstract First-Order Computability, I" and "Abstract First-Order computability, II". In fact, Thm. 2.6 in Chapter II of Barwise's book states that the $\Sigma_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are semi-search computable on $\mathfrak M$ and the $\Delta_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are the search-computable relations on $\mathfrak M$ (the search-computable relations being Moschovakis' generalization of the general recursive functions on $\mathfrak N$=(N,+,$\cdot$)) so what you seem to require, that is, that there exists a special class of "provably total" $\Sigma_1$ functions on $\mathbb A$ which reduces to the class of primitive recursive functions when $\mathbb A$=$\mathbb H$$F_{\mathfrak M}$ does not exist. That is why I asked those particular questions in my comment to you. If you believe my observation is incorrect, please be so kind as to show me how the class of functions you are interested in can exist.

Source Link
Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39

Actually, for the case $\mathbb A$=$\mathbb H$$Y$$P_{\mathfrak M}$ (which seems, if I am understanding your question correctly, what you are referring to), since $\mathbb H$$F_{\mathfrak M}$$\subseteq$$\mathbb H$$Y$$P_{\mathfrak M}$, the generalization of primitive recursive function you get (rather than want, possibly) is the primitive computable functions of Moschovakis which are defined in his papers "Abstract First-Order Computability, I" and "Abstract First-Order computability, II". In fact, Thm. 2.6 in Chapter II of Barwise's book states that the $\Sigma_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are semi-search computable on $\mathfrak M$ and the $\Delta_1$ relations on $\mathbb H$$F_{\mathfrak M}$ are the search-computable relations on $\mathfrak M$ (the search-computable relations being Moschovakis' generalization of the general recursive functions on $\mathfrak N$=(N,+,$\cdot$)) so what you seem to require, that is, that there exists a special class of "provably total" $\Sigma_1$ functions on $\mathbb A$ which reduces to the class of primitive recursive functions when $\mathbb A$=$\mathbb H$$F_{\mathfrak M}$ does not exist. That is why I asked those particular questions in my comment to you. If you believe my observation is incorrect, please be so kind as to show me how the class of functions you are interested in can exist.