Arithmetical hierarchy: If you don't read logic

The ar­ith­meti­cal hi­er­ar­chy is a way of strat­ify­ing state­ments by how many “for ev­ery num­ber” and “there ex­ists a num­ber” clauses they con­tain.

Sup­pose we say “2 + 1 = 1 + 2”. Since this is only a state­ment about three spe­cific num­bers, this state­ment would oc­cupy the low­est level of the ar­ith­meti­cal hi­er­ar­chy, which we can equiv­a­lently call \(\Delta_0,\) \(\Pi_0,\) or \(\Sigma_0\) (the rea­son for us­ing all three terms will soon be­come clear).

Next, sup­pose we say, “For all num­bers x: (1 + x) = (x + 1).” This gen­er­al­izes over all num­bers—a uni­ver­sal quan­tifier—and then makes a state­ment about each par­tic­u­lar num­ber x, that (1 + x) = (x + 1), that in­volves no fur­ther quan­tifiers and can be ver­ified im­me­di­ately. This state­ment is said to be in \(\Pi_1.\)

Sup­pose we say, “There ex­ists a y such that \(y^9 = 9^y.\)” This is a sin­gle ex­is­ten­tial quan­tifier. To ver­ify it by sheer brute force, we’d need to start from 0 and then con­sider suc­ces­sive in­te­gers y, check­ing for each par­tic­u­lar y whether it was true that \(y^9 = 9^y.\) Since the state­ment has a sin­gle ex­is­ten­tial quan­tifier over y, sur­round­ing a state­ment that for any par­tic­u­lar y is in \(\Delta_0,\) it is said to be in \(\Sigma_1.\)

Sup­pose we say, “For ev­ery num­ber x, there ex­ists a prime num­ber y that is greater than x.” For any par­tic­u­lar \(c\) the state­ment “There is a prime num­ber x that is greater than \(c\)” lies in \(\Sigma_1.\) Univer­sally quan­tify­ing over all \(c,\) out­side of the \(\Sigma_1\) state­ment about any par­tic­u­lar \(c,\) cre­ates a state­ment in \(\Pi_2.\)

Similarly, the state­ment “There ex­ists a num­ber x such that, for ev­ery num­ber y, \((x + y) > 10^9\) would be in \(\Sigma_2,\) since it ad­joins a “there ex­ists a num­ber x…” to a state­ment that lies in \(\Pi_1\) for any par­tic­u­lar \(x.\)

Gen­er­al­iz­ing, putting a “There ex­ists an x…” quan­tifier out­side a \(\Pi_n\) state­ment cre­ates a \(\Sigma_{n+1}\) state­ment, and putting a “For all y” quan­tifier out­side a \(\Sigma_n\) state­ment about y cre­ates a \(\Pi_{n+1}\) state­ment.

If there are equiv­a­lent ways of for­mu­lat­ing a sen­tence such that it can be seen to oc­cupy both \(\Sigma_n\) and \(\Pi_n\), we say that it be­longs to \(\Delta_n.\)

Con­se­quences for epistemic reasoning

State­ments in \(\Sigma_1\) are ver­ifi­able. Tak­ing “There ex­ists \(y\) such that \(y^9 = 9^y\)” as the ex­am­ple, soon as we find any one par­tic­u­lar \(y\) such that \(y^9 = 9^y,\) we can ver­ify the cen­tral for­mula \(y^9 = 9^y\) for that par­tic­u­lar \(y\) im­me­di­ately, and then we’re done.

State­ments in \(\Pi_1\) are falsifi­able. We can de­ci­sively demon­strate them to be wrong by find­ing a par­tic­u­lar ex­am­ple where the core state­ment is false.

Sen­tences in \(\Delta_1\) are those which are both falsifi­able and ver­ifi­able in finite time.

\(\Pi_2\) and \(\Sigma_2\) state­ments are not definitely ver­ifi­able or falsifi­able by brute force. E.g. for a \(\Pi_2\) state­ment, “For ev­ery x there is a y”, even af­ter we’ve found a y for many par­tic­u­lar x, we haven’t tested all the x; and even if we’ve searched some par­tic­u­lar x and not yet found any y, we haven’t yet searched all pos­si­ble y. But state­ments in this class can still be prob­a­bil­is­ti­cally sup­ported or coun­ter­sup­ported by ex­am­ples; 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 a long time search­ing, we might be­come a lit­tle less con­fi­dent.


Bounded quan­tifiers don’t count

