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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 6, 2016 at 20:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .