universal relations exist for each level of the arithmetical hierarchy


Let L{Σn,Δn,Πn} and take any k. Then there is a k+1-ary relationMathworldPlanetmath UL such that U is universalPlanetmathPlanetmath for the k-ary relations in L.

Proof

First we prove the case where L=Δ1, the recursive relations. We use the example of a Gödel numbering.

Define T to be a k+2-ary relation such that T(e,x,a) if:

  • e=ϕ

  • a is a deductionMathworldPlanetmathPlanetmath of either ϕ(x) or ¬ϕ(x)

Since deductions are (http://planetmath.org/DeductionsAreDelta1)Δ1, it follows that T is Δ1. Then define U(e,x) to be the least a such that T(e,x,a) and U(e,x)(U(e,x))len(U(e,x))=e. This is again Δ1 since the Δ1 functions are closed underPlanetmathPlanetmath minimization (http://planetmath.org/Delta_1Bootstrapping).

If f is any k-ary Δ1 function then f(x)=U(f,x).

Now take L to be the k-ary relatons in either Σn or Πn. Call the universal relation for k+n-ary Δ1 relations UΔ. Then any ϕL is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to a relation in the form Qy1Qy2Q*ynψ(x,y) where gΔ1, and so U(x)=Qy1Qy2Q*ynUΔ(ψ,x,y). Then U is universal for L.

Finally, if L is the k-ary Δn relations and ϕL then ϕ is equivalent to relations of the form y1y2Qynψ(x,y) and z1z2Qznη(x,z). If the k-ary universal relations for Σn and Πn are UΣ and UΠ respectively then ϕ(x)UΣ(ψ,x)UΠ(η,x).

Title universal relations exist for each level of the arithmetical hierarchy
Canonical name UniversalRelationsExistForEachLevelOfTheArithmeticalHierarchy
Date of creation 2013-03-22 12:58:40
Last modified on 2013-03-22 12:58:40
Owner Henry (455)
Last modified by Henry (455)
Numerical id 5
Author Henry (455)
Entry type Theorem
Classification msc 03B10