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\to P(B)$, the power set^{} of $B$, such that $f(a)$ is nonempty for every $a\in A$. Let us denote $f:A\Rightarrow B$ the multivalued function $f$ from $A$ to $B$.
A multivalued function is said to be singlevalued if $f(a)$ is a singleton for every $a\in A$.
From this definition, we see that every function $f:A\to B$ is naturally associated with a multivalued function ${f}^{*}:A\Rightarrow B$, given by
$${f}^{*}(a)=\{f(a)\}.$$ 
Thus a function is just a singlevalued multivalued function, and vice versa.
As another example, suppose $f:A\to B$ is a surjective function. Then ${f}^{1}:B\Rightarrow A$ defined by ${f}^{1}(b)=\{a\in A\mid 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\in A$, there exists a $b\in B$ such that $aRb$.
Given a total relation $R$ from $A$ to $B$, the function ${f}_{R}:A\Rightarrow B$ given by
$${f}_{R}(a)=\{b\in B\mid aRb\}$$ 
is multivalued. Conversely, given $f:A\Rightarrow B$, the relation ${R}_{f}$ from $A$ to $B$ defined by
$$a{R}_{f}b\mathit{\hspace{1em}\hspace{1em}}\text{iff}\mathit{\hspace{1em}\hspace{1em}}b\in f(a)$$ 
is total.
Basic notions such as functional^{} composition^{}, injectivity and surjectivity on functions can be easily translated to multivalued functions:
Definition. A multivalued function $f:A\Rightarrow B$ is injective^{} if $f(a)=f(b)$ implies $a=b$, absolutely injective if $a\ne b$ implies $f(a)\cap f(b)=\mathrm{\varnothing}$, and surjective if every $b\in B$ belongs to some $f(a)$ for some $a\in A$. If $f$ is both injective and surjective, it is said to be bijective^{}.
Given $f:A\Rightarrow B$ and $g:B\Rightarrow C$, then we define the composition of $f$ and $g$, written $g\circ f:A\Rightarrow C$, by setting
$$(g\circ f)(a):=\{c\in C\mid c\in g(b)\text{for some}b\in f(a)\}.$$ 
It is easy to see that ${R}_{g\circ f}={R}_{g}\circ {R}_{f}$, where the $\circ $ on the right hand side denotes relational composition^{}.
For a subset $S\subseteq A$, if we define $f(S)=\{b\in B\mid b\in f(s)\text{for some}s\in S\}$, then $f:A\Rightarrow B$ is surjective iff $f(A)=B$, and functional composition has a simplified and familiar form:
$$(g\circ f)(a)=g(f(a)).$$ 
A bijective multivalued function $i:A\Rightarrow A$ is said to be an identity^{} (on $A$) if $a\in i(a)$ for all $a\in A$ (equivalently, ${R}_{f}$ is a reflexive relation). Certainly, the function $i{d}_{A}$ 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:\mathbb{Z}\to \mathbb{Z}$ given by $f(n)=\{n,n+1\}$ is an identity that is not $i{d}_{\mathbb{Z}}$. An absolute identity on $A$ is necessarily $i{d}_{A}$.
Suppose $i:A\Rightarrow A$, we have the following equivalent^{} characterizations of an identity:

1.
$i$ is an identity on $A$

2.
$f(x)\subseteq (f\circ i)(x)$ for every $f:A\Rightarrow B$ and every $x\in A$

3.
$g(y)\subseteq (i\circ g)(y)$ for all $g:C\Rightarrow A$ and $y\in C$
To see this, first assume $i$ is an identity on $A$. Then $x\in i(x)$, so that $f(x)\subseteq f(i(x))$. Conversely, $i{d}_{A}(x)\subseteq (i{d}_{A}\circ i)(x)$ implies that $\{x\}\subseteq i{d}_{A}(i(x))=\{y\mid y\in i(x)\}$, so that $x\in i(x)$. This proved the equivalence of (1) and (2). The equivalence of (1) and (3) are established similarly.
A multivalued function $g:B\Rightarrow A$ is said to be an inverse^{} of $f:A\Rightarrow B$ if $f\circ g$ is an identity on $B$ and $g\circ f$ is an identity on $A$. If $f$ possesses an inverse, it must be surjective. Given that $f:A\Rightarrow B$ is surjective, the multivalued function ${f}^{1}:B\Rightarrow A$ defined by ${f}^{1}(b)=\{a\in A\mid b\in f(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:A\Rightarrow B$ is used to mean that $f$ is a multivalued partial function from $A$ to $B$. A multivalued partial function $f:A\Rightarrow B$ can be equivalently characterized, either as a function ${f}^{\prime}:A\to P(B)$, where ${f}^{\prime}(a)$ is undefined iff ${f}^{\prime}(a)=\mathrm{\varnothing}$, or simply as a relation ${R}_{f}$ from $A$ to $B$, where $a{R}_{f}b$ iff $f(a)$ is defined and $b\in f(a)$. Every partial function^{} $f:A\to B$ has an associated multivalued partial function ${f}^{*}:A\Rightarrow B$, 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  20130322 18:36:26 
Last modified on  20130322 18:36:26 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  15 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03E20 
Synonym  multivalued 
Synonym  multiplevalued 
Synonym  multiple valued 
Synonym  singlevalued 
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 