Arithmetical hierarchy

https://arbital.com/p/arithmetical_hierarchy

by Eliezer Yudkowsky Jan 16 2016 updated Jan 17 2016

The arithmetical hierarchy is a way of classifying logical statements by the number of clauses saying "for every object" and "there exists an object".


[summary: The arithmetical hierarchy classifies logical statements by the number of nested clauses saying "for every object" and "there exists an object". Statements with one "for every object" clause belong in $~$\Pi_1$~$, and statements with one "there exists an object" clause belong in $~$\Sigma_1$~$. Saying "There exists an object x such that (some $~$\Pi_n$~$ statement treating x as a constant)" creates a $~$\Sigma_{n+1}$~$ statement. Similarly, adding a "For every x" clause outside a $~$\Sigma_n$~$ statement creates a $~$\Pi_{n+1}$~$ statement. Statements that can be formulated in both $~$\Pi_n$~$ and $~$\Sigma_n$~$ are said to lie in $~$\Delta_n$~$. Some interesting consequences are that $~$\Pi_1$~$ statements are falsifiable by observation, $~$\Sigma_1$~$ statements are verifiable by observation, and statements strictly in higher classes can only be probabilistically verified by observation.]

[summary(Technical): The arithmetical hierarchy classifies statements by the number of nested, unbounded quantifiers they contain. The classes $~$\Delta_0$~$, $~$\Pi_0$~$, and $~$\Sigma_0$~$ are equivalent and include statements containing only bounded quantifiers, e.g. $~$\forall x < 10: \exists y < x: x + y < 10$~$. If, treating $~$x, y, z…$~$ as constants, a statement $~$\phi(x, y, z…)$~$ would be in $~$\Sigma_n,$~$ then adjoining the unbounded universal quantifiers $~$\forall x: \forall y: \forall z: … \phi(x, y, z…)$~$ creates a $~$\Pi_{n+1}$~$ statement. Similarly, adjoining existential quantifiers to a $~$\Pi_n$~$ statement creates a $~$\Sigma_{n+1}$~$ statement. Statements that can be equivalently formulated to be in both $~$\Pi_n$~$ and $~$\Sigma_n$~$ are said to lie in $~$\Delta_n$~$. Interesting consequences include, e.g., $~$\Pi_1$~$ statements are falsifiable by simple observation, $~$\Sigma_1$~$ statements are verifiable by observation, and statements strictly in higher classes can only be probabilistically verified by observation.]

The arithmetical hierarchy classifies statements according to the number of unbounded $~$\forall x$~$ and $~$\exists y$~$ quantifiers, treating adjacent quantifiers of the same type as a single quantifier.

The formula $~$\phi(x, y) \leftrightarrow [(x + y) = (y + x)],$~$ treating $~$x$~$ and $~$y$~$ as constants, contains no quantifiers and would occupy the lowest level of the hierarchy, $~$\Delta_0 = \Pi_0 = \Sigma_0.$~$ (Assuming that the operators $~$+$~$ and $~$=$~$ are themselves considered to be in $~$\Delta_0$~$, or from another perspective, that for any particular $~$c$~$ and $~$d$~$ we can verify whether $~$c + d = d + c$~$ in bounded time.)

Adjoining any number of $~$\forall x_1: \forall x_2: …$~$ quantifiers to a statement that would be in $~$\Sigma_n$~$ if the $~$x_i$~$ were considered as constants, creates a statement in $~$\Pi_{n+1}.$~$ Thus, the statement $~$\forall x: (x + 3) = (3 + x)$~$ is in $~$\Pi_1.$~$

Similarly, adjoining $~$\exists x_1: \exists x_2: …$~$ to a statement in $~$\Pi_n$~$ creates a statement in $~$\Sigma_{n+1}.$~$ Thus, the statement $~$\exists y: \forall x: (x + y) = (y + x)$~$ is in $~$\Sigma_2$~$, while the statement $~$\exists y: \exists x: (x + y) = (y + x)$~$ is in $~$\Sigma_1.$~$

Statements in both $~$\Pi_n$~$ and $~$\Sigma_n$~$ (e.g. because they have provably equivalent formulations belonging to both classes) are said to lie in $~$\Delta_n.$~$

Quantifiers that can be bounded by $~$\Delta_0$~$ functions of variables already introduced are ignored by this classification schema: the sentence $~$\forall x: \exists y < x: (x + y) = (y + x)$~$ is said to lie in $~$\Pi_1$~$, not $~$\Pi_2$~$. We can justify this by observing that for any particular $~$c,$~$ the statement $~$\forall x < c: \phi(x)$~$ can be expanded into the non-quantified statement $~$\phi(0) \wedge \phi(1) … \wedge \phi(c)$~$ and similarly $~$\exists x < c: \phi(x)$~$ expands to $~$\phi(0) \vee \phi(1) \vee …$~$

This in turn justifies collapsing adjacent quantifiers of the same type inside the classification schema. Since, e.g., we can uniquely encode every pair (x, y) in a single number $~$z = 2^x \cdot 3^y$~$, to say "there exists a pair (x, y)" or "for every pair (x, y)" it suffices to quantify over z encoding (x, y) with x and y less than z.

We say that $~$\Delta_{n+1}$~$ includes the entire sets $~$\Pi_n$~$ and $~$\Sigma_n$~$, since from a $~$\Pi_{n}$~$ statement we can produce a $~$\Pi_{n+1}$~$ statement just by adding an inner $~$\exists$~$ quantifier and then ignoring it, and we can obtain a $~$\Sigma_{n+1}$~$ statement from a $~$\Pi_{n}$~$ statement by adding an outer $~$\forall$~$ quantifier and ignoring it, etcetera.

This means that the arithmetic hierarchy talks about power sufficient to resolve statements. To say $~$\phi \in \Pi_n$~$ asserts that if you can resolve all $~$\Pi_n$~$ formulas then you can resolve $~$\phi$~$, which might potentially also be doable with less power than $~$\Pi_n$~$, but can definitely not require more power than $~$\Pi_n.$~$

Consequences for epistemic properties

All and only statements in $~$\Sigma_1$~$ are verifiable by observation. If $~$\phi \in \Delta_0$~$ then the sentence $~$\exists x: \phi(x)$~$ can be positively known by searching for and finding a single example. Conversely, if a statement involves an unbounded universal quantifier, we can never be sure of it through simple observation because we can't observe the truth for every possible number.

All and only statements in $~$\Pi_1$~$ are falsifiable by observation. If $~$\phi$~$ can be tested in bounded time, then we can falsify the whole statement $~$\forall x: \phi(x)$~$ by presenting some single x of which $~$\phi$~$ is false. Conversely, if a statement involves an unbounded existential quantifier, we can never falsify it directly through a bounded number of observations because there could always be some higher, as-yet untested number that makes the sentence true.

This doesn't mean we can't get probabilistic confirmation and disconfirmation of sentences outside $~$\Sigma_1$~$ and $~$\Pi_1.$~$ E.g. for a $~$\Pi_2$~$ statement, "For every x there is a y", 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 long searching, we might become a little less confident in the entire statement.