Index sets and presentations of complexity classes

This paper draws close connections between the ease of presenting a given complexity class script C sign and the position of the index sets I_{script C sign} = {i : L(M_i) ∈ script C sign} and J_{script C sign} = {i : M_i is total ∧L(M_i) ∉ script C sign} in the arithmetical hierarchy. For virtually all classes script C sign studied in the literature, the lowest levels attainable are I_{script C sign} ∈ ∑⁰₃ and J_{script C sign} ∈ Π⁰₂; the first holds iff script C sign is Δ⁰₂-presentable, and the second iff script C sign is recursively presentable. A general kind of priority argument is formulated, and it is shown that every property enforcible by it is not recursively presentable. It follows that the classes of P-immune and P-biimmune languages in exponential time are not recursively presentable. It is shown that for all script C sign with I_{script C sign} ∉ ∑⁰₃, "many" members of script C sign do not provably (in true Π₂-arithmetic) belong to script C sign. A class script K sign is exhibited such that I_{script K sign} ∈ ∑⁰₃ is open, and I_{script K sign} ∉ ∑⁰₃ implies that the polynomial hierarchy is infinite.