# About functions primitive recursively definable using a $Sigma _ 1$ oracle

In a discussion with one of my friends about degrees of computability, I was informed about something that was somehow new to me. As I’m not that much familiar with computability theory, I’ve partially forgotten what exactly the statement was. I’m trying to recover the exact statement, using the part I can recall, and I’ll try to formulate the question in the context of first order arithmetic, with which I’m more familiar. The statement was something like this:

Every function primitive recursively definable using a $$Sigma _ 1$$ oracle is $$Sigma _ 2$$.

The "is $$Sigma _ 2$$" part is what I’m the least sure about, and I can’t recall whether it was "is $$Sigma _ 2$$-definable in the language of arithmetic", "provably total using $$Sigma _ 2$$ induction", a combination of them, or even something else. In the other part, if I recall correctly, "primitive recursively definable using a $$Sigma _ 1$$ oracle" means a function in the class defined as follows: add the characteristic function of a recursively enumerable subset of $$mathbb N$$ to the primitive recursive initial functions (zero, successor and projections), and recursively define new functions by composition an primitive recursion, using the previously defined functions. If I again recall correctly, this class is denoted by $$mathrm { PR } ^ { Sigma _ 1 }$$.

To reformulate the question, let $$mathcal L$$ be the language of primitive recursive arithmetic $$mathrm { PRA }$$, in which there is a constant symbol for $$0$$, and a function symbol for every (primitive recursive definition of a) primitive recursive function. Let $$mathcal L ‘$$ extend $$mathcal L$$, adding a new unary function symbol $$f$$ (as the initial function) and recursively adding new function symbols, each corresponding to a definition by either composition or primitive recursion. I’ll denote everything related to the theories in the language $$mathcal L ‘$$ with a prime symbol and those related to $$mathcal L$$ without it. For example $$Sigma _ n$$ will denote the class of $$Sigma _ n$$ formulas in the language $$mathcal L$$, and $$Sigma _ n ‘$$ will denote the class of $$Sigma _ n$$ formulas in the language $$mathcal L ‘$$. $$mathrm { PRA }$$ is the theory in the language $$mathcal L$$ with the usual axioms of first order classical logic with equality, primitive recursive function defining axioms, and $$Delta _ 0$$ induction axiom schema. $$mathrm I Sigma _ n$$ is the theory in the language $$mathcal L$$ extending $$mathrm { PRA }$$ by adding $$Sigma _ n$$ induction axiom schema. $$mathrm { PRA } ‘$$ and $$mathrm I Sigma _ n ‘$$ are the corresponding theories in the language $$mathcal L ‘$$, with the following additional axioms:
$$forall x big( f ( x ) = 0 lor f ( x ) = 1 big) text ,$$
$$forall x big( f ( x ) = 1 leftrightarrow A ( x ) big) text ,$$
where $$A ( x )$$ is in $$Sigma _ 1$$.

I can now make sense of the above struggle asking the following questions:

1. Is there, for every function symbol $$g$$ in $$mathcal L ‘$$, a natural number $$n$$ such that $$g$$ is $$Sigma _ n$$-definable (i.e. is there a $$Sigma _ n$$ formula $$B ( x , y , dots , z )$$ such that $$mathbb N models forall x , y , dots , z big( g ( x , y , dots ) = z leftrightarrow B ( x , y , dots , z ) big)$$)? If yes, how low can this $$n$$ be (can it be, say, equal to $$2$$)?
2. For a $$g$$ in $$mathcal L ‘$$ which is $$Sigma _ n$$-definable by the formula $$B ( x , y , dots , z )$$, is there a natural number $$m$$ such that $$mathrm I Sigma _ m ‘ vdash forall x , y , dots , z big( g ( x , y , dots ) = z leftrightarrow B ( x , y , dots , z ) big)$$? If yes, how low can this $$m$$ be?
3. For a $$g$$ in $$mathcal L ‘$$ which is $$Sigma _ n$$-definable by the formula $$B ( x , y , dots , z )$$, is there a natural number $$m$$ such that $$g$$ is provably total in $$mathrm I Sigma _ m$$? More accurately, can we have
$$mathrm I Sigma _ m vdash forall x , y , dots , exists z B ( x , y , dots , z )$$
and
$$mathrm I Sigma _ m vdash forall x , y , dots , z _ 0 , z _ 1 big( B ( x , y , dots , z _ 0 ) land B ( x , y , dots , z _ 1 ) rightarrow z _ 0 = z _ 1 big) text ?$$
If yes, how low can this $$m$$ be?

I realize that these are separate questions and maybe not suitable to be asked in a single post, but they seem very much related, and I thought maybe they could be answered all together. This thought is mostly driven by the fact that something similar was claimed to be true in the mentioned discussion. I would appreciate any insights about why the above questions can be answered positively/negatively, as well as any source where I can read about them and find proofs. I would also appreciate it if someone could inform me about what the original statement probably was, in case the above questions do not formulate any well-known fact in computability theory, while there is some known fact in line with the vague statement that I started with.

MathOverflow Asked by Mohsen Shahriari on November 9, 2021

## Related Questions

### Example of an intersection complex not concentrated in a single degree

1  Asked on November 29, 2021

### Is every proper regular relative algebraic space curve over a Dedekind domain projective?

1  Asked on November 26, 2021 by lisa-s

### Examples of residually-finite groups

7  Asked on November 26, 2021 by yiftach-barnea

### Reference: Packing under translation is in NP

1  Asked on November 26, 2021 by till

### Representing a continuous time-inhomogeneous Markov chain by a stochastic integral

0  Asked on November 26, 2021

### Convergence of empirical measure to Mc-Kean Vlasov equation for mean-field model with jumps

0  Asked on November 26, 2021 by sid-a

### Values of a pair of determinants

1  Asked on November 26, 2021

### What subsystem of third order arithmetic proves the real numbers are Dedekind complete?

1  Asked on November 26, 2021

### Algebras Morita equivalent with the Weyl Algebra and its smash products with a finite group

1  Asked on November 24, 2021

### Error rate implying regularity

0  Asked on November 24, 2021 by user69642

### Pairing up vertices in a graph

1  Asked on November 24, 2021

### Minimizing an f-divergence and Jeffrey’s Rule

0  Asked on November 24, 2021 by jw7642

### Rational functions with trivial Weil symbols at every point

0  Asked on November 24, 2021 by daniil-rudenko

### Regular singular point of non-linear ODE: $dot{x}(t) + t^{-1}Ax(t) = Q(x(t))$

1  Asked on November 24, 2021

### Inverse problem of Chern Classes

4  Asked on November 22, 2021 by temitope-a

### Reference for graduate-level text or monograph with focus on “the continuum”

5  Asked on November 22, 2021 by ruth-no

### Do Poincaré residue and integrable log connection commute?

0  Asked on November 22, 2021

### Numbers of the form $x^2(x-1) + y^2(y-1) + z^2(z-1)$ with $x,y,zinmathbb Z$

0  Asked on November 22, 2021

### How to solve a differential equation in the form $frac{partial}{partial t}g(x,t)=g(x-Delta,t)+frac{partial^2}{partial x^2} g(x,t)$?

1  Asked on November 22, 2021

### Multidimensional series: an application of quantum field theory

0  Asked on November 22, 2021 by andrea-t