1 Definition and basic intuition

A multivalued inverse generalizes the idea of an inverse of a function or relation. In ordinary inverse problems, one starts from an output and seeks a single input that produced it. When the original rule is not one-to-one, that “output” may arise from many different inputs; the multivalued inverse records all such candidates.

Formally, if a relation \(R\) connects inputs to outputs, then its multivalued inverse is obtained by exchanging the roles of inputs and outputs. The result can be viewed as a new relation that, for each original output, relates it to every original input that could yield it.

1.1 Inverse of a relation vs. inverse of a function

A function inverse is typically discussed only when the function is bijective (or when a single branch of an inverse is selected). For relations, no such restriction is needed: every relation has an inverse relation formed by swapping ordered pairs. The multivalued aspect appears naturally because a relation may map one input to multiple outputs, or multiple inputs to one output.

When the original rule is a function \(f\), the multivalued inverse is especially intuitive: it maps a target value to the entire set of preimages under \(f\). This set-valued response captures non-injectivity without forcing a unique answer.

1.2 Set-valued (multivalued) viewpoint

The “multivalued” designation comes from treating the inverse not as a single-valued rule but as a correspondence that returns a set. For a given output \(y\), the multivalued inverse returns all \(x\) such that the original rule maps \(x\) to \(y\). Thus, the codomain of the inverse is naturally interpreted as a collection of subsets of the original domain.

1.3 Connection to preimages

The multivalued inverse is closely tied to preimages. For a function \(f\), the set of elements mapped into \(y\) is called the preimage of \(y\): \[ f^{-1}(\{y\})=\{x : f(x)=y\}. \] This preimage set is precisely what the multivalued inverse assigns to \(y\). For general relations, the same idea holds: the inverse relation relates \(y\) to every \(x\) that lies in the preimage of \(y\).

1.4 Notation and terminology

Different fields use slightly different notation. A common convention for a function \(f\) is to write \(f^{-1}(y)\) to mean the set of solutions to \(f(x)=y\), even though \(f^{-1}\) is not a true function unless \(f\) is injective. In relational settings, one writes \(R^{-1}\) for the inverse relation, where \[ R^{-1}=\{(y,x) : (x,y)\in R\}. \] The terms “inverse relation,” “multivalued inverse,” and “set-valued inverse mapping” are frequently used to emphasize that outputs correspond to sets of inputs.

2 Multivalued inverses in relational form

2.1 Swapping ordered pairs

For a relation \(R \subseteq X\times Y\), the inverse relation is \[ R^{-1} \subseteq Y\times X, \] defined by swapping each ordered pair’s coordinates. Each \((x,y)\) in \(R\) becomes \((y,x)\) in \(R^{-1}\). This definition works uniformly whether \(R\) is functional, one-to-one, many-to-one, or highly non-deterministic.

2.2 Inverse relation properties

Inversion is a basic symmetry operation on relations. Many properties can be expressed in terms of how inversion interacts with other relation constructions.

2.2.1 Involutive behavior (inverse of inverse)

Inverting twice returns the original relation: \[ (R^{-1})^{-1} = R. \] This “involution” property reflects the fact that swapping ordered pairs twice restores their original order.

2.3 Domain and range exchange under inversion

In a relation, the domain consists of elements that appear as the first component of some ordered pair, while the range consists of elements that appear as the second component. Under inversion, these roles swap. Concretely, the domain of \(R^{-1}\) corresponds to the range of \(R\), and the range of \(R^{-1}\) corresponds to the domain of \(R\). This exchange is one reason the multivalued inverse is often described as “turning around” the direction of mapping.

2.4 Composition with inverses

Relation composition interacts naturally with inversion. If \(R\subseteq X\times Y\) and \(S\subseteq Y\times Z\), then \[ (S\circ R)^{-1} = R^{-1}\circ S^{-1}. \] This identity shows how reversing a composite process corresponds to composing the reversed pieces in the opposite order. It provides a convenient algebraic tool for reasoning about multistep preimage computations.

3 Multivalued inverses as set-valued functions

3.1 Defining a set-valued inverse mapping

When the original rule is a function \(f: X\to Y\), one can define a set-valued inverse mapping \(f^{-1}\) that assigns to each \(y\in Y\) the set of inputs producing it: \[ f^{-1}(y)=\{x\in X : f(x)=y\}. \] This does not create a conventional inverse function unless each \(y\) has at most one preimage and every \(y\) has exactly one preimage, i.e., unless \(f\) is bijective.

3.2 Output as a set of all preimages

