# 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.

# Subtleties

## 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?

Parents:

• 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”.

• Mathematics

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