Constrained DMC information capacity is attained, nondecreasing, and concave

The probability simplex on $\mathcal{X}$ is closed and bounded in ${\mathbb{R}}^{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}$. The feasible subset is closed because $P_X\mapsto \bar{c}(P_X)$ is linear and continuous; it is nonempty because ${\delta }_{x_{\min }}$ has cost $c_{\min }\le \mathrm{\Gamma }$. Hence it is compact by [F5]. The output law $P_{X}W$ is linear in $P_X$, so [F3]–[F4] show that $P_X\mapsto I(P_X;W)$ is continuous. Nonnegativity of mutual information follows from [F6] applied to the joint law and product marginals. Also $I(P_X;W)=H(P_X)-H(X\mid Y)\le H(P_X)$ by [F3], since conditional entropy is a sum of nonnegative terms. Concavity in [F4] gives $H(P_X)\le \ln \mathrm{\mid }\mathcal{X}\mathrm{\mid }$: the uniform vector is the average of the finitely many coordinate permutations of $P_X$, all of which have the same entropy. Thus the objective lies in $[0,\ln \mathrm{\mid }\mathcal{X}\mathrm{\mid }]$, and [F5] proves its supremum is finite and attained.

If ${\mathrm{\Gamma }}_0\le {\mathrm{\Gamma }}_1$, the feasible set at ${\mathrm{\Gamma }}_0$ is contained in the one at ${\mathrm{\Gamma }}_1$, proving monotonicity. For $0\le \theta \le 1$, let $P_0,P_1$ attain $C_I({\mathrm{\Gamma }}_0),C_I({\mathrm{\Gamma }}_1)$. The mixture $P_{\theta }=\theta P_0+(1-\theta )P_1$ has cost at most $\theta {\mathrm{\Gamma }}_0+(1-\theta ){\mathrm{\Gamma }}_1$. By [F3]–[F4], mutual information is concave in $P_X$: the output entropy is concave and the conditional entropy term is linear. Therefore $C_I(\theta {\mathrm{\Gamma }}_0+(1-\theta ){\mathrm{\Gamma }}_1)\ge \theta C_I({\mathrm{\Gamma }}_0)+(1-\theta )C_I({\mathrm{\Gamma }}_1)$.

Suppose $\mathrm{\Gamma }>c_{\min }$ and $P_X^{\ast }$ attains $C_I(\mathrm{\Gamma })$. If $\bar{c}(P_X^{\ast })=\mathrm{\Gamma }$, choose a minimum-cost symbol $x_{\min }$ from the finite alphabet. Then $\bar{c}(P_{X,ϵ})=(1-ϵ)\mathrm{\Gamma }+ϵc_{\min }<\mathrm{\Gamma }$ for every $ϵ>0$. Since $P_{X,ϵ}\to P_X^{\ast }$ and the mutual-information objective is continuous by step 1.1, $I(P_{X,ϵ};W)\to C_I(\mathrm{\Gamma })$. If $P_X^{\ast }$ already has strict cost, no approximation is needed.