The defining feature is that the “output” of the inverse is a set rather than a single element. Even when \(f\) is deterministic, the inverse correspondence is generally non-deterministic: different inputs may collapse to the same output under \(f\), producing multiple elements in \(f^{-1}(y)\).

3.3 Empty set cases and interpretation

For some \(y\in Y\), it may happen that no input maps to \(y\). In that case, \[ f^{-1}(y)=\varnothing. \] Interpreting this outcome is straightforward: the multivalued inverse returns the empty candidate set, meaning the original rule cannot produce that value.

In relational terms, the same phenomenon occurs: if \(y\) never appears as a second component in \(R\), then \((y,\cdot)\) pairs do not exist in \(R^{-1}\).

3.4 Non-uniqueness and ambiguity

If \(y\) has multiple preimages, the inverse mapping necessarily returns a set with more than one element. Any downstream selection—such as choosing one preimage based on additional criteria—requires extra structure beyond the multivalued inverse itself. Without such criteria, the inverse is best regarded as “all consistent inputs,” not as a unique recovered input.

4 Examples and worked mini-cases

4.1 Simple non-injective mappings

Let \(f:\mathbb{R}\to\mathbb{R}\) be given by \(f(x)=x^2\). For a positive output \(y>0\), \[ f^{-1}(y)=\{\sqrt{y},-\sqrt{y}\}, \] so the multivalued inverse returns two candidates. For \(y=0\), \[ f^{-1}(0)=\{0\}, \] and for \(y<0\), \[ f^{-1}(y)=\varnothing, \] since no real square equals a negative number.

4.2 Many-to-one correspondences

Consider a relation that groups several inputs under a shared label. For instance, let \(X=\{a,b,c\}\), \(Y=\{1,2\}\), and define a relation by pairing \(a\) and \(b\) with \(1\), and \(c\) with \(2\): \[ R=\{(a,1),(b,1),(c,2)\}. \] Then \[ R^{-1}=\{(1,a),(1,b),(2,c)\}. \] Viewed as a multivalued inverse, the output \(1\) corresponds to the candidate set \(\{a,b\}\), while output \(2\) corresponds to \(\{c\}\).

4.3 Constant relations and their inverses

Let \(f:X\to Y\) be constant, say \(f(x)=y_0\) for all \(x\in X\). Then:

  • For \(y=y_0\), \(f^{-1}(y_0)=X\).
  • For \(y\neq y_0\), \(f^{-1}(y)=\varnothing\).

This case highlights the extremal non-injectivity: the inverse correspondence collapses many inputs into one output and therefore returns the entire domain as the candidate set for that output.

4.4 Inverse images in toy examples

Suppose \(f:\{1,2,3,4\}\to\{A,B\}\) is defined by \(f(1)=A\), \(f(2)=A\), \(f(3)=B\), and \(f(4)=B\). Then:

  • \(f^{-1}(A)=\{1,2\}\),
  • \(f^{-1}(B)=\{3,4\}\).

If one writes the multivalued inverse mapping as a set-valued rule, it can be summarized as sending each label to the set of elements that carry it.

5 Special cases and reductions to ordinary inverses

5.1 When the inverse becomes single-valued

The multivalued inverse becomes single-valued precisely when the original rule is injective (for the function setting). If \(f\) is one-to-one, then each \(y\in f(X)\) has exactly one preimage, so \(f^{-1}(y)\) has one element. If, additionally, \(f\) is surjective, then every \(y\in Y\) has a preimage, and the inverse correspondence can be treated as an ordinary inverse function.

5.2 Bijections and exact inverses

When \(f:X\to Y\) is bijective, the multivalued inverse coincides with the usual inverse function. In that situation, each output corresponds to exactly one input and vice versa, eliminating ambiguity. The set-valued inverse reduces to singleton sets, and those singletons correspond directly to inverse-function values.

5.3 One-to-one relations with multivalued inverse

Even if a relation is one-to-one in the sense that no two distinct inputs map to the same output, the inverse may still fail to be single-valued if the original relation is not “functional” in the other direction (i.e., if an input may be related to multiple outputs). Thus, in relational contexts, one-to-one behavior depends on which direction of determinism is assumed. The multivalued inverse framework remains valid, while the conditions for collapsing to an ordinary inverse depend on the precise properties of the relation.

5.4 When no inverse exists in the traditional sense

There are cases where no ordinary inverse function exists, but a multivalued inverse still provides meaningful information. For example, non-injective functions do not have a well-defined single-valued inverse, yet the multivalued inverse always exists as a set-valued rule listing all consistent inputs. Likewise, certain relations may be too nondeterministic to admit a traditional inverse function, but their inverse relation is still well-defined by swapping ordered pairs.

