PAC Learning, VC Dimension, and the Arithmetic Hierarchy
  We compute that the index set of PAC-learnable concept classes is
$m$-complete $\Sigma^0_3$ within the set of indices for all concept classes of
a reasonable form. All concept classes considered are computable enumerations
of computable $\Pi^0_1$ classes, in a sense made precise here. This family of
concept classes is sufficient to cover all standard examples, and also has the
property that PAC learnability is equivalent to finite VC dimension.
