universal relations exist for each level of the arithmetical hierarchy
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 .
|Title||universal relations exist for each level of the arithmetical hierarchy|
|Date of creation||2013-03-22 12:58:40|
|Last modified on||2013-03-22 12:58:40|
|Last modified by||Henry (455)|