1
$\begingroup$

A function $f:\mathbb{N}^k\to\mathbb{N}$ is Provably Total in Arithmetical recursively enumerable Theory $T$ if there exists a $\Sigma_1$ formula $\phi({\bf x},y)$ in language of $T$ such that:

  1. $T\vdash \forall {\bf x}\exists!y\phi({\bf x},y)$
  2. $\mathbb{N}\models \forall{\bf x}\phi({\bf x},f({\bf x}))$.

(Suppose $\mathbb{N}\models T$.)

Def. A set $\mathcal{A}\subseteq \mathbb{N}$ is Provably Decidable in Arithmetical recursively enumerable Theory $T$ if $\chi_{\mathcal{A}}$ is provably total in $T$.

Is there any standard name or reference for Provably Decidable sets of Theory $T$?

Thanks.

Improve this question
$\endgroup$
7
  • $\begingroup$ Could you clarify whether you intend to assume that $T$ is computably enumerable? Or that $T$ is true in the standard model? Or that $T$ contains some specific weak theory? $\endgroup$
    – Joel David Hamkins
    Aug 5, 2016 at 17:31
  • $\begingroup$ @JoelDavidHamkins: I edited my post. about your third question, Is there any difference for definition of provably decidable set if for example $I\Delta_0\subseteq T$ ? $\endgroup$
    – Erfan Khaniki
    Aug 5, 2016 at 18:11
  • $\begingroup$ What does "arithmetical" mean here? (Since $T$ is recursively enumerable, it's certainly arithmetical in the computability-theoretic sense . . .) $\endgroup$
    – Noah Schweber
    Aug 6, 2016 at 0:26
  • $\begingroup$ @NoahSchweber:I mean $T$ is in language of arithmetic($\mathcal{L}_T=\{0,S,+,\cdot\}$) $\endgroup$
    – Erfan Khaniki
    Aug 6, 2016 at 0:46
  • 2
    $\begingroup$ For all levels of the arithmetical hierarchy ($\Sigma_n$, $\Pi_n$, $\Delta_n$), a definable set $A$ my be (for example) "$\Sigma_n$ in the standard model of arithetic" or "provabily $\Sigma_n$ in $T$). Obviously the later implies the former (if $T$ is sound) but the converse is not necessarily true. So I think another name for your concept is "provabily (in $T$) $\Delta_1$". $\endgroup$
    – Payam Seraji
    Aug 6, 2016 at 20:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.