# universal relations exist for each level of the arithmetical hierarchy

Let $L\in\{\Sigma_{n},\Delta_{n},\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=\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,\vec{x},a)$ if:

• $e=\ulcorner\phi\urcorner$

• $a$ is a deduction of either $\phi(\vec{x})$ or $\neg\phi(\vec{x})$

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

If $f$ is any $k-ary$ $\Delta_{1}$ function then $f(\vec{x})=U(\ulcorner f\urcorner,\vec{x})$.

Now take $L$ to be the $k$-ary relatons in either $\Sigma_{n}$ or $\Pi_{n}$. Call the universal relation for $k+n$-ary $\Delta_{1}$ relations $U_{\Delta}$. Then any $\phi\in L$ is equivalent to a relation in the form $Qy_{1}Q^{\prime}y_{2}\cdots Q^{*}y_{n}\psi(\vec{x},\vec{y})$ where $g\in\Delta_{1}$, and so $U(\vec{x})=Qy_{1}Q^{\prime}y_{2}\cdots Q^{*}y_{n}U_{\Delta}(\ulcorner\psi% \urcorner,\vec{x},\vec{y})$. Then $U$ is universal for $L$.

Finally, if $L$ is the $k$-ary $\Delta_{n}$ relations and $\phi\in L$ then $\phi$ is equivalent to relations of the form $\exists y_{1}\forall y_{2}\cdots Qy_{n}\psi(\vec{x},\vec{y})$ and $\forall z_{1}\exists z_{2}\cdots Qz_{n}\eta(\vec{x},\vec{z})$. If the $k$-ary universal relations for $\Sigma_{n}$ and $\Pi_{n}$ are $U_{\Sigma}$ and $U_{\Pi}$ respectively then $\phi(\vec{x})\leftrightarrow U_{\Sigma}(\ulcorner\psi\urcorner,\vec{x})\wedge U% _{\Pi}(\ulcorner\eta\urcorner,\vec{x})$.

Title universal relations exist for each level of the arithmetical hierarchy UniversalRelationsExistForEachLevelOfTheArithmeticalHierarchy 2013-03-22 12:58:40 2013-03-22 12:58:40 Henry (455) Henry (455) 5 Henry (455) Theorem msc 03B10