I am stuck at the following exercise:
Let $\mathcal{C} = (\mathcal{X} , P, \mathcal{Y})$ be a channel with $\mathcal{X} = \{x_1, \ldots, x_n\}$. Let $\mathcal{C}^\prime =(\mathcal{X}^\prime, P^\prime, \mathcal{Y})$ be the channel in which $\mathcal{X}^\prime = \{x_1, \ldots , x_n, x_{n+1}\}$ and the matrix $P^\prime$ consists of the matrix P with one more row added. Show that $cap(\mathcal{C}^\prime) \ge cap(\mathcal{C})$.
The larger channel has greater capacity, not smaller as in the question. The operational proof is that capacity is the maximum possible rate, and if you can achieve some rate over the smaller channel, you can achieve this rate over the larger channel by simply never using the extra input.
More directly, let $P_X$ be the input distribution that achieves capacity in the case of the channel $P_{Y|X}$. Then the distribution $Q_{X'}$ s.t. $Q_{X'}(x) = P_X(x)$ if $x \in \{x_1,\dots, x_n\}$ and $Q_{X'}(x_{n+1}) = 0$ is a valid input distribution for $\mathcal{C}',$ and since $P_{Y'|X'}'$ is the same as $P_{Y|X}$ in the support of $Q_{X'},$ the value of $I(X';Y')$ for this choice of input distribution equals the capacity of $\mathcal{C}$. The capacity of $\mathcal{C}'$ in turn must be no smaller than the value of $I(X';Y')$ with this input distribution (since it is max over these $I$s), and so the capacity of $\cal C'$ must dominate that of $\cal C$.