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 $\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.

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 $Q y_1 Q^\prime y_2 \cdots Q^* y_n \psi(\vec{x},\vec{y})$ where $g\in\Delta_1$ and so $U(\vec{x})=Q y_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 Q y_n \psi(\vec{x},\vec{y})$ and $\forall z_1\exists z_2\cdots Q z_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})$