Sometimes I see the $\Sigma_n, \Pi_n, \Delta_n$ notation without superscript symbols (for example, in this answer on Mathoverflow; another example is hypermachines ($\Sigma_n$-machines)). But when I read articles on Wikipedia (Descriptive set theory, Arithmetical hierarchy, Hyperarithmetical theory, Analytical hierarchy, Projective hierarchy, Borel hierarchy), I only see the notation with superscript symbols, and I cannot find what is implied by $\Sigma_n, \Pi_n, \Delta_n$. Why is the superscript symbol omitted?

  • $\begingroup$ It may depend on the context, but probably it's the sum, &c, from $n=0$ (or $1$, depending on the convention) to $\infty$. $\endgroup$ – Bernard Aug 31 '19 at 8:50
  • 2
    $\begingroup$ @Bernard: If you mean summation, then no, the $\Sigma$ symbol in my question is not related to this. I added another example. $\endgroup$ – lyrically wicked Aug 31 '19 at 9:13

This notation implies a formula in the Lévy hierarchy.

  • 1
    $\begingroup$ It's also used interchangeably with $\Sigma^0_n$ etc. in many circumstances - e.g. in the notation "I$\Sigma_n$" for the fragment of PA with induction restricted to $\Sigma_n$, or $\Sigma^0_n$, sentences. Really it's a "flexible" notation, which can be applied to whatever complexity hierarchy we're in. $\endgroup$ – Noah Schweber Sep 6 '19 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.