The state­ment, “For ev­ery num­ber \(x,\) there ex­ists a prime num­ber \(y\) smaller than \(x^x\)” is said to lie in \(\Pi_1\), not \(\Pi_2\). Since the ex­is­tence state­ment is bounded by \(x^x\), a func­tion which can it­self be com­puted in bounded time, in prin­ci­ple we could just search through ev­ery pos­si­ble \(y\) that is less than \(x^x\) and test it in bounded time. For any par­tic­u­lar \(x,\) such as \(x = 2,\) we could in­deed re­place the state­ment “There ex­ists a prime num­ber \(y\) less than \(2^2\)” with the state­ment “Either 0 is a prime num­ber, or 1 is a prime num­ber, or 2 is a prime num­ber, or 3 is a prime num­ber” which con­tains no quan­tifiers at all. Thus, in gen­eral within the ar­ith­meti­cal hi­er­ar­chy, bounded quan­tifiers don’t count.

We similarly ob­serve that the state­ment “For ev­ery num­ber \(x,\) there ex­ists a prime num­ber \(y\) smaller than \(x^x\)” is falsifi­able—we could falsify it by ex­hibit­ing some par­tic­u­lar con­stant \(c,\) test­ing all the num­bers smaller than \(c^c,\) and failing to find any primes. (As would in fact be the case if we tested \(c=1.\))

Similar ad­ja­cent quan­tifiers can be col­lapsed into a sin­gle quantifier

Since bounded quan­tifiers don’t count, it fol­lows more sub­tly that we can com­bine ad­ja­cent quan­tifiers of the same type, since there are bounded ways to en­code mul­ti­ple num­bers in a sin­gle num­ber. For ex­am­ple, the num­bers x and y can be en­coded into a sin­gle num­ber \(z = 2^x \cdot 3^y\). So if I want to say, “For ev­ery nonzero in­te­gers x, y, and z, it is not the case that \(x^3 + y^3 = z^3\)” I can ac­tu­ally just say, “There’s no num­ber \(w\) such that there ex­ist nonzero x, y, and z less than w with \(w = 2^x \cdot 3^y \cdot 5^z\) and \(x^3 + y^3 = z^3.\)” Thus, the three ad­ja­cent uni­ver­sal quan­tifiers over all x, y, and z can be com­bined. How­ever, if the sen­tence is “for all x there ex­ists y”, there’s no way to trans­late that into a state­ment about a sin­gle num­ber z, so only al­ike quan­tifiers can be col­lapsed in this way.

With these sub­tleties in hand, we can see, e.g., that Fer­mat’s Last The­o­rem be­longs in \(\Pi_1,\) since FLT says, “For ev­ery w greater than 2 and x, y, z greater than 0, it’s not the case that \(x^w + y^w = z^w.\) This im­plies that like any other \(\Pi_1\) state­ment, Fer­mat’s Last The­o­rem should be falsifi­able by brute force but not ver­ifi­able by brute force. If a coun­terex­am­ple ex­isted, we could even­tu­ally find it by brute force (even if it took longer than the age of the uni­verse) and ex­hibit that ex­am­ple to de­ci­sively dis­prove FLT; but there’s no amount of brute-force ver­ifi­ca­tion of par­tic­u­lar ex­am­ples that can prove the larger the­o­rem.

How im­pli­ca­tions in­ter­act with falsifi­a­bil­ity and verifiability

In gen­eral, if the im­pli­ca­tion \(X \rightarrow Y\) holds, then:

  • If \(Y\) is falsifi­able, \(X\) is falsifi­able.

  • If \(X\) is ver­ifi­able, \(Y\) is ver­ifi­able.

The con­verse im­pli­ca­tions do not hold.

As an ex­am­ple, con­sider the \(\Pi_2\) state­ment “For ev­ery prime \(x\), there is a larger prime \(y\)”. Ig­nor­ing the ex­is­tence of proofs, this state­ment is un­falsifi­able by di­rect ob­ser­va­tion. The falsifi­able \(\Pi_1\) state­ment, “For ev­ery prime \(x\), there is a larger prime \(y = f(x) = 4x+1\) would if true im­ply the \(\Pi_2\) state­ment.” But this doesn’t make the \(\Pi_2\) state­ment falsifi­able. Even if the \(\Pi_1\) as­ser­tion about the prime­ness of \(4x+1\) in par­tic­u­lar is false, the \(\Pi_2\) state­ment can still be true (as is in­deed the case). Pa­trick, is there a par­tic­u­lar rea­son we want this knowl­edge to be ac­cessible to peo­ple who don’t na­tively read logic? I.e. were you mak­ing some­thing else rely on it?


  • Arithmetical hierarchy

    The ar­ith­meti­cal hi­er­ar­chy is a way of clas­sify­ing log­i­cal state­ments by the num­ber of clauses say­ing “for ev­ery ob­ject” and “there ex­ists an ob­ject”.