The arithmetical hierarchy classifies statements according to the number of unbounded \(\forall x\) and \(\exists y\) quantifiers, treating adjacent quantifiers of the same type as a single quantifier.

The formula \(\phi(x, y) \leftrightarrow [(x + y) = (y + x)],\) treating \(x\) and \(y\) as constants, contains no quantifiers and would occupy the lowest level of the hierarchy, \(\Delta_0 = \Pi_0 = \Sigma_0.\) (Assuming that the operators \(+\) and \(=\) are themselves considered to be in \(\Delta_0\), or from another perspective, that for any particular \(c\) and \(d\) we can verify whether \(c + d = d + c\) in bounded time.)

Adjoining any number of \(\forall x_1: \forall x_2: ...\) quantifiers to a statement that would be in \(\Sigma_n\) if the \(x_i\) were considered as constants, creates a statement in \(\Pi_{n+1}.\) Thus, the statement \(\forall x: (x + 3) = (3 + x)\) is in \(\Pi_1.\)

Similarly, adjoining \(\exists x_1: \exists x_2: ...\) to a statement in \(\Pi_n\) creates a statement in \(\Sigma_{n+1}.\) Thus, the statement \(\exists y: \forall x: (x + y) = (y + x)\) is in \(\Sigma_2\), while the statement \(\exists y: \exists x: (x + y) = (y + x)\) is in \(\Sigma_1.\)

Statements in both \(\Pi_n\) and \(\Sigma_n\) (e.g. because they have provably equivalent formulations belonging to both classes) are said to lie in \(\Delta_n.\)

Quantifiers that can be bounded by \(\Delta_0\) functions of variables already introduced are ignored by this classification schema: the sentence \(\forall x: \exists y < x: (x + y) = (y + x)\) is said to lie in \(\Pi_1\), not \(\Pi_2\). We can justify this by observing that for any particular \(c,\) the statement \(\forall x < c: \phi(x)\) can be expanded into the non-quantified statement \(\phi(0) \wedge \phi(1) ... \wedge \phi(c)\) and similarly \(\exists x < c: \phi(x)\) expands to \(\phi(0) \vee \phi(1) \vee ...\)

This in turn justifies collapsing adjacent quantifiers of the same type inside the classification schema. Since, e.g., we can uniquely encode every pair (x, y) in a single number \(z = 2^x \cdot 3^y\), to say “there exists a pair (x, y)” or “for every pair (x, y)” it suffices to quantify over z encoding (x, y) with x and y less than z.

We say that \(\Delta_{n+1}\) includes the entire sets \(\Pi_n\) and \(\Sigma_n\), since from a \(\Pi_{n}\) statement we can produce a \(\Pi_{n+1}\) statement just by adding an inner \(\exists\) quantifier and then ignoring it, and we can obtain a \(\Sigma_{n+1}\) statement from a \(\Pi_{n}\) statement by adding an outer \(\forall\) quantifier and ignoring it, etcetera.

This means that the arithmetic hierarchy talks about power sufficient to resolve statements. To say \(\phi \in \Pi_n\) asserts that if you can resolve all \(\Pi_n\) formulas then you can resolve \(\phi\), which might potentially also be doable with less power than \(\Pi_n\), but can definitely not require more power than \(\Pi_n.\)

Consequences for epistemic properties

All and only statements in \(\Sigma_1\) are verifiable by observation. If \(\phi \in \Delta_0\) then the sentence \(\exists x: \phi(x)\) can be positively known by searching for and finding a single example. Conversely, if a statement involves an unbounded universal quantifier, we can never be sure of it through simple observation because we can’t observe the truth for every possible number.

All and only statements in \(\Pi_1\) are falsifiable by observation. If \(\phi\) can be tested in bounded time, then we can falsify the whole statement \(\forall x: \phi(x)\) by presenting some single x of which \(\phi\) is false. Conversely, if a statement involves an unbounded existential quantifier, we can never falsify it directly through a bounded number of observations because there could always be some higher, as-yet untested number that makes the sentence true.

This doesn’t mean we can’t get probabilistic confirmation and disconfirmation of sentences outside \(\Sigma_1\) and \(\Pi_1.\) E.g. for a \(\Pi_2\) statement, “For every x there is a y”, each time we find an example of a y for another x, we might become a little more confident, and if for some x we fail to find a y after long searching, we might become a little less confident in the entire statement.