# Arithmetic hierarchy via oracles

My professor gave an introduction to the arithmetic hierarchy via Turing reductions, stating that, for instance, $$\Sigma_2 = \text{r.e.}^\text{r.e.}$$ (namely an $$\text{r.e.}$$ pseudocode with access to an $$\text{r.e.}$$ oracle) or $$\Pi_3 = \text{co-r.e.}^{\text{r.e.}^\text{r.e.}}$$. Later, the equivalent formulation via alternating quantifier descriptions was discussed, but I found it difficult to link the two definitions. I have not been able to find any references describing the connection between the above definitions, with everything I've seen having solely to do with the quantifier-based description. Are there any texts/notes that might cover what I'm looking for?

• Isnt the definition of the hirarchy using oracles to $NP$ and $coNP$? Oct 28 at 6:15
• @nirshahar Not sure what you mean. I'm referring to the arithmetic hierarchy, not the polynomial hierarchy.
– gf.c
Oct 28 at 6:18
• Oh, ok. The arithmetic hirarchy indeed uses oracle calls to $RE$ and $coRE$. For some reason I was sure you meant to talk about the polynomial hirarchy... Oct 28 at 6:21