[proofplan]
We prove each closure property directly from the defining two-set inequality. For non-negative linear combinations, we multiply the two submodular inequalities by non-negative scalars and add them, preserving the inequality direction. For the modular perturbation, the modular equality contributes the same amount to both sides of the submodular inequality. For the supermodular case, multiplying the supermodular inequality by $-1$ reverses the inequality and gives exactly submodularity of $-h$.
[/proofplan]
[step:Combine the two submodular inequalities with non-negative coefficients]
Fix $\alpha,\beta\in[0,\infty)$, and fix arbitrary subsets $A,B\subset E$. Define the function $F:\mathcal{P}(E)\to\mathbb{R}$ by
\begin{align*}
F(S)=(\alpha f+\beta g)(S):=\alpha f(S)+\beta g(S)
\end{align*}
for every $S\subset E$.
Since $f$ and $g$ are submodular, we have
\begin{align*}
f(A)+f(B) \geq f(A\cup B)+f(A\cap B).
\end{align*}
Also,
\begin{align*}
g(A)+g(B) \geq g(A\cup B)+g(A\cap B).
\end{align*}
Because $\alpha,\beta\geq 0$, multiplying the [first inequality](/theorems/2897) by $\alpha$ and the second by $\beta$ preserves the inequality direction. Adding the resulting inequalities gives
\begin{align*}
\alpha f(A)+\alpha f(B)+\beta g(A)+\beta g(B)
\geq
\alpha f(A\cup B)+\alpha f(A\cap B)+\beta g(A\cup B)+\beta g(A\cap B).
\end{align*}
Regrouping the left-hand side and the right-hand side according to the definition of $F$ yields
\begin{align*}
F(A)+F(B)\geq F(A\cup B)+F(A\cap B).
\end{align*}
Since $A,B\subset E$ were arbitrary, $F=\alpha f+\beta g$ is submodular.
[guided]
We want to prove that the function $F:\mathcal{P}(E)\to\mathbb{R}$ defined by
\begin{align*}
F(S)=(\alpha f+\beta g)(S):=\alpha f(S)+\beta g(S)
\end{align*}
for every $S\subset E$ satisfies the submodular inequality. Thus we fix arbitrary subsets $A,B\subset E$ and aim to prove
\begin{align*}
F(A)+F(B)\geq F(A\cup B)+F(A\cap B).
\end{align*}
The hypotheses give exactly two inequalities for these same subsets. First,
\begin{align*}
f(A)+f(B) \geq f(A\cup B)+f(A\cap B).
\end{align*}
Second,
\begin{align*}
g(A)+g(B) \geq g(A\cup B)+g(A\cap B).
\end{align*}
The important point is that the coefficients are non-negative. Since $\alpha\geq 0$, multiplying the first inequality by $\alpha$ does not reverse its direction:
\begin{align*}
\alpha f(A)+\alpha f(B)\geq \alpha f(A\cup B)+\alpha f(A\cap B).
\end{align*}
Similarly, since $\beta\geq 0$,
\begin{align*}
\beta g(A)+\beta g(B)\geq \beta g(A\cup B)+\beta g(A\cap B).
\end{align*}
Adding these two inequalities gives
\begin{align*}
\alpha f(A)+\alpha f(B)+\beta g(A)+\beta g(B)
\geq
\alpha f(A\cup B)+\alpha f(A\cap B)+\beta g(A\cup B)+\beta g(A\cap B).
\end{align*}
Now we regroup terms using the definition of $F$. The left-hand side is
\begin{align*}
\alpha f(A)+\beta g(A)+\alpha f(B)+\beta g(B)=F(A)+F(B),
\end{align*}
and the right-hand side is
\begin{align*}
\alpha f(A\cup B)+\beta g(A\cup B)+\alpha f(A\cap B)+\beta g(A\cap B)
=F(A\cup B)+F(A\cap B).
\end{align*}
Therefore
\begin{align*}
F(A)+F(B)\geq F(A\cup B)+F(A\cap B).
\end{align*}
Because the subsets $A$ and $B$ were arbitrary, this is precisely the submodularity of $\alpha f+\beta g$.
[/guided]
[/step]
[step:Add a modular function without changing the submodular gap]
Fix arbitrary subsets $A,B\subset E$. Define the function $G:\mathcal{P}(E)\to\mathbb{R}$ by
\begin{align*}
G(S)=(f+m)(S):=f(S)+m(S)
\end{align*}
for every $S\subset E$.
By submodularity of $f$,
\begin{align*}
f(A)+f(B)\geq f(A\cup B)+f(A\cap B).
\end{align*}
By modularity of $m$,
\begin{align*}
m(A)+m(B)=m(A\cup B)+m(A\cap B).
\end{align*}
Adding this equality to the submodular inequality for $f$ gives
\begin{align*}
f(A)+f(B)+m(A)+m(B)
\geq
f(A\cup B)+f(A\cap B)+m(A\cup B)+m(A\cap B).
\end{align*}
Regrouping terms gives
\begin{align*}
G(A)+G(B)\geq G(A\cup B)+G(A\cap B).
\end{align*}
Since $A,B\subset E$ were arbitrary, $G=f+m$ is submodular.
[/step]
[step:Convert supermodularity into submodularity by negation]
Fix arbitrary subsets $A,B\subset E$. Define the function $K:\mathcal{P}(E)\to\mathbb{R}$ by
\begin{align*}
K(S)=(-h)(S):=-h(S)
\end{align*}
for every $S\subset E$.
Since $h$ is supermodular,
\begin{align*}
h(A)+h(B)\leq h(A\cup B)+h(A\cap B).
\end{align*}
Multiplying this inequality by $-1$ reverses the inequality direction and gives
\begin{align*}
-h(A)-h(B)\geq -h(A\cup B)-h(A\cap B).
\end{align*}
Using the definition of $K$, this is
\begin{align*}
K(A)+K(B)\geq K(A\cup B)+K(A\cap B).
\end{align*}
Since $A,B\subset E$ were arbitrary, $K=-h$ is submodular. This proves all three closure properties.
[/step]
