VC dimension of set of functions
This is a classical result of Assouad (Densité et dimension) about dual VC dimension.
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 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 \\
0 &amp; 1 &amp; 0 \\
0 &amp; 1 &amp; 1 \\
1 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 1 \\
1 &amp; 1 &amp; 0 \\
1 &amp; 1 &amp; 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) &lt; 2^{\mathrm{VC}(A)+1}$.