Learning Theory in the Arithmetic Hierarchy
  We consider the arithmetic complexity of index sets of uniformly computably
enumerable families learnable under different learning criteria. We determine
the exact complexity of these sets for the standard notions of finite learning,
learning in the limit, behaviorally correct learning and anomalous learning in
the limit. In proving the $\Sigma_5^0$-completeness result for behaviorally
correct learning we prove a result of independent interest; if a uniformly
computably enumerable family is not learnable, then for any computable learner
there is a $\Delta_2^0$ enumeration witnessing failure.
