3.19 VC-dimension of a vector space of real functions. Let F be a nite-dimensional vector space of real functions on Rn, dim(F) = r < 1. Let H be the set of hypotheses:

H = ffx: f(x)  0g: f 2 Fg:

Show that

d, the VC-dimension of H, is nite and that d  r. (Hint: select an arbitrary set of m = r + 1 points and consider linear mapping u: F ! Rm dened by: u

(f) = (f(x1); : : : ; f(xm)).)