# Prove there is a formula $\phi(x,z)$ of VC dimension $\kappa$ and dual VC dimension $2^\kappa$

I first recall some definition since the notation can differ somewhat.

Consider a formula $$\phi(x,z)$$ defining a binary relation $$\{(u,v)\in U\times V|\quad \phi(u,v)\}$$.
$$\phi$$ defines subsets of $$U$$ as $$\phi(U,b)=\{a\in U|\quad \phi(a,b)\}$$.
The corresponding collection of defined subsets is $$\phi(U,b)_{b\in V}\subset\wp(U)$$
Now, we say $$\phi$$ has VC dimension $$\kappa$$ if $$\kappa$$ is the maximum cardinality of $$A\subset U$$ such that $$\phi$$ shatters $$A$$ i.e. $$\phi(A,b)_{b\in V}=\wp(A)$$
The dual dimension is just the dimension of the dual formula $$\phi^*(z,x):=\phi(x,z)$$

Now I am asked to find a formula as in the title.

The only way I know to produce a formula (actually a set-system, in an equivalent fashion) of arbitrary $$\kappa$$ VC dimension is to consider: $$\Phi=U^{\leq\kappa}:=\{A\subset U|\quad |A|\leq\kappa\}\subset\wp(U)$$

Now this is equivalent to the binary relation defined by $$\phi(u,B)\Leftrightarrow u\in B \quad\quad on\ \ U\times\Phi$$

So my try is to prove that $$\phi^*(B,u)$$ has VC dimension $$2^k$$.
To asess that it has dimension $$\geq2^\kappa$$ I would try by proving that since there must be $$A\subset U\ \ |A|=\kappa$$ shattered by $$\phi$$ then $$\phi^*$$ shatters $$\wp(A)\subset \phi\ \ |\wp(A)|=2^\kappa$$.

Anyhow I am quite stuck on this.
I think that similarly one can prove that $$\phi^*$$ has VC dimension $$\leq 2^\kappa$$

Can someone help?

I'll assume $$\kappa$$ is finite in this answer. For infinite $$\kappa$$, there's one major issue: The function $$\kappa\mapsto 2^\kappa$$ may not be strictly increasing on infinite cardinals. If you're really interested in infinite $$\kappa$$, I think that everything I wrote goes through with minor modifications if you assume GCH. I'm not sure what happens when $$\kappa\mapsto 2^\kappa$$ is not strictly increasing.

The set system $$\mathcal{P}_{\leq\kappa}(U) = \{A\subseteq U\mid |A|\leq \kappa\}$$ is a natural guess, since it is somehow the canonical set system with VC dimension $$\kappa$$. Unfortunately, it can't have dual VC-dimension $$2^\kappa$$. Suppose we have $$\mathcal{B} = \{B_1,\dots,B_{d}\}\in \wp_{\leq\kappa}(U)$$. To shatter $$\mathcal{B}$$, we need a family $$(a_X)_{X\subseteq \mathcal{B}}$$ of $$2^{d}$$-many (distinct) elements of $$U$$ such that for any subset $$X\subseteq \mathcal{B}$$, we have $$a_X\in B_j$$ if and only if $$B_j\in X$$. But for each $$j$$, $$B_j$$ is in exactly half of the $$2^{d}$$-many subsets of $$\mathcal{B}$$, so $$B_j$$ contains $$2^{d-1}$$ many distinct elements $$a_X$$, and hence $$\kappa \geq |B_j|\geq 2^{d-1}$$. This shows that $$\lfloor \log_2(\kappa)\rfloor + 1$$ is an upper bound for the dual VC dimension of $$\mathcal{P}_{\leq\kappa}(U)$$. And that quantity is much smaller than $$2^\kappa$$, for all $$\kappa>0$$.

