universal relations exist for each level of the arithmetical hierarchy

Let $L\in \{{\mathrm{\Sigma }}_n,{\mathrm{\Delta }}_n,{\mathrm{\Pi }}_n\}$ and take any $k\in \mathbb{N}$. Then there is a $k+1$-ary relation $U\in L$ such that $U$ is universal for the $k$-ary relations in $L$.

Proof

First we prove the case where $L={\mathrm{\Delta }}_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,\overrightarrow{x},a)$ if:

• $e=\mathrm{⌜}\varphi \mathrm{⌝}$

• $a$ is a deduction of either $\varphi (\overrightarrow{x})$ or $\mathrm{\neg }\varphi (\overrightarrow{x})$

Since deductions are (http://planetmath.org/DeductionsAreDelta1)${\mathrm{\Delta }}_1$, it follows that $T$ is ${\mathrm{\Delta }}_1$. Then define $U^{\prime }(e,\overrightarrow{x})$ to be the least $a$ such that $T(e,\overrightarrow{x},a)$ and $U(e,\overrightarrow{x})\leftrightarrow {(U^{\prime }(e,\overrightarrow{x}))}_{\mathrm{len}(U^{\prime }(e,\overrightarrow{x}))}=e$. This is again ${\mathrm{\Delta }}_1$ since the ${\mathrm{\Delta }}_1$ functions are closed under minimization (http://planetmath.org/Delta_1Bootstrapping).

If $f$ is any $k-ary$ ${\mathrm{\Delta }}_1$ function then $f(\overrightarrow{x})=U(\mathrm{⌜}f\mathrm{⌝},\overrightarrow{x})$.

Now take $L$ to be the $k$-ary relatons in either ${\mathrm{\Sigma }}_n$ or ${\mathrm{\Pi }}_n$. Call the universal relation for $k+n$-ary ${\mathrm{\Delta }}_1$ relations $U_{\mathrm{\Delta }}$. Then any $\varphi \in L$ is equivalent to a relation in the form $Q{y}_1{Q}^{\prime }{y}_2\mathrm{\cdots }{Q}^{*}{y}_n\psi (\overrightarrow{x},\overrightarrow{y})$ where $g\in {\mathrm{\Delta }}_1$, and so $U(\overrightarrow{x})=Q{y}_1{Q}^{\prime }{y}_2\mathrm{\cdots }{Q}^{*}{y}_n{U}_{\mathrm{\Delta }}(\mathrm{⌜}\psi \mathrm{⌝},\overrightarrow{x},\overrightarrow{y})$. Then $U$ is universal for $L$.

Finally, if $L$ is the $k$-ary ${\mathrm{\Delta }}_n$ relations and $\varphi \in L$ then $\varphi$ is equivalent to relations of the form $\exists y_1\forall y_2\mathrm{\cdots }Q{y}_n\psi (\overrightarrow{x},\overrightarrow{y})$ and $\forall z_1\exists z_2\mathrm{\cdots }Q{z}_n\eta (\overrightarrow{x},\overrightarrow{z})$. If the $k$-ary universal relations for ${\mathrm{\Sigma }}_n$ and ${\mathrm{\Pi }}_n$ are $U_{\mathrm{\Sigma }}$ and $U_{\mathrm{\Pi }}$ respectively then $\varphi (\overrightarrow{x})\leftrightarrow U_{\mathrm{\Sigma }}(\mathrm{⌜}\psi \mathrm{⌝},\overrightarrow{x})\wedge U_{\mathrm{\Pi }}(\mathrm{⌜}\eta \mathrm{⌝},\overrightarrow{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