The arithmetical hierarchy classifies statements according to the number of unbounded and quantifiers, treating adjacent quantifiers of the same type as a single quantifier.
The formula treating and as constants, contains no quantifiers and would occupy the lowest level of the hierarchy, (Assuming that the operators and are themselves considered to be in , or from another perspective, that for any particular and we can verify whether in bounded time.)
Adjoining any number of quantifiers to a statement that would be in if the were considered as constants, creates a statement in Thus, the statement is in
Similarly, adjoining to a statement in creates a statement in Thus, the statement is in , while the statement is in
Statements in both and (e.g. because they have provably equivalent formulations belonging to both classes) are said to lie in
Quantifiers that can be bounded by functions of variables already introduced are ignored by this classification schema: the sentence is said to lie in , not . We can justify this by observing that for any particular the statement can be expanded into the non-quantified statement and similarly expands to
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 , 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 includes the entire sets and , since from a statement we can produce a statement just by adding an inner quantifier and then ignoring it, and we can obtain a statement from a statement by adding an outer quantifier and ignoring it, etcetera.
This means that the arithmetic hierarchy talks about power sufficient to resolve statements. To say asserts that if you can resolve all formulas then you can resolve , which might potentially also be doable with less power than , but can definitely not require more power than
All and only statements in are verifiable by observation. If then the sentence 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 are falsifiable by observation. If can be tested in bounded time, then we can falsify the whole statement by presenting some single x of which 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 and E.g. for a 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.