Subadditive set functie - Subadditive set function

In de wiskunde is een subadditieve set-functie een set-functie waarvan de waarde, informeel, de eigenschap heeft dat de waarde van de functie op de vereniging van twee sets ten hoogste de som is van de waarden van de functie op elk van de sets. Dit is thematisch gerelateerd aan de subadditiviteitseigenschap van reëel gewaardeerde functies.

Definitie

Laat een set zijn en een ingestelde functie , waarbij de vermogensset van . De functie f is subadditief als we voor elke subset en van hebben . ${\ displaystyle \ Omega}$${\ displaystyle f \ dubbele punt 2 ^ {\ Omega} \ rightarrow \ mathbb {R}}$${\ displaystyle 2 ^ {\ Omega}}$${\ displaystyle \ Omega}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle \ Omega}$${\ Displaystyle f (S) + f (T) \ geq f (S \ cup T)}$

Voorbeelden van subadditieve functies

Elke niet-negatieve submodulaire setfunctie is subadditief (de familie van niet-negatieve submodulaire functies is strikt opgenomen in de familie van subadditieve functies).

De functie die het aantal sets telt dat nodig is om een bepaalde set te dekken , is subadditief. Laat zo dat . Definieer dit als het minimum aantal subsets dat nodig is om een ​​bepaalde set te dekken. Formeel is het minimum aantal zodanig dat er sets zijn die voldoen . Dan is subadditief. ${\ displaystyle T_ {1}, \ dotsc, T_ {m} \ subseteq \ Omega}$${\ displaystyle \ cup _ {i = 1} ^ {m} T_ {i} = \ Omega}$${\ displaystyle f}$${\ displaystyle f (S)}$${\ displaystyle t}$${\ displaystyle T_ {i_ {1}}, \ dotsc, T_ {i_ {t}}}$${\ displaystyle S \ subseteq \ cup _ {j = 1} ^ {t} T_ {i_ {j}}}$${\ displaystyle f}$

Het maximum van additieve setfuncties is subadditief (tweevoudig, het minimum van additieve functies is superadditief ). Laten we formeel voor elk additieve ingestelde functies zijn. Dan is een subadditieve set-functie. ${\ displaystyle i \ in \ {1, \ dotsc, m \}}$${\ displaystyle a_ {i} \ dubbele punt \ Omega \ to \ mathbb {R} _ {+}}$${\ displaystyle f (S) = \ max _ {i} \ left (\ sum _ {x \ in S} a_ {i} (x) \ right)}$

Fractioneel subadditieve setfuncties zijn een generalisatie van submodulaire functies en een speciaal geval van subadditieve functies. Een subadditieve functie is bovendien fractioneel subadditief als deze aan de volgende definitie voldoet. Voor elke , elke en elke , als , dan . De set van fractioneel subadditieve functies is gelijk aan de set functies die kan worden uitgedrukt als het maximum van additieve functies, zoals in het voorbeeld in de vorige paragraaf. ${\ displaystyle f}$${\ displaystyle S \ subseteq \ Omega}$${\ displaystyle X_ {1}, \ dotsc, X_ {n} \ subseteq \ Omega}$${\ displaystyle \ alpha _ {1}, \ dotsc, \ alpha _ {n} \ in [0,1]}$${\ displaystyle 1_ {S} \ leq \ sum _ {i = 1} ^ {n} \ alpha _ {i} 1_ {X_ {i}}}$${\ displaystyle f (S) \ leq \ sum _ {i = 1} ^ {n} \ alpha _ {i} f (X_ {i})}$

Zie ook

• Submodulaire set functie
• Nutsfuncties op ondeelbare goederen

Citaten