SOURCE-LINKED INTELLIGENCE

A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

arXiv · AI, language, vision and robotics · article · Aug 31, 2026 · UTC

The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--

Read original source ↗ Open in workspace

recordType

paper

region

Global