universal relations exist for each level of the arithmetical hierarchy
Let and take any . Then there is a -ary relation such that is universal
for the -ary relations in .
Proof
First we prove the case where , the recursive relations. We use the example of a Gödel numbering.
Define to be a -ary relation such that if:
- •
- •
is a deduction
of either or
Since deductions are (http://planetmath.org/DeductionsAreDelta1), it follows that is . Then define to be the least such that and . This is again since the functions are closed under minimization (http://planetmath.org/Delta_1Bootstrapping).
If is any function then .
Now take to be the -ary relatons in either or . Call the universal relation for -ary relations . Then any is equivalent to a relation in the form where , and so . Then is universal for .
Finally, if is the -ary relations and then is equivalent to relations of the form and . If the -ary universal relations for and are and respectively then .