## You are here

Homemultivalued function

## Primary tabs

# 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. $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, $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$.

## Mathematics Subject Classification

03E20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections