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 non-empty 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 single-valued 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)=\lbrace f(a)\rbrace.$$ Thus a function is just a single-valued 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)=\lbrace a\in A \mid f(a)=b\rbrace$ 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)=\lbrace b\in B\mid aRb\rbrace$$ is multivalued. Conversely, given $f:A \Rightarrow B$ , the relation $R_f$ from $A$ to $B$ defined by $$a R_f b \qquad\mbox{iff}\qquad 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)=\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):=\lbrace c\in C\mid c\in g(b)\mbox{ for some }b\in f(a)\rbrace.$$ 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)=\lbrace b\in B\mid b\in f(s)\mbox{ for some }s\in S\rbrace$ , 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 $id_A$ on $A$ , taking $a$ into itself (or equivalently, $\lbrace a\rbrace$ ), 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)=\lbrace n,n+1\rbrace$ is an identity that is not $id_{\mathbb{Z}}$ . An absolute identity on $A$ is necessarily $id_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$

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)=\lbrace a\in A\mid b\in f(a)\rbrace$ 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':A \to P(B)$ , where $f'(a)$ is undefined iff $f'(a)=\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 $\lbrace b\rbrace$ iff $f(a)$ is and $f(a)=b$ .