Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Subadditive set function

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated September 7, 2025

In mathematics, a subadditive set function is a set function whose value, informally, has the property that the value of function on the union of two sets is at most the sum of values of the function on each of the sets. This is thematically related to the subadditivity property of real-valued functions.

01Definition

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)\geq 0 for all ⁠S⁠.

Everyday example of sigma sub-additivity: when sand is mixed with water, the bulk volume 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.
Everyday example of sigma sub-additivity: when sand is mixed with water, the bulk volume 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.

02Examples of subadditive functions


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.

Watch videos about Subadditive set functionExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Subadditive set function”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Submodular set function

In mathematics, a submodular set function is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit (diminishing returns). The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks.

Utility functions on indivisible goods

Some branches of economics and game theory deal with indivisible goods, discrete items that can be traded only as a whole. For example, in combinatorial auctions there is a finite set of items, and every agent can buy a subset of the items, but an item cannot be divided among two or more agents.