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:AP(B), the power setMathworldPlanetmath of B, such that f(a) is non-empty for every aA. Let us denote f:AB 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 aA.

From this definition, we see that every function f:AB is naturally associated with a multivalued function f*:AB, given by

f*(a)={f(a)}.

Thus a function is just a single-valued multivalued function, and vice versa.

As another example, suppose f:AB is a surjective function. Then f-1:BA defined by f-1(b)={aAf(a)=b} is a multivalued function.

Another way of looking at a multivalued function is to interpret it as a special type of a relationMathworldPlanetmath, called a total relation. A relation R from A to B is said to be total if for every aA, there exists a bB such that aRb.

Given a total relation R from A to B, the function fR:AB given by

fR(a)={bBaRb}

is multivalued. Conversely, given f:AB, the relation Rf from A to B defined by

aRfb  iff  bf(a)

is total.

Basic notions such as functionalPlanetmathPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath, injectivity and surjectivity on functions can be easily translated to multivalued functions:

Definition. A multivalued function f:AB is injectivePlanetmathPlanetmath if f(a)=f(b) implies a=b, absolutely injective if ab implies f(a)f(b)=, and surjective if every bB belongs to some f(a) for some aA. If f is both injective and surjective, it is said to be bijectiveMathworldPlanetmath.

Given f:AB and g:BC, then we define the composition of f and g, written gf:AC, by setting

(gf)(a):={cCcg(b) for some bf(a)}.

It is easy to see that Rgf=RgRf, where the on the right hand side denotes relational compositionPlanetmathPlanetmath.

For a subset SA, if we define f(S)={bBbf(s) for some sS}, then f:AB is surjective iff f(A)=B, and functional composition has a simplified and familiar form:

(gf)(a)=g(f(a)).

A bijective multivalued function i:AA is said to be an identityPlanetmathPlanetmathPlanetmath (on A) if ai(a) for all aA (equivalently, Rf is a reflexive relation). Certainly, the function idA on A, taking a into itself (or equivalently, {a}), is an identity. However, given A, there may be more than one identity on it: f: given by f(n)={n,n+1} is an identity that is not id. An absolute identity on A is necessarily idA.

Suppose i:AA, we have the following equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath characterizations of an identity:

  1. 1.

    i is an identity on A

  2. 2.

    f(x)(fi)(x) for every f:AB and every xA

  3. 3.

    g(y)(ig)(y) for all g:CA and yC

To see this, first assume i is an identity on A. Then xi(x), so that f(x)f(i(x)). Conversely, idA(x)(idAi)(x) implies that {x}idA(i(x))={yyi(x)}, so that xi(x). This proved the equivalence of (1) and (2). The equivalence of (1) and (3) are established similarly.

A multivalued function g:BA is said to be an inversePlanetmathPlanetmath of f:AB if fg is an identity on B and gf is an identity on A. If f possesses an inverse, it must be surjective. Given that f:AB is surjective, the multivalued function f-1:BA defined by f-1(b)={aAbf(a)} is an inverse of f. Like identities, inverses are not unique.

Remark. More generally, one defines a multivalued partial function (or partial multivalued function) f from A to B, as a multivalued function from a subset of A to B. The same notation f:AB is used to mean that f is a multivalued partial function from A to B. A multivalued partial function f:AB can be equivalently characterized, either as a function f:AP(B), where f(a) is undefined iff f(a)=, or simply as a relation Rf from A to B, where aRfb iff f(a) is defined and bf(a). Every partial functionMathworldPlanetmath f:AB has an associated multivalued partial function f*:AB, so that f*(a) is defined and is equal to {b} iff f(a) is and f(a)=b.

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