Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?

Question

In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, etc.

All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $\mathcal{H}$? Since all examples ends up with a lower bound matching the upper bound, is the lower bound just helpful/useful to set a target when trying to show an upper bound?

Reference: From page 41 of this book pdf version https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf

Answer 1

Lets use the quotes from the book.

To give an upper bound, we need to prove that no set $S$ of cardinality $d + 1$ can be shattered by $H$

By doing this, we are proving that $\text{VCdim}(H) < d+1$, but it does not necessarily mean $\text{VCdim}(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $\text{VCdim}(H) < 2d+1$, although we know $\text{VCdim}(H) = d$. Therefore:

To give a lower bound $d$ for $\text{VCdim}(H)$, it suffices to show that a set $S$ of cardinality $d$ can be shattered by $H$

We need to prove the lower bound as well to show that $d \le \text{VCdim}(H) < d+1$, which implies $\text{VCdim}(H) = d$. The last equality means that for each size $1$ to $d$, $H$ can shatter at least one set $S$ with that size.

Note that for the $2d+1$ example, we will fail to prove $2d \le \text{VCdim}(H)$, therefore $\text{VCdim}(H) \neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.