equivalence of definitions of a submodular function on sets

Question

Wikipedia lists these definitions of the submodularity of a function $f:2^\Omega\rightarrow\mathbb{R}$ as equivalent:

1. for every $A,B\subseteq\Omega$ with $A\subseteq B$ and every $x\in\Omega\setminus B$ we have that $f(A\cup\{x\})-f(A)\geq f(B\cup\{x\}-f(B)$.
2. for every $A,B\subseteq\Omega$ we have that $f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$.

I know that $2\implies 1$ since if 2 is true we have $$f(A\cup\{x\})+f(B) \geq f(A\cup B\cup\{x\}) + f((A\cup\{x\})\cap B)$$ and if $A\subseteq B$, $x\in\Omega\setminus B$ the RHS equals $$f(B\cup\{x\}) + f(A).$$ We can then rearrange terms to get the result.

However, I can't come up with a way to prove $1\implies 2$. Some tips would be much appreciated.

Answer 1

Thm. If $\Omega$ is finite, then the following conditions on $f\colon 2^{\Omega}\to \mathbb R$ are equivalent.

(1) For every $X\subseteq Y\subseteq \Omega$ and every $x\in\Omega\setminus Y$ we have that $$f(X\cup\{x\})-f(X)\geq f(Y\cup\{x\})-f(Y).$$

(2) For every $S, T\subseteq \Omega$ we have that $$f(S)+f(T)\geq f(S\cup T)+f(S\cap T).$$

Proof of $(1)\Rightarrow(2)$: Let $x_1,\ldots,x_n$ be an enumeration of $S\setminus (S\cap T)$. Define $X_i$ to be $(S\cap T)\cup\{x_1,\ldots,x_i\}$ and $Y_i$ to be $X_i\cup T$. Then $X_i\subseteq Y_i\subseteq \Omega$ and $x_{i+1}\notin Y_i$, so by (1) we have $$ f(X_i\cup\{x_{i+1}\})-f(X_i)\geq f(Y_i\cup\{x_{i+1}\})-f(Y_i), $$ which may be rewritten as $$ f(X_{i+1})-f(X_i)\geq f(Y_{i+1})-f(Y_i). $$ If you sum both sides over $i$ you obtain $$ f(X_n)-f(X_0)\geq f(Y_n)-f(Y_0), $$ which may be rewritten $$ f(S)-f(S\cap T)\geq f(S\cup T)-f(T), $$ which may be further rewritten to look like (2). \\\