Subadditive set function

Let \Omega be a set and f \colon 2^{\Omega} \rightarrow \mathbb{R} be a set function, where 2^\Omega denotes the power set of \Omega. The function f is subadditive if for each subset S and T of \Omega, we have f(S) + f(T) \geq f(S \cup T). Note that by substitution of T=S into the defining equation, it follows that f(S) \ge 0 for all . == Examples of subadditive functions ==

of the mixture is smaller than the sum of the individual volumes, as the water can lodge in the spaces between the sand grains. A similar situation with a different mechanism occurs when ethanol is mixed with water, see apparent molar property. Every non-negative submodular set function is subadditive (the family of non-negative submodular functions is strictly contained in the family of subadditive functions). The function that counts the number of sets required to cover a given set is subadditive. Let T_1, \dotsc, T_m \subseteq \Omega such that \cup_{i=1}^m T_i=\Omega. Define f as the minimum number of subsets required to cover a given set. Formally, f(S) is the minimum number t such that there are sets T_{i_1}, \dotsc, T_{i_t} satisfying S\subseteq \cup_{j=1}^t T_{i_j}. Then f is subadditive. The maximum of additive set functions is subadditive (dually, the minimum of additive functions is superadditive). Formally, for each i \in \{1, \dotsc, m\}, let a_i \colon \Omega \to \mathbb{R} be additive set functions. Then f(S)=\max_{i} a_i(S) is a subadditive set function. Fractionally subadditive set functions are a generalization of submodular functions and a special case of subadditive functions. A subadditive function f is furthermore fractionally subadditive if it satisfies the following definition. For every S \subseteq \Omega, every X_1, \dotsc, X_n \subseteq \Omega, and every \alpha_1, \dotsc, \alpha_n \in [0, 1], if 1_S \leq \sum_{i=1}^n \alpha_i 1_{X_i}, then f(S) \leq \sum_{i=1}^n \alpha_i f(X_i). The set of fractionally subadditive functions equals the set of functions that can be expressed as the maximum of additive functions, as in the example in the previous paragraph. == See also ==