In mathematics, a superadditive set function is a
set function
In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line \R \cup \, which consists of the real numbers \R a ...
whose value when applied to the
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
of two
disjoint sets
In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...
is greater than or equal to the sum of values of the function applied to each of the sets separately. This definition is analogous to the notion of
superadditivity In mathematics, a function f is superadditive if
f(x+y) \geq f(x) + f(y)
for all x and y in the domain of f.
Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality
a_ \geq a_n + a_m
for all m and n.
The ter ...
for real-valued functions. It is contrasted to
subadditive set function 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 ...
.
Definition
Let
be a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
and
be a
set function
In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line \R \cup \, which consists of the real numbers \R a ...
, where
denotes the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of
. The function ''f'' is ''superadditive'' if for any pair of disjoint subsets
of
, we have
.
See also
*
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 i ...
Citations
{{reflist
Combinatorial optimization
Approximation algorithms