The arithmetical hierarchy is a way of stratifying statements by how many "for every number" and "there exists a number" clauses they contain.

Suppose we say "2 + 1 = 1 + 2". Since this is only a statement about three specific numbers, this statement would occupy the lowest level of the arithmetical hierarchy, which we can equivalently call $~$\Delta_0,$~$ $~$\Pi_0,$~$ or $~$\Sigma_0$~$ (the reason for using all three terms will soon become clear).

Next, suppose we say, "For all numbers x: (1 + x) = (x + 1)." This generalizes over *all* numbers - a universal quantifier - and then makes a statement about each particular number x, that (1 + x) = (x + 1), that involves no further quantifiers and can be verified immediately. This statement is said to be in $~$\Pi_1.$~$

Suppose we say, "There exists a y such that $~$y^9 = 9^y.$~$" This is a single existential quantifier. To verify it by sheer brute force, we'd need to start from 0 and then consider successive integers y, checking for each particular y whether it was true that $~$y^9 = 9^y.$~$ Since the statement has a single existential quantifier over y, surrounding a statement that for any particular y is in $~$\Delta_0,$~$ it is said to be in $~$\Sigma_1.$~$

Suppose we say, "For every number x, there exists a prime number y that is greater than x." For any particular $~$c$~$ the statement "There is a prime number x that is greater than $~$c$~$" lies in $~$\Sigma_1.$~$ Universally quantifying over all $~$c,$~$ outside of the $~$\Sigma_1$~$ statement about any particular $~$c,$~$ creates a statement in $~$\Pi_2.$~$

Similarly, the statement "There exists a number x such that, for every number y, $~$(x + y) > 10^9$~$ would be in $~$\Sigma_2,$~$ since it adjoins a "there exists a number x…" to a statement that lies in $~$\Pi_1$~$ for any particular $~$x.$~$

Generalizing, putting a "There exists an x…" quantifier outside a $~$\Pi_n$~$ statement creates a $~$\Sigma_{n+1}$~$ statement, and putting a "For all y" quantifier outside a $~$\Sigma_n$~$ statement about y creates a $~$\Pi_{n+1}$~$ statement.

If there are equivalent ways of formulating a sentence such that it can be seen to occupy both $~$\Sigma_n$~$ and $~$\Pi_n$~$, we say that it belongs to $~$\Delta_n.$~$

# Consequences for epistemic reasoning

Statements in $~$\Sigma_1$~$ are *verifiable*. Taking "There exists $~$y$~$ such that $~$y^9 = 9^y$~$" as the example, soon as we find any one particular $~$y$~$ such that $~$y^9 = 9^y,$~$ we can verify the central formula $~$y^9 = 9^y$~$ for that particular $~$y$~$ immediately, and then we're done.

Statements in $~$\Pi_1$~$ are *falsifiable*. We can decisively demonstrate them to be wrong by finding a particular example where the core statement is false.

Sentences in $~$\Delta_1$~$ are those which are both falsifiable and verifiable in finite time.

$~$\Pi_2$~$ and $~$\Sigma_2$~$ statements are not definitely verifiable or falsifiable by brute force. E.g. for a $~$\Pi_2$~$ statement, "For every x there is a y", even after we've found a y for many particular x, we haven't tested all the x; and even if we've searched some particular x and not yet found any y, we haven't yet searched all possible y. But statements in this class can still be probabilistically supported or countersupported by examples; 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 a long time searching, we might become a little less confident.

# Subtleties

## Bounded quantifiers don't count

The statement, "For every number $~$x,$~$ there exists a prime number $~$y$~$ smaller than $~$x^x$~$" is said to lie in $~$\Pi_1$~$, not $~$\Pi_2$~$. Since the existence statement is bounded by $~$x^x$~$, a function which can itself be computed in bounded time, in principle we could just search through every possible $~$y$~$ that is less than $~$x^x$~$ and test it in bounded time. For any particular $~$x,$~$ such as $~$x = 2,$~$ we could indeed replace the statement "There exists a prime number $~$y$~$ less than $~$2^2$~$" with the statement "Either 0 is a prime number, or 1 is a prime number, or 2 is a prime number, or 3 is a prime number" which contains no quantifiers at all. Thus, in general within the arithmetical hierarchy, bounded quantifiers don't count.

We similarly observe that the statement "For every number $~$x,$~$ there exists a prime number $~$y$~$ smaller than $~$x^x$~$" is *falsifiable* - we could falsify it by exhibiting some particular constant $~$c,$~$ testing all the numbers smaller than $~$c^c,$~$ and failing to find any primes. (As would in fact be the case if we tested $~$c=1.$~$)

## Similar adjacent quantifiers can be collapsed into a single quantifier

Since bounded quantifiers don't count, it follows more subtly that we can combine adjacent quantifiers of the same type, since there are bounded ways to *encode* multiple numbers in a single number. For example, the numbers x and y can be encoded into a single number $~$z = 2^x \cdot 3^y$~$. So if I want to say, "For every nonzero integers x, y, and z, it is not the case that $~$x^3 + y^3 = z^3$~$" I can actually just say, "There's no number $~$w$~$ such that there exist 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 adjacent universal quantifiers over all x, y, and z can be combined. However, if the sentence is "for all x there exists y", there's no way to translate that into a statement about a single number z, so only alike quantifiers can be collapsed in this way.

With these subtleties in hand, we can see, e.g., that Fermat's Last Theorem belongs in $~$\Pi_1,$~$ since FLT says, "For *every* w greater than 2 and x, y, z greater than 0, it's not the case that $~$x^w + y^w = z^w.$~$ This implies that like any other $~$\Pi_1$~$ statement, Fermat's Last Theorem should be falsifiable by brute force but not verifiable by brute force. If a counterexample existed, we could eventually find it by brute force (even if it took longer than the age of the universe) and exhibit that example to decisively disprove FLT; but there's no amount of brute-force verification of particular examples that can prove the larger theorem.

## How implications interact with falsifiability and verifiability

In general, if the implication $~$X \rightarrow Y$~$ holds, then:

- If $~$Y$~$ is falsifiable, $~$X$~$ is falsifiable.
- If $~$X$~$ is verifiable, $~$Y$~$ is verifiable.

The converse implications do not hold.

As an example, consider the $~$\Pi_2$~$ statement "For every prime $~$x$~$, there is a larger prime $~$y$~$". Ignoring the existence of proofs, this statement is unfalsifiable by direct observation. The falsifiable $~$\Pi_1$~$ statement, "For every prime $~$x$~$, there is a larger prime $~$y = f(x) = 4x+1$~$ would if true imply the $~$\Pi_2$~$ statement." But this doesn't make the $~$\Pi_2$~$ statement falsifiable. Even if the $~$\Pi_1$~$ assertion about the primeness of $~$4x+1$~$ in particular is false, the $~$\Pi_2$~$ statement can still be true (as is indeed the case). [comment: Patrick, is there a particular reason we want this knowledge to be accessible to people who don't natively read logic? I.e. were you making something else rely on it?]