MathOverflow Asked by Mohsen Shahriari on November 9, 2021
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.
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP