Definition:Left-Total Relation/Multifunction

From ProofWiki
Jump to navigation Jump to search


A multifunction is a left-total relation $\RR$ which is specifically not many-to-one or one-to-one.

That is, for each element $s$ of the domain of $\RR$, there exists more than one $t$ in the codomain of $\RR$ such that $\tuple {s, t} \in \RR$.

Hence a multifunction is not strictly speaking a mapping.

However, if $\RR$ is regarded as a mapping from $S$ to the power set of $T$, then left-totality of $\RR$ is the same as totality of this lifted function.

See the definition of a direct image mapping.


Let $A$ and $B$ be sets.

Let $f: A \to B$ be a multifunction on $A$.

Let $\family {S_i}_{i \mathop \in I}$ be a partitioning of the codomain of $f$ such that:

$\forall i \in I: f \restriction_{A \times S_i}$ is a mapping.

Then each $f \restriction_{A \times S_i}$ is a branch of $f$.

Also known as

A multifunction is also known as a many-valued function, a multiple-valued function or a multi-valued function.

On $\mathsf{Pr} \infty \mathsf{fWiki}$ the terse form multifunction is preferred.

When the number of values is known to be $n$, the multifunction can be referred to as an $n$-valued function.


Arbitrary Multifunction

Consider the implicit function:

$y^2 = x + 2$

For $x > 2$, there are $2$ values of $y$ for every $x$.

Hence on that domain $y$ is a two-valued function of $x$.

Also see

  • Results about multifunctions can be found here.