6 Structural properties and logical perspectives

6.1 Order-theoretic behavior (inclusion of relations)

Inversion preserves inclusion order: if \(R_1 \subseteq R_2\) as relations, then \(R_1^{-1} \subseteq R_2^{-1}\). For set-valued inverses of functions, a related monotonicity appears when comparing candidate sets associated with different outputs or when refining the underlying rule. The key idea is that inversion does not “lose” ordered-pair information; it only redirects it.

6.2 Closure properties under operations

Because relation inversion is defined directly on ordered pairs, it behaves well under many relation-algebra operations. For instance, inversion distributes over union: \[ (R_1 \cup R_2)^{-1} = R_1^{-1} \cup R_2^{-1}. \] Similarly, it interacts predictably with composition, providing algebraic tools for constructing multistep inverse reasoning.

6.3 Relationship to equivalence relations and kernels

For functions, the kernel relation (in an appropriate algebraic setting) groups inputs that share the same output under the function. While the term “kernel” has specific meanings across mathematics, the conceptual link is that identifying equal outputs naturally produces classes of inputs. The multivalued inverse can be seen as extracting, for a particular output, the corresponding class or preimage set.

In equivalence-relation terms, inversion supports the idea of swapping viewpoint: outputs become “representatives” that determine which inputs belong to the same group under the original mapping.

6.4 Logical reading: “all values consistent with a result”

A common logical interpretation treats the multivalued inverse as a constraint extractor. Given an equation \(f(x)=y\), the multivalued inverse returns all \(x\) that satisfy it. The result is not a choice, but a statement of consistency: every element in the returned set is a witness that the original rule can produce the target value.

This viewpoint is especially helpful in constraint solving and in any setting where one needs “all solutions” rather than “the” solution.

7 Connections to broader concepts

At a high level, multivalued inverses relate to Galois connections, which connect two order structures through a pair of monotone maps that reverse inequalities. In many formulations, taking preimages is order-reversing in a way that pairs well with image-like operations. While the full theory depends on the surrounding structures, the shared theme is correspondence between “forward” constructions and their “backward” solution sets.

7.2 Constraint solving and candidate sets

In algorithmic contexts, computing \(f^{-1}(y)\) is often viewed as generating candidate solutions that meet a requirement. Whether the original rule is a mathematical function or a relational constraint, the backward step collects all admissible inputs, enabling filtering, branching, or further constraints to be applied.

7.3 Complements in relation algebra (informal)

Relation algebra often manipulates relations through complement, union, intersection, and composition. Since inversion is a structural symmetry on ordered pairs, it can be combined with these operations to express alternative viewpoints. Informally, one can think of inversion as switching “from inputs to outputs” into “from desired outputs to possible inputs,” while other operations control which pairs are included or excluded.

In a functional graph representation of a function, each node points to its image. The multivalued inverse corresponds to following edges backward: for a node \(y\), the multivalued inverse returns all predecessors \(x\) that have edges into \(y\). This aligns with the concept of backward reachability in graphs, where one explores all nodes that can lead to a target through directed steps.

8 Common pitfalls and best practices

8.1 Confusing relational inverse with reciprocal functions

A frequent source of confusion is mistaking the multivalued inverse \(R^{-1}\) or \(f^{-1}\) for a reciprocal operation (such as \(1/f(x)\)). Inverses here refer to reversing input-output dependence, not taking multiplicative reciprocals. Keeping track of whether an expression is algebraic (reciprocal) versus relational (input-output swap) prevents incorrect transformations.

8.2 Assuming uniqueness of results

Another common mistake is treating \(f^{-1}(y)\) as if it always returns a single value. For non-injective functions, the inverse correspondence generally yields multiple candidates or none. Best practice is to interpret it explicitly as a set of solutions and to only collapse to a single value after additional assumptions (like injectivity) or selection rules.

8.3 Handling units/labels and notation clashes

Notation can clash across disciplines: some fields use \(^{-1}\) for inverse matrices, reciprocals, or inverses of operators. In set-valued inverse contexts, \(f^{-1}(y)\) is not a number but a set. Clear labeling—such as specifying that the inverse is multivalued or set-valued—helps avoid misreading.

8.4 Distinguishing function inverse from relation inverse

A function inverse is a particular type of mapping with strong existence and uniqueness requirements. A relation inverse always exists as a relation by swapping ordered pairs, but it may correspond to a set-valued function only under additional structure. A practical rule is: use relation language when determinism or uniqueness is absent, and reserve function-inverse language for bijective (or appropriately restricted) cases.