Editing Arithmetical hierarchy (section)

== Meaning of the notation==

The following meanings can be attached to the notation for the arithmetical hierarchy on formulas.

The subscript <math>n</math> in the symbols <math>\Sigma^0_n</math> and <math>\Pi^0_n</math> indicates the number of alternations of blocks of universal and existential first-order quantifiers that are used in a formula.   Moreover, the outermost block is existential in <math>\Sigma^0_n</math> formulas and universal in <math>\Pi^0_n</math> formulas.

The superscript <math>0</math> in the symbols <math>\Sigma^0_n</math>, <math>\Pi^0_n</math>, and <math>\Delta^0_n</math> indicates the type of the objects being quantified over.  Type 0 objects are natural numbers, and objects of type <math>i+1</math> are functions that map the set of objects of  type <math>i</math> to the natural numbers. Quantification over higher type objects, such as functions from natural numbers to natural numbers, is described by a superscript greater than 0, as in the [[analytical hierarchy]]. The superscript 0 indicates quantifiers over numbers, the superscript 1 would indicate quantification over functions from numbers to numbers (type 1 objects), the superscript 2 would correspond to quantification over functions that take a type 1 object and return a number, and so on.