arithmetical hierarchy is a proper hierarchy
By definition, we have . In addition, .
This is proved by vacuous quantification. If is equivalent to then is equivalent to and , where is some variable that does not occur free in .
More significant is the proof that all containments are proper. First, let and be universal for -ary relations
. Then is obviously . But suppose . Then , so . Since is universal, ther is some such that , and therefore . This is clearly a contradiction
, so and .
In addition the recursive join of and , defined by
Clearly both and can be recovered from , so it is contained in neither nor . However the definition above has only unbounded quantifiers except for those in and , so