✳flâneur — a map of the web's best reading

Arithmetical hierarchy — LessWrong

lesswrong.com · 1,350 words · saved by 1 readers

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=2x⋅3y, 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 ∀ quantifi

x Arithmetical hierarchy — LessWrong Main 5 If you don't read logic 2 Arithmetical hierarchy: If you don't read logic Edited by Eliezer Yudkowsky , et al. last updated 4th Apr 2016 Requires: Ability to read algebra 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 , Π 0 , or Σ 0 (the reason for using a

Explore this link on the map →

related reading