# Arithmetical hierarchy

The ar­ith­meti­cal hi­er­ar­chy clas­sifies state­ments ac­cord­ing to the num­ber of un­bounded $$\forall x$$ and $$\exists y$$ quan­tifiers, treat­ing ad­ja­cent quan­tifiers of the same type as a sin­gle quan­tifier.

The for­mula $$\phi(x, y) \leftrightarrow [(x + y) = (y + x)],$$ treat­ing $$x$$ and $$y$$ as con­stants, con­tains no quan­tifiers and would oc­cupy the low­est level of the hi­er­ar­chy, $$\Delta_0 = \Pi_0 = \Sigma_0.$$ (As­sum­ing that the op­er­a­tors $$+$$ and $$=$$ are them­selves con­sid­ered to be in $$\Delta_0$$, or from an­other per­spec­tive, that for any par­tic­u­lar $$c$$ and $$d$$ we can ver­ify whether $$c + d = d + c$$ in bounded time.)

Ad­join­ing any num­ber of $$\forall x_1: \forall x_2: ...$$ quan­tifiers to a state­ment that would be in $$\Sigma_n$$ if the $$x_i$$ were con­sid­ered as con­stants, cre­ates a state­ment in $$\Pi_{n+1}.$$ Thus, the state­ment $$\forall x: (x + 3) = (3 + x)$$ is in $$\Pi_1.$$

Similarly, ad­join­ing $$\exists x_1: \exists x_2: ...$$ to a state­ment in $$\Pi_n$$ cre­ates a state­ment in $$\Sigma_{n+1}.$$ Thus, the state­ment $$\exists y: \forall x: (x + y) = (y + x)$$ is in $$\Sigma_2$$, while the state­ment $$\exists y: \exists x: (x + y) = (y + x)$$ is in $$\Sigma_1.$$

State­ments in both $$\Pi_n$$ and $$\Sigma_n$$ (e.g. be­cause they have prov­ably equiv­a­lent for­mu­la­tions be­long­ing to both classes) are said to lie in $$\Delta_n.$$

Quan­tifiers that can be bounded by $$\Delta_0$$ func­tions of vari­ables already in­tro­duced are ig­nored by this clas­sifi­ca­tion schema: the sen­tence $$\forall x: \exists y < x: (x + y) = (y + x)$$ is said to lie in $$\Pi_1$$, not $$\Pi_2$$. We can jus­tify this by ob­serv­ing that for any par­tic­u­lar $$c,$$ the state­ment $$\forall x < c: \phi(x)$$ can be ex­panded into the non-quan­tified state­ment $$\phi(0) \wedge \phi(1) ... \wedge \phi(c)$$ and similarly $$\exists x < c: \phi(x)$$ ex­pands to $$\phi(0) \vee \phi(1) \vee ...$$

This in turn jus­tifies col­laps­ing ad­ja­cent quan­tifiers of the same type in­side the clas­sifi­ca­tion schema. Since, e.g., we can uniquely en­code ev­ery pair (x, y) in a sin­gle num­ber $$z = 2^x \cdot 3^y$$, to say “there ex­ists a pair (x, y)” or “for ev­ery pair (x, y)” it suffices to quan­tify over z en­cod­ing (x, y) with x and y less than z.

We say that $$\Delta_{n+1}$$ in­cludes the en­tire sets $$\Pi_n$$ and $$\Sigma_n$$, since from a $$\Pi_{n}$$ state­ment we can pro­duce a $$\Pi_{n+1}$$ state­ment just by adding an in­ner $$\exists$$ quan­tifier and then ig­nor­ing it, and we can ob­tain a $$\Sigma_{n+1}$$ state­ment from a $$\Pi_{n}$$ state­ment by adding an outer $$\forall$$ quan­tifier and ig­nor­ing it, etcetera.

This means that the ar­ith­metic hi­er­ar­chy talks about power suffi­cient to re­solve state­ments. To say $$\phi \in \Pi_n$$ as­serts that if you can re­solve all $$\Pi_n$$ for­mu­las then you can re­solve $$\phi$$, which might po­ten­tially also be doable with less power than $$\Pi_n$$, but can definitely not re­quire more power than $$\Pi_n.$$

# Con­se­quences for epistemic properties

All and only state­ments in $$\Sigma_1$$ are ver­ifi­able by ob­ser­va­tion. If $$\phi \in \Delta_0$$ then the sen­tence $$\exists x: \phi(x)$$ can be pos­i­tively known by search­ing for and find­ing a sin­gle ex­am­ple. Con­versely, if a state­ment in­volves an un­bounded uni­ver­sal quan­tifier, we can never be sure of it through sim­ple ob­ser­va­tion be­cause we can’t ob­serve the truth for ev­ery pos­si­ble num­ber.

All and only state­ments in $$\Pi_1$$ are falsifi­able by ob­ser­va­tion. If $$\phi$$ can be tested in bounded time, then we can falsify the whole state­ment $$\forall x: \phi(x)$$ by pre­sent­ing some sin­gle x of which $$\phi$$ is false. Con­versely, if a state­ment in­volves an un­bounded ex­is­ten­tial quan­tifier, we can never falsify it di­rectly through a bounded num­ber of ob­ser­va­tions be­cause there could always be some higher, as-yet untested num­ber that makes the sen­tence true.

This doesn’t mean we can’t get prob­a­bil­is­tic con­fir­ma­tion and dis­con­fir­ma­tion of sen­tences out­side $$\Sigma_1$$ and $$\Pi_1.$$ E.g. for a $$\Pi_2$$ state­ment, “For ev­ery x there is a y”, each time we find an ex­am­ple of a y for an­other x, we might be­come a lit­tle more con­fi­dent, and if for some x we fail to find a y af­ter long search­ing, we might be­come a lit­tle less con­fi­dent in the en­tire state­ment.

Children:

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.