Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm reading van der Vaart's "Asymptotic statistics" and on page 275 the author introduces the concepts of Vapnik-Červonenkis (VC) classes of sets and functions and states a proposition which I can't prove. I'll write the definitions:

A collection $\mathcal{C}$ of subsets of the set $\mathcal{X}$ is said to pick out a certain subset $A$ of the finite set $\{x_1,\ldots,x_n\}\subset\mathcal{X}$ if it can be written as $A=\{x_1,\ldots,x_n\}\cap C$ for some $C\in\mathcal{C}$.

The collection $\mathcal{C}$ is said to shatter $\{x_1,\ldots,x_n\}$ if $\mathcal{C}$ picks out each of its $2^n$ subsets.

The VC index $V(\mathcal{C})$ of $\mathcal{C}$ is the smallest $n$ for which no set of size $n$ is shattered by $\mathcal{C}$. A collection of sets is called a VC class if its VC index is finite.

A collection of functions $\mathcal{F}:=\{f:\mathcal{X}\to\mathbb{R}\}$ is said to be a VC class of functions if the collection of all subgraphs $\{(x,t):f(x)<t\}$, if $f$ ranges over $\mathcal{F}$, forms a VC class of sets in $\mathcal{X}\times\mathbb{R}$.

Then goes a proposition: A collection of sets $C$ is a VC class of sets if and only if the collection of corresponding indicator functions $1_C$ is a VC class of functions.

It is said to be not difficult to see but I got stuck trying to prove it. Say $V(\mathcal{C})=n$. For $C\in\mathcal{C}$ denote $I_C:=\{(x,t)\subset\mathcal{X}\times\mathbb{R}:1_C(x)<t\}$ and $\mathcal{C}':=\{I_C:C\in\mathcal{C}\}$. My guess is that $V(\mathcal{C}')$ should also be $n$.

share|cite|improve this question
up vote 0 down vote accepted

I think I figured it out. Indeed, $V(\mathcal{C}')\leq n$. To see this let $$\widetilde{V}:=\{(x_1,t_1),\ldots,(x_n,t_n)\}\subset X\times\mathbb{R}.$$ Suppose there exists an $i\in\{1,\ldots,n\}$ such that $t_i>1$. Then $(x_i,t_i)\notin I_C$ for all $C\in\mathcal{C}$, thus $\mathcal{C}'$ doesn't pick out $\{(x_i,t_i)\}$ and therefore does not shatter $\widetilde{V}$. If there exists an $i\in\{1,\ldots,n\}$ such that $t_i\leq 0$ then $(x_i,t_i)\in I_C$ for all $C\in\mathcal{C}$. But in this case setting $j=\{1,\ldots,n\}\backslash\{i\}$ results in $\{(x_j,t_j)\}\neq \widetilde{V}\cap I_C$ for all $C\in\mathcal{C}$. Therefore, $\mathcal{C}'$ doesn't pick out $\{(x_j,t_j)\}$ and consequently doesn't shatter $\widetilde{V}$. We will further assume that $t_i\in(0,1]$ for all $i\in\{1,\ldots,n\}$.

Since $V(\mathcal{C})=n$ there exists a subset $A$ of $V:=\{x_1,\ldots,x_n\}$, $A:=\{x_i:i\in T\subset\{1,\ldots,n\}\}$ such that $\mathcal{C}$ doesn't pick out $A$, i.e. $A\neq V\cap C$ for all $C\in\mathcal{C}$. Denote $\widetilde{A}:=\{(x_i,t_i):i\in T\subset\{1,\ldots,n\}\}$. Let $C\in\mathcal{C}$. Then $A\neq V\cap C$ and this means that:

  1. there exists $i\in\{1,\ldots,n\}$ such that $x_i\in A\backslash C$, or
  2. there exists $i\in\{1,\ldots,n\}$ such that $x_i\in C\backslash A$.

In the first case, from $t_i>0$ it follows that $(x_i,t_i)\notin I_C$, therefore $\widetilde{A}\neq \widetilde{V}\cap I_C$. In the second case $(x_i,t_i)\in I_C$, thus again $\widetilde{A}\neq \widetilde{V}\cap I_C$. Since $C$ is arbitrary $\widetilde{A}\neq \widetilde{V}\cap I_C$ for all $C\in\mathcal{C}$, i.e. $\mathcal{C}'$ doesn't pick out $\widetilde{A}$ and consequently doesn't shatter $\widetilde{V}$.

Suppose $V(\mathcal{C}')=n$. We will show that $V(\mathcal{C})\leq n$. Let $\{x_1,\ldots,x_n\}\subset X$. Denote $a:=1/2$. By $V(\mathcal{C}')=n$, the set $\{(x_1,a),\ldots,(x_n,a)\}$ has a subset $\{(x_i,a):i\in T\}$, $T\subset\{1,\ldots,n\}$, such that \begin{align*} \{(x_i,a):i\in T\}\neq \{(x_1,a),\ldots,(x_n,a)\}\cap I_C,\ \forall C\in\mathcal{C}. \end{align*} Let $C\in\mathcal{C}$. Then

  1. there exists $i\in T$ such that $(x_i,a)\in \{(x_i,a):i\in T\}\backslash I_C$, or
  2. there exists $i\in\{1,\ldots,n\}\backslash T$ such that $(x_i,a)\in I_C$.

In the first case $(x_i,a)\notin I_C$, which can only be true when $x_i\notin C$, therefore $\{x_i:i\in T\}\neq \{x_1,\ldots,x_n\}\cap C$. In the second case, from $(x_i,a)\in I_C$ it follows that $x_i\in C$, however, by the choice of $i$, $x_i\notin\{x_i:i\in T\}$, therefore $\{x_i:i\in T\}\neq \{x_1,\ldots,x_n\}\cap C$. Since $C$ is arbitrary, $\{x_i:i\in T\}\neq \{x_1,\ldots,x_n\}\cap C$ for all $C\in\mathcal{C}$, i.e. $\mathcal{C}$ doesn't pick out $\{x_i:i\in T\}$ and consequently doesn't shatter $\{x_1,\ldots,x_n\}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.