How would you intuitively but rigorously explain what the VC dimension is? The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents or means, as it involves other concepts, such as shattering, hypothesis class, learning and sets. For example, let's take a look at the definition given by Shai Shalev-Shwartz and Shai Ben-David (p. 70)

DEFINITION $6.5$ (VC-dimension) The VC-dimension of a hypothesis class $\mathcal{H}$, denoted $\operatorname{VCdim}(\mathcal{H})$, is the maximal size of a set $C \subset \mathcal{X}$ that can be shattered by $\mathcal{H}$. If $\mathcal{H}$ can shatter sets of arbitrarily large size we say that $\mathcal{H}$ has infinite VC-dimension.

Without knowing what a hypothesis class is, or what the specific $C$, $X$ and $H$ in this definition are, it's difficult to understand this definition. Even if you are familiar with what a hypothesis class is (i.e. a set of sets, i.e. our set of functions/hypotheses/models, e.g. the set of all possible neural networks with a specific topology) and you know that $C$ and $X$ are sets of input points, it should still not be clear what the VC dimesion really is or represents.
So, how would you intuitively and rigorously explain the exact definition of the VC dimension?
Note that I am not asking for answers like

The VC dimension represents the complexity (or expressive power, richness, or flexibility) of your model/hypothesis class.

Of course, this is easy to memorize, but it's quite vague. So, I am not looking for vague/general answers. I am looking for answers that rigorously but intuitively describe the mathematical definition of the VC dimension. For example, you could provide an illustration that shows what the VC dimension is, and, in your example (e.g. the XOR problem cannot be solved by a set of lines), you can describe what $H$, $C$, and $X$ are, and how they relate to the typical concepts you will find an introductory course to machine learning, but you should not forget to describe the concept of shattering. If you have other ideas of how to illustrate this concept memnomically, feel free to provide an answer.
Shattered set. First we need a concept of a shattered set. I'll work from a shattered set example in Wikipedia adjusting it to your notation.
The statement that $\mathcal{H}$ shatters $C$ means that for every subset $A \subset C$ there is a set $B\in\mathcal{H}$ such that $B$ &quot;separates&quot; $A$ from $C \backslash A$. Writing this formally:
$$\text{shatters}(\mathcal{H},C) = \forall A \subset C\; \exists B\in\mathcal{H}\;.\;A = B\,\cap A $$
As an example consider the set $C$ of four points on $\mathcal{X} = \mathbb{R}^2$:
$$C = \left\{(0,0); (0,1); (1,0); (1,1)\right\}$$
And the classification class $\mathcal{H}$ being all possible 2D discs on $\mathcal{X} =\mathbb{R}^2$. (Notice that people use the world &quot;class&quot; here, because we are dealing with &quot;set-of-sets&quot; stuff and that might get tricky). Note that a disk can be represented as the set of all points inside the circle.
Now, it turns out that this $\mathcal{H}$ doesn't shatter $C$. The counterexample would be the subset $A$ of &quot;diagonal&quot; points:
$$A = \left\{(0,0); (1,1)\right\} \subset C$$
There is no 2D disk $B\in\mathcal{H}$ (in the context of learning theory, an element/set of the hypothesis class is a hypothesis, which can also be viewed as a function) that satisfies $A = B\,\cap A$.  Intuitively, this means that you cannot use a 2D disk to classify your pair of points $A$ from the rest of the set $C$.
The VC dimension of $\mathcal{H}$ is the maximal cardinality $d$ of the set $C$ that it can shatter. For $d=3$, we can provide tree points $C'$ for which we can easily find all discs that cover all eight possible subsets of $C'$:
$$C' = \left\{(0,0); (0,1); (1,0)\right\}$$
Above we've shown that for a particular set $C$ of $d=4$ points $\text{shatters}(\mathcal{H}, C)$ is false. But we need to prove that it is false for all 4-point sets. To prove this, we  consider a convex hull of an arbitrary set of four points $C = \left\{a;b;c;d\right\}$. In general position, the convex hull is either a triangle or a quad:

In the case of a triangle, we choose the outermost three points as a counterexample set $A$. So, with this (labeling) configuration, you cannot find a disk that covers (i.e. classifies) the outermost three points correctly while excluding the point inside the triangle. In the case of a quad, we choose the pair on the longest diagonal. If any three points lay on a single line, then we choose the pair of outermost points.
This sketches a proof that no $d=4$ point set can be shattered by $\mathcal{H}$, but we've shown that there is a $d=3$ set $C'$ that can be. Concluding that $VCdim(\mathcal{H}) = 3$
Another example is considered on the next page (pg. 71) of the book you've referenced. It again considers 2D plane  $\mathcal{X} =\mathbb{R}^2$ and the classification class $\mathcal{H}$ is all possible axis-aligned rectangles. Authors show a configuration $C$ of four points that can be shattered by $\mathcal{H}$ on the left of figure 6.1. And then provide a proof that no $d=5$ points can be shattered by axis-aligned rectangles. Concluding that VC dimension of their  $\mathcal{H}$ is four.
Hope these examples help. (BTW, note that, it seems that Deep Learning has quite bad VC dimension but it still works somehow - which is rather puzzling).