Additive set functions and measures

Set function is a valid numerical function $f{\mbox{: }}2^{\Omega }\rightarrow \ \mathbb {R}$ ${\ displaystyle f {\ mbox {:}} 2 ^ {\ Omega} \ rightarrow \ \ mathbb {R}}$ ${\ displaystyle f {\ mbox {:}} 2 ^ {\ Omega} \ rightarrow \ \ mathbb {R}}$ defined on $2^{\Omega }\$ ${\ displaystyle 2 ^ {\ Omega} \}$ ${\ displaystyle 2 ^ {\ Omega} \}$ - the set of all subsets of some arbitrary finite set $\Omega \$ ${\ displaystyle \ Omega \}$ ${\ displaystyle \ Omega \}$ measurable space $(\Omega ,{\mathcal {F}})$ ${\ displaystyle (\ Omega, {\ mathcal {F}})}$ ${\ displaystyle (\ Omega, {\ mathcal {F}})}$ and taking its values on the numerical axis $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb {R}$ .

An additive set-function is a set-function for which the equality holds:

$f(x\cup y)+f(x\cap y)=f(x)+f(y)$ ${\ displaystyle f (x \ cup y) + f (x \ cap y) = f (x) + f (y)}$ ${\ displaystyle f (x \ cup y) + f (x \ cap y) = f (x) + f (y)}$

for any subsets $x\subseteq \Omega$ ${\ displaystyle x \ subseteq \ Omega}$ ${\ displaystyle x \ subseteq \ Omega}$ and $y\subseteq \Omega$ ${\ displaystyle y \ subseteq \ Omega}$ ${\ displaystyle y \ subseteq \ Omega}$ .

Measure is an additive set-function for which it is true: $f(\emptyset )=0$ ${\ displaystyle f (\ emptyset) = 0}$ ${\ displaystyle f (\ emptyset) = 0}$ .

The value of any measure $f\$ ${\ displaystyle f \}$ ${\ displaystyle f \}$ on an arbitrary subset $x\subseteq \Omega$ ${\ displaystyle x \ subseteq \ Omega}$ ${\ displaystyle x \ subseteq \ Omega}$ can be represented as the sum of its values on monoplet $\{\omega \}:\omega \in x$ ${\ displaystyle \ {\ omega \}: \ omega \ in x}$ ${\ displaystyle \ {\ omega \}: \ omega \ in x}$ :

$f(x)=\sum _{\omega \in x}f(\{\omega \}){\mbox{, }}x\subseteq \Omega$ ${\ displaystyle f (x) = \ sum _ {\ omega \ in x} f (\ {\ omega \}) {\ mbox {,}} x \ subseteq \ Omega}$ ${\ displaystyle f (x) = \ sum _ {\ omega \ in x} f (\ {\ omega \}) {\ mbox {,}} x \ subseteq \ Omega}$ .

It is believed that $\sum _{\omega \in \emptyset }f(\{\omega \})=0,\prod _{\omega \in \emptyset }f(\{\omega \})=1$ ${\ displaystyle \ sum _ {\ omega \ in \ emptyset} f (\ {\ omega \}) = 0, \ prod _ {\ omega \ in \ emptyset} f (\ {\ omega \}) = 1}$ ${\ displaystyle \ sum _ {\ omega \ in \ emptyset} f (\ {\ omega \}) = 0, \ prod _ {\ omega \ in \ emptyset} f (\ {\ omega \}) = 1}$ .

Literature

Lovasz L. (1983) Submodular functions and convexity. In: A. Bachem, M. Grotschel, and B. Korte, editors, Mathematical Programming - The State of the Art}, Springer-Veriag, 235–257.
Fujishige S. (1984) Theory of submodular programs, A Fenchel-type min-max theorem and subgradients of submodular functions, Mathematical Programming, 29, 142-155.
Foldes Stephan, Hammer Peter L. (2002) Submodularity, Supermodularity, Higher Order Monotonicities. Rutcor research

Report, 10-2002, March, 2002.

Hammer, PL, and S. Rudeanu} (1968) Boolean Methods in Operation Research and Relared Areas, Springer-Verlag, Berlin, Heidelberg, New York.

Additive set functions and measures

Literature

More articles: