Субадитивная функция множества

В математике субаддитивная функция множества — это функция множества , значение которой, неформально, обладает тем свойством, что значение функции при объединении двух множеств не превышает суммы значений функции на каждом из множеств. Тематически это связано со свойством субаддитивности вещественных функций.

Определение

Позволять $\Omega$ быть набором и $f\colon 2^{\Omega }\rightarrow \mathbb {R}$ — функция множества , где $2^{\Omega }$ обозначает мощности набор $\Omega$. Функция f субаддитивна , если для каждого подмножества $S$ и $T$ из $\Omega$, у нас есть $f(S)+f(T)\geq f(S\cup T)$.

Примеры субаддитивных функций

Повседневный пример сигма-субаддитивности: когда песок смешивается с водой, общий объем смеси меньше суммы отдельных объемов, поскольку вода может задерживаться в промежутках между зернами песка. Аналогичная ситуация с другим механизмом возникает при смешивании этанола с водой, см. кажущееся молярное свойство .

Всякая неотрицательная субмодулярная функция множества субаддитивна (семейство неотрицательных субмодулярных функций строго содержится в семействе субаддитивных функций).

Функция, подсчитывающая количество множеств, необходимых для покрытия данного множества, является субаддитивной. Позволять $T_{1},\dotsc ,T_{m}\subseteq \Omega$ такой, что $\cup _{i=1}^{m}T_{i}=\Omega$. Определять $f$ как минимальное количество подмножеств, необходимое для покрытия данного множества. Формально, $f(S)$ это минимальное количество $t$ такие, что существуют множества $T_{i_{1}},\dotsc ,T_{i_{t}}$ удовлетворяющий $S\subseteq \cup _{j=1}^{t}T_{i_{j}}$. Затем $f$ является субаддитивным.

Максимум супераддитивен аддитивных функций множества субаддитивен (двойственно минимум аддитивных функций ) . Формально для каждого $i\in \{1,\dotsc ,m\}$, позволять $a_{i}\colon \Omega \to \mathbb {R} _{+}$ быть аддитивными функциями множества. Затем $f(S)=\max _{i}\left(\sum _{x\in S}a_{i}(x)\right)$ является субаддитивной функцией множества.

Дробно субаддитивные функции множества являются обобщением субмодулярных функций и частным случаем субаддитивных функций. Субадитивная функция $f$ кроме того, является дробно субаддитивным, если удовлетворяет следующему определению. Для каждого $S\subseteq \Omega$, каждый $X_{1},\dotsc ,X_{n}\subseteq \Omega$и каждый $\alpha _{1},\dotsc ,\alpha _{n}\in [0,1]$, если $1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}$, затем $f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})$. Набор дробно-субадитивных функций равен набору функций, которые можно выразить как максимум аддитивных функций, как в примере в предыдущем параграфе.

См. также

• Субмодульная функция множества
• Функции полезности для неделимых благ.