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

$$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	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