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.



  • Mathematics

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