# 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 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)=\{f(a)\}.$

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)=\{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

 $aR_{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\neq 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):=\{c\in C\mid c\in g(b)\mbox{ 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)\mbox{ 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 $id_{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 $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. 1.

$i$ is an identity on $A$

2. 2.

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

3. 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, $id_{A}(x)\subseteq(id_{A}\circ i)(x)$ implies that $\{x\}\subseteq id_{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)=\varnothing$, or simply as a relation $R_{f}$ from $A$ to $B$, where $aR_{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 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