Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / a / i / Solution

The hypothesis class $H$ shatters a set $S$ when it realizes every binary labelling of $S$: for every function $g:S\to \{0,1\}$ there is an $h\in H$ with $h{|}_S=g$. Identifying each classifier with its positive set, this sayswhere $\mathcal{P}(S)$ is the power set. Different labellings may require different members of the hypothesis class.