Submodularity for Cartesian product We define a set function $f:2^E \rightarrow \mathbb{R}$ to be submodular if for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $.
How could I extend this concept to a Cartesian product of two sets? For example, would the following definition make sense?
We define a set function $f:2^{E_1 \times E_2} \rightarrow \mathbb{R}$ to be submodular if for every $ S_1,T_1\subseteq E_1 $ with $ S_1\subseteq T_1 $ and $ S_2,T_2\subseteq E_2 $ with $ S_2\subseteq T_2 $ for every $ p\in E_1\setminus T_1$ and $q\in E_2\setminus T_2 $, it holds that $f((S_1\cup \{p\}) \times (S_2\cup \{q\}))-f(S_1 \times S_2)\geq f((T_1\cup \{p\}) \times (T_2\cup \{q\})) - f(T_1 \times T_2) $.
If yes, then how can I prove this holds if submodularity holds for individual set functions $f_1:2^{E_1} \rightarrow \mathbb{R}$ and $f_2:2^{E_2} \rightarrow \mathbb{R}$?
Any help and hints will be greatly appreciated.
 A: Submodularity is really a property of functions on what are called lattices.
A lattice is a set $L$ with a partial order $\succeq$, along with the property that for all $a, b \in L$, $ a \vee b = l.u.b. \{a,b\} \in L$ and $ a \wedge b = g.l.b. \{a,b \} \in L$.   For you, $L$ is almost a power set, $\vee$ is set union, and $\wedge$ is set intersection, and the partial order $\succeq$ is set inclusion.  So the "real" definition of submodular is that for all sets $S$ and $ T$ in $L$, $f(S\cup T) + f(S\cap T) \le f(S) + f(T)$. The definitions you wrote are just to avoid introducing the idea of the lattice, order, and $\vee$ and $\wedge$.
But you want to look at Cartesian products of lattices.  You have a lattice $L_1$ and a lattice $L_2$, set functions $f_1$ on $L_1$ and $f_2$ on $L_2$, and you want to combine things together.
If you define $(S_1, S_2) \vee (T_1, T_2) = (S_1\cup S_2, T_1 \cup T_2)$ and $(S_1, S_2) \wedge (T_1, T_2) = (S_1\cap S_2, T_1 \cap T_2)$, the glb and lub properties still hold for $L_1 \times L_2$.  Now, if you take any submodular function $g$ on $\mathbb{R}^2$ --- $g(\max\{a,b\})+g(\min\{a,b\}) \le g(a) + g(b)$ --- you have
$$
g( f_1(S_1\vee S_2), f_2(T_1\vee T_2)) + g( f_1(S_1\wedge S_2), f_2(T_1\wedge T_2)) \le g(f_1(S_1),f_2(S_2))+g(f_1(T_1),f_2(T_2))
$$
and you get a submodular set function on the product of the two lattices if $f_1$ and $f_2$ are submodular. 
To extend this to $L_1 \times L_2 \times ... \times L_N$, make $g$ an argument of $N$ numbers so that $g(y) = g((y_1, ..., y_N))$ with the same submodularity property, so that
$$
g(y \vee y') + g(y \wedge y') \le g(y) + g(y').
$$
where $\vee$ is coordinatewise maximization and $\wedge$ is coordinatewise minimization.
