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 $Π_{0},$ or $Σ_{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 $Π_{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 $Δ_{0},$ it is said to be in $Σ_{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 $Σ_{1} .$ Universally quantifying over all $c,$ outside of the $Σ_{1}$ statement about any particular $c,$ creates a statement in $Π_{2} .$

Similarly, the statement "There exists a number x such that, for every number y, $(x + y) > 10^{9}$ would be in $Σ_{2},$ since it adjoins a "there exists a number x..." to a statement that lies in $Π_{1}$ for any particular $x .$

Generalizing, putting a "There exists an x..." quantifier outside a $Π_{n}$ statement creates a $Σ_{n + 1}$ statement, and putting a "For all y" quantifier outside a $Σ_{n}$ statement about y creates a $Π_{n + 1}$ statement.

If there are equivalent ways of formulating a sentence such that it can be seen to occupy both $Σ_{n}$ and $Π_{n}$ , we say that it belongs to $Δ_{n} .$

Consequences for epistemic reasoning

Statements in $Σ_{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 $Π_{1}$ are falsifiable. We can decisively demonstrate them to be wrong by finding a particular example where the core statement is false.

Sentences in $Δ_{1}$ are those which are both falsifiable and verifiable in finite time.

$Π_{2}$ and $Σ_{2}$ statements are not definitely verifiable or falsifiable by brute force. E.g. for a $Π_{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 $Π_{1}$ , not $Π_{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 $Π_{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 $Π_{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 \to 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 $Π_{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 $Π_{1}$ statement, "For every prime $x$ , there is a larger prime $y = f (x) = 4 x + 1$ would if true imply the $Π_{2}$ statement." But this doesn't make the $Π_{2}$ statement falsifiable. Even if the $Π_{1}$ assertion about the primeness of $4 x + 1$ in particular is false, the $Π_{2}$ statement can still be true (as is indeed the case).

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?

Posts

Wikitag Contributions

Comments