# VC dimension of set of functions

Let $$\chi$$ be an instance space and $$H \in \{0, 1\}^\chi$$ a class with finite VC-dimension. For each $$x \in X$$ we consider $$z_x\colon H \rightarrow \{0, 1\}$$ s.t. $$z_x(h) = h(x), \forall h \in H$$.

Let $$Z = \{z_x:H\rightarrow\{0,1\}\mid x\in\chi\}$$. Is $$\mathit{VCdim}(Z)<2^{\mathit{VCdim}(H)+1}$$?

The only thing that comes to mind when seeing this is the Sauer lemma, but that's related to the growth function and I don't see how to apply it here. Anyone got any idea on how to approach this?

Let $$A$$ be a binary matrix. The VC dimension of $$A$$ is the maximal size of a set $$S$$ of columns which are shattered, that is, all possible rows appear when we restrict $$A$$ to the columns in $$S$$. The dual VC dimension of $$A$$ is the VC dimension of $$A^T$$, the transpose of $$A$$.
Suppose that $$A^T$$ has VC dimension $$2^{d+1}$$. Then there is a set $$S$$ of $$2^{d+1}$$ rows of $$A$$ such that when we restrict $$A$$ to this set of rows, we see all possible columns. If we number the rows using binary numbers of length $$d+1$$, then in particular we see the following columns: for each $$i$$, there is a column which contains the $$i$$'th bit of the row index. For example, if $$d=1$$ then we see the following columns: $$\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}$$ Therefore the VC dimension of $$A$$ is at least $$d+1$$.
If we take $$d = \mathrm{VC}(A)$$, then we deduce $$\mathrm{VC}(A^T) < 2^{\mathrm{VC}(A)+1}$$.