multivalued function
Let us recall that a function f from a set A to a set B is an assignment that takes each element of A to a unique element of B. 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 f from a set A to a set B is a function f:A→P(B), the power set of B, such that f(a) is non-empty for every a∈A. Let us denote f:A⇒B the multivalued function f from A to B.
A multivalued function is said to be single-valued if f(a) is a singleton for every a∈A.
From this definition, we see that every function f:A→B is naturally associated with a multivalued function f*:A⇒B, given by
f*(a)={f(a)}. |
Thus a function is just a single-valued multivalued function, and vice versa.
As another example, suppose f:A→B is a surjective function. Then f-1:B⇒A defined by f-1(b)={a∈A∣f(a)=b} 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 R from A to B is said to be total if for every a∈A, there exists a b∈B such that aRb.
Given a total relation R from A to B, the function fR:A⇒B given by
fR(a)={b∈B∣aRb} |
is multivalued. Conversely, given f:A⇒B, the relation Rf from A to B defined by
aRfb |
is total.
Basic notions such as functional composition
, injectivity and surjectivity on functions can be easily translated to multivalued functions:
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 .
Suppose , we have the following equivalent characterizations of an identity:
-
1.
is an identity on
-
2.
for every and every
-
3.
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 .
Title | multivalued function |
Canonical name | MultivaluedFunction |
Date of creation | 2013-03-22 18:36:26 |
Last modified on | 2013-03-22 18:36:26 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 15 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03E20 |
Synonym | multi-valued |
Synonym | multiple-valued |
Synonym | multiple valued |
Synonym | single-valued |
Synonym | single valued |
Synonym | partial multivalued function |
Related topic | Multifunction |
Defines | multivalued |
Defines | singlevalued |
Defines | total relation |
Defines | multivalued partial function |
Defines | injective |
Defines | surjective |
Defines | bijective |
Defines | identity |
Defines | inverse |
Defines | absolutely injective |