Exercise in VC-dimensions:

Let G be a vector space of real valued functions of X, with finite dimension d. We then define the set of functions of X in {0,1},F by F={1R+(g):gG}. (a) Prove that VC(F)d. (b) Compute, thanks to that result, that the VC dimensions of S={Ha,b+:aRd,bR}, where Ha,b+is the half-space {xRd:a,x+b0}. (c) Let S={B1(z,r):zRd,rR+}, where for all zRd,rR+,B1(z,r) is the ball B1(z,r)= {xRd:xzr}. Prove that VC(S)d+2. (d) Show that VC(S)=d+1