How can I understand the multiclass verison of "shattering" intuitively? I'm learning machine learning. VC dimension is a good way to measure the complexity of hypothesis class for binary classifier and has a very good intuitive explanation from shattering.
I know that both dimensions are based on the "shattering" concept.
When we discuss VC-dimension, shattering means $H$ have all the behaviors on a set of size less than $VCdim(H)$. That is:
Let $C=(c_1,\dots,c_d)$ be a shattered set by $H$.
Denote the restriction of $H$ to $C$ by $H_c$.
$$H_c = \{(h(c_1),\dots,h(c_d)):h\in H\}$$
Then $$|H_c| = 2^d$$
However, according to the definition of shattering on Page 403 of the book "Understanding Machine Learning: from theory to algorithms"(You can click the link to download the book.), the multiclass version of "shattering" is as follows:

We say a that a set $C\subset X$ is shattered by $H$ if there exist 2 functions $f_0$, $f_1: C\to [k]$ such that

*

*for every $x\in C$, $f_0(x) \ne f_1(x)$.


*for every $B\subset C$, there exists a function $h\in H$ such that
$$\forall x\in B, h(x)=f_0(x)\ and\ \forall x\in C \backslash B, h(x) = f_1(x)$$

Here, $H$ does not have all the behaviors on a set of size less than the Nagarajan dimension. That is,
$$|H_c| \ne k^d$$ when $k>2$.
How do you understand the definition of the multiclass version of shattering, especially this point?
 A: Original question:
This is actually fairly straightforward if you translate from math to human.
You have a set, i.e. a grab-bag of possible inputs, called $C$, and a function $h(x)$ that can work on all the things in it.
If you imagine the C is a bag of marbles, some of them are Blue, some are other Colors. 
If you separated them, the new bag with only Blues will be a new bag B, and you'll be left with the other bag C, except without all the Blues, so we'll call it C\B.

If C is shattered by h, the definition simply explains what $h(x)$ does. It grabs a random marble from the bag, if it's Blue it feeds them to function $f1(x)$, otherwise it feeds them to function $f2(x)$, and spits out whatever those functions would.
There's an additional constraint, which is that $f_1$ must, in practice, be different from $f_2$. 
In practice meaning something like:
$$f_1 := 2x+2$$
$$f_2 := 0.5*(4x+4)$$
doesn't count, as it's blatantly cheating. 
They need to be able to use the same input to produce a different output.
You can extend it to any number of specific 'colors': partition the input space into some non-overlapping chunks, pick a unique function $F_n(x)$ for each chunk, and let $h(x)$ dispatch the actual computation to one of the $F(x)$es based on which chunk your x is in.

Re: edited part:
I'll start with a caveat that the 'behavior' here seems a little under-defined for my tastes, so I may be misunderstanding something.
In the binary case, since the sum of probabilities of all the options is 1, any nonempty subset of inputs from C to h assigns between 0 and 1 of the total probability to one class, and the rest to the other.
So, even if $f2(x)$ doesn't ostensively work for some specific x, you can infer what it 'should' output by simply calculating $1-f1(x)$, or vice versa.
Note that you only ever need two functions in this definition. If you want to support, say, three, you can rewrite $f2(x)$ as $g2(x) := ({f_2}_a(x)$ if something else ${f_2}_b(x))$, and so on, so the definition still holds.

Re: edited^2:
Oh dear. This is a long story.
The cardinality of H is defined here as the count of all possible function outputs for all included inputs. They don't need to be distinct (i.e. if $h(c_1) = h(c_7) = h(c_{124})$ all three are counted as three different items).
If we had just one class, there's only one possible output per all inputs,  $p(k_1) = 1$. That means the cardinality of $H$ grows linearly with the number of inputs in $C$.
With two classes, the outputs are bounded between zero and one - simply by the definition of probability. Furthermore, they are complementary: $p(k_2|x) = 1 - p(k_1|x)$, so we only need to know one to infer the other.
If you took reals as your $C$, you can plot some values of $p(k_1)$ on the x-axis, and the values of $p(k_2)$ that satisfy this condition on the y axis of a 2D plot. An interesting feature of that is that if you look at these pairs and plot enough of them, you get a 45-degree slope from $(0,1)$ to $(1,0)$, forming a right triangle with the X & Y axes.
By simple application of Pythagoras, we can find the exact length of that slope, which corresponds to the number of all valid single-class outputs = $\sqrt{1^2+1^2} = \sqrt 2$.
Now, that's for one half of the pair. We have two. Since we're operating on reals, picking one for the value of $p(k_1)$ doesn't really shrink the space of options for $p(k_2)$, so we can pretend they're independent samples with replacement. Therefore, the total number of possible outcomes for all classes a single input in C is: 
$$|H_x| = {\sqrt 2}^2 = 2$$
Rinse and repeat for N inputs in C, each one expands the space by a factor of 2, so 
$$|H_c| = {({\sqrt 2}^2)}^n = 2^n$$
Now, if you add a third class... things get messy. Now $p(k_1) + p(k_2) + p(k_3) = 1$. Now instead of a 1D slope in a 2D space, you need to find a 2D area in a 3D space; it's a triangle anchored at $(1,0,0); (0,1,0); (0,0,1)$.
I'll... leave you to it, okay? There's a reason I'm not on the GeometryExchange, and this answer is long enough as-is.
Again, take the answer and raise it to the Nth power to get the actual cardinality over $C_N$. Similarly, for additional classes, you get higher-dimensional analogues (hyperplanes) of valid outputs.