However, this suggests that $$\mathcal{P}_{\leq 2^\kappa}(U)$$ might be an example of a set system with VC dimension $$2^\kappa$$ and dual VC dimension $$\kappa$$. This is equivalent to what you asked for, by dualizing. In fact, this system has dual VC dimension $$\kappa+1$$. But we can fix the example: rather than considering the subsets of size at most $$2^\kappa$$ of some large set $$U$$, let's just think about the full power set of a set $$U$$ of size $$2^\kappa$$ (and note that all such sets have size at most $$2^\kappa$$!).

Let $$U$$ be a set of size $$2^\kappa$$, and consider the set system $$\mathcal{P}(U)$$ (the full power set). Clearly $$\mathcal{P}(U)$$ has VC dimension $$2^\kappa$$, since it shatters $$U$$, but there is no subset of $$U$$ of size greater than $$2^\kappa$$ to shatter. But also the dual VC dimension is at most $$\kappa$$, since we would need $$2^{\kappa+1}$$ points in $$U$$ to shatter a subset of $$\mathcal{P}(U)$$ of size $$\kappa+1$$. So it remains to show that the dual VC dimension is at least $$\kappa$$.

This follows from the usual bound (see below): If the dual VC dimension of a set system is $$d$$, then the VC dimension of the set system is strictly less than $$2^{d+1}$$.

In the contrapositive, this says that if the VC dimension of a set system is at least $$2^{d+1}$$, then the dual VC dimension is strictly greater than $$d$$. Equivalently, taking $$\kappa = d+1$$, if the VC dimension of a set system is at least $$2^{\kappa}$$, then the dual VC dimension is at least $$\kappa$$, which is what we wanted.

Proof of the usual bound: We prove it in the modified contrapositive form, that if the VC dimension of a set system $$\Phi$$ on the set $$U$$ is at least $$2^{\kappa}$$, then the dual VC dimension is at least $$\kappa$$.

Let $$A\subseteq U$$ be a subset of size $$2^\kappa$$ which is shattered by $$\Phi$$. Put the elements of $$A$$ in bijection with binary sequences of length $$\kappa$$. For $$a\in A$$ and $$n < \kappa$$, write $$a(n)\in \{0,1\}$$ for the $$n^\text{th}$$ term in the corresponding sequence. Now for each $$n < \kappa$$, let $$B_n\in \Phi$$ be a set such that for all $$a\in A$$, $$a\in B_n$$ if and only if $$a(n) = 1$$ (we can do this since $$\Phi$$ shatters $$A$$). Then $$\mathcal{B} = \{B_n\mid n<\kappa\}$$ has size $$\kappa$$, and $$\mathcal{B}$$ is shattered by $$A$$. Indeed, for any subset $$X\subseteq \mathcal{B}$$, let $$a\in A$$ be the element such that $$a(n) = 1$$ if and only if $$B_n\in X$$. Then for all $$n$$, $$a\in B_n$$ if and only if $$a(n) = 1$$ if and only if $$B_n\in X$$. So the dual VC dimension is at least $$\kappa$$.

Incidentally, exactly the same argument shows that the usual bound is tight. That is, we can do better than what you asked for: We can find a set system with VC dimension $$2^{\kappa+1}-1$$ and dual VC dimension $$\kappa$$.

Let $$U$$ be a set of size $$2^{\kappa+1}-1$$, and consider the set system $$\mathcal{P}(U)$$. Clearly $$\mathcal{P}(U)$$ has VC dimension $$2^{\kappa+1}-1$$. But the dual VC dimension is at most $$\kappa$$, since we would need $$2^{\kappa+1}$$ elements of $$U$$ to shatter a subset of $$\mathcal{P}(U)$$ of size $$\kappa+1$$. And by the usual bound, since the VC dimension is at least $$2^\kappa$$, the dual VC dimension is at least $$\kappa$$, and hence equal to $$\kappa$$.

• Thanks, I was interested in the finite case, so your answer is perfect! – Francesco Bilotta Apr 16 at 18:30