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:

- 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 $)?
- 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?
- 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

0 Answers1 Asked on November 29, 2021

ag algebraic geometry etale cohomology intersection cohomology perverse sheaves reference request

1 Asked on November 26, 2021 by lisa-s

7 Asked on November 26, 2021 by yiftach-barnea

1 Asked on November 26, 2021 by till

algorithms computational complexity computational geometry linear programming reference request

0 Asked on November 26, 2021

limits and convergence markov chains pr probability stochastic processes

0 Asked on November 26, 2021 by sid-a

limits and convergence markov chains pr probability stochastic differential equations stochastic processes

1 Asked on November 26, 2021

1 Asked on November 24, 2021

ag algebraic geometry differential operators ra rings and algebras reference request sg symplectic geometry

0 Asked on November 24, 2021 by user69642

ap analysis of pdes fa functional analysis reference request

0 Asked on November 24, 2021 by jw7642

0 Asked on November 24, 2021 by daniil-rudenko

1 Asked on November 24, 2021

ca classical analysis and odes cv complex variables ds dynamical systems real analysis

4 Asked on November 22, 2021 by temitope-a

5 Asked on November 22, 2021 by ruth-no

infinite games real analysis reference request set theory textbook recommendation

0 Asked on November 22, 2021

ag algebraic geometry complex geometry dg differential geometry hodge theory

0 Asked on November 22, 2021

1 Asked on November 22, 2021

0 Asked on November 22, 2021 by andrea-t

eisenstein series nt number theory quantum field theory sequences and series

Get help from others!

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

Recent Answers

- eric_kernfeld on How to test consistency of responses?
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- kjetil b halvorsen on How to test consistency of responses?
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Philipp on How do i draw a ray in unity

© 2022 AnswerBun.com. All rights reserved.