Let us recall that a function from a set to a set is an assignment that takes each element of to a unique element of . One way to generalize this notion is to remove the uniqueness aspect of this assignment, and what results is a multivalued function. Although a multivalued function is in general not a function, one may formalize this notion mathematically as a function:
Definition. A multivalued function from a set to a set is a function , the power set of , such that is non-empty for every . Let us denote the multivalued function from to .
A multivalued function is said to be single-valued if is a singleton for every .
From this definition, we see that every function is naturally associated with a multivalued function , given by
Thus a function is just a single-valued multivalued function, and vice versa.
As another example, suppose is a surjective function. Then defined by is a multivalued function.
Another way of looking at a multivalued function is to interpret it as a special type of a relation, called a total relation. A relation from to is said to be total if for every , there exists a such that .
Given a total relation from to , the function given by
is multivalued. Conversely, given , the relation from to defined by
Definition. A multivalued function is injective if implies , absolutely injective if implies , and surjective if every belongs to some for some . If is both injective and surjective, it is said to be bijective.
Given and , then we define the composition of and , written , by setting
It is easy to see that , where the on the right hand side denotes relational composition.
For a subset , if we define , then is surjective iff , and functional composition has a simplified and familiar form:
A bijective multivalued function is said to be an identity (on ) if for all (equivalently, is a reflexive relation). Certainly, the function on , taking into itself (or equivalently, ), is an identity. However, given , there may be more than one identity on it: given by is an identity that is not . An absolute identity on is necessarily .
is an identity on
for every and every
for all and
To see this, first assume is an identity on . Then , so that . Conversely, implies that , so that . This proved the equivalence of (1) and (2). The equivalence of (1) and (3) are established similarly.
A multivalued function is said to be an inverse of if is an identity on and is an identity on . If possesses an inverse, it must be surjective. Given that is surjective, the multivalued function defined by is an inverse of . Like identities, inverses are not unique.
Remark. More generally, one defines a multivalued partial function (or partial multivalued function) from to , as a multivalued function from a subset of to . The same notation is used to mean that is a multivalued partial function from to . A multivalued partial function can be equivalently characterized, either as a function , where is undefined iff , or simply as a relation from to , where iff is defined and . Every partial function has an associated multivalued partial function , so that is defined and is equal to iff is and .
|Date of creation||2013-03-22 18:36:26|
|Last modified on||2013-03-22 18:36:26|
|Last modified by||CWoo (3771)|
|Synonym||partial multivalued function|
|Defines||multivalued partial function|