v0.3      

Log In

 
We have recently moved to a new authentication service, Okta. If you are having trouble logging in, please send a Hangouts message to alexei.andreev@gmail.com.
This page's content is still being worked on.
arrow_downward
Mathematics domain
Arithmetical hierarchy

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

The formula ϕ(x,y)[(x+y)=(y+x)], treating x and y as constants, contains no quantifiers and would occupy the lowest level of the hierarchy, Δ0=Π0=Σ0. (Assuming that the operators + and = are themselves considered to be in Δ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 x1:x2:... quantifiers to a statement that would be in Σn if the xi were considered as constants, creates a statement in Πn+1. Thus, the statement x:(x+3)=(3+x) is in Π1.

Similarly, adjoining x1:x2:... to a statement in Πn creates a statement in Σn+1. Thus, the statement y:x:(x+y)=(y+x) is in Σ2, while the statement y:x:(x+y)=(y+x) is in Σ1.

Statements in both Πn and Σn (e.g. because they have provably equivalent formulations belonging to both classes) are said to lie in Δn.

Quantifiers that can be bounded by Δ0 functions of variables already introduced are ignored by this classification schema: the sentence x:y<x:(x+y)=(y+x) is said to lie in Π1, not Π2. We can justify this by observing that for any particular c, the statement x<c:ϕ(x) can be expanded into the non-quantified statement ϕ(0)ϕ(1)...ϕ(c) and similarly x<c:ϕ(x) expands to ϕ(0)ϕ(1)...

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=2x3y, 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 Δn+1 includes the entire sets Πn and Σn, since from a Πn statement we can produce a Πn+1 statement just by adding an inner quantifier and then ignoring it, and we can obtain a Σn+1 statement from a Πn 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 ϕΠn asserts that if you can resolve all Πn formulas then you can resolve ϕ, which might potentially also be doable with less power than Πn, but can definitely not require more power than Πn.

Consequences for epistemic properties

All and only statements in Σ1 are verifiable by observation. If ϕΔ0 then the sentence x:ϕ(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 Π1 are falsifiable by observation. If ϕ can be tested in bounded time, then we can falsify the whole statement x:ϕ(x) 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 Σ1 and Π1. E.g. for a Π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.

Parents: Mathematics
Children: one page
Tags: C-Class

Help to improve this page

Anyone can help with improving Arbital's content. This page's quality is C-Class , which means it will benefit the most from polish and editing.

This page has the following issues: Needs links