 Solution

Use the chain lower bound for a submodular set function. Order $T=\{x_1,\dots ,x_n\}$, set $P_j=\{x_1,\dots ,x_j\}$ with $P_0=\varnothing$, and put $a_j=f(P_j)-f(P_{j-1})$. For each $U\subseteq T$, reveal its elements in this same order. Since $U\cap P_{j-1}\subseteq P_{j-1}$, diminishing returns and the normalised set function property giveApply this to each $T_i$ and interchange the finite sums. Every element occurs exactly $k$ times, soThis is the exact-cover inequality for submodular set functions. Some $a_j$ can be negative: exact multiplicity, rather than merely at least $k$ occurrences, is what makes the argument valid without monotonicity. In fact the nonnegative function hypothesis is unnecessary here. If $T=\varnothing$, every $T_i$ is empty and both sides vanish.