PAC Learning, VC Dimension, and the Arithmetic Hierarchy

We compute that the index set of PAC-learnable concept classes is $m$-complete ${\mathrm{\Sigma }}_3^0$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable ${\mathrm{\Pi }}_1^0$ 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.