# PAC Learning, VC Dimension, and the Arithmetic Hierarchy

arXiv: https://arxiv.org/abs/1406.1111 · HTML: https://mlsanity.com/paper/1406.1111/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2014.

## Built on by (most cited first, 5 of 5)

- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [On computable learning of continuous features](https://mlsanity.com/paper/2111.14630/) (2021)
- [On statistical learning of graphs](https://mlsanity.com/paper/2507.13054/) (2025)
- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

We compute that the index set of PAC-learnable concept classes is m-complete Sigma03 within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable Pi01 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.