arithmetical hierarchy is a proper hierarchy

By definition, we have Δn=ΠnΣn. In additionPlanetmathPlanetmath, ΣnΠnΔn+1.

This is proved by vacuous quantification. If R is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to ϕ(n) then R is equivalent to xϕ(n) and xϕ(n), where x is some variable that does not occur free in ϕ.

More significant is the proof that all containments are proper. First, let n1 and U be universalPlanetmathPlanetmath for 2-ary Σn relationsMathworldPlanetmath. Then D(x)U(x,x) is obviously Σn. But suppose DΔn. Then DPin, so ¬DΣn. Since U is universal, ther is some e such that ¬D(x)U(e,x), and therefore ¬D(e)U(e,e)¬U(e,e). This is clearly a contradictionMathworldPlanetmathPlanetmath, so DΣnΔn and ¬DΠnΔn.

In addition the recursive join of D and ¬D, defined by


Clearly both D and ¬D can be recovered from D¬D, so it is contained in neither Σn nor Πn. However the definition above has only unboundedPlanetmathPlanetmath quantifiers except for those in D and ¬D, so D¬D(x)Δn+1ΣnΠn

Title arithmetical hierarchy is a proper hierarchy
Canonical name ArithmeticalHierarchyIsAProperHierarchy
Date of creation 2013-03-22 12:55:14
Last modified on 2013-03-22 12:55:14
Owner Henry (455)
Last modified by Henry (455)
Numerical id 6
Author Henry (455)
Entry type Result
Classification msc 03B10