Set-valued map - Ciallo Wiki

1. Basic Definitions and Examples

1.1 Set-valued maps (correspondences) and notation

Let \(X\) and \(Y\) be sets. A set-valued map (or correspondence) \(F\) from \(X\) to \(Y\) assigns to each point \(x\in X\) a subset \(F(x)\subseteq Y\). The defining feature is that \(F(x)\) may contain several elements, rather than exactly one.

A common convention is to write \[ F: X \rightrightarrows Y,\quad x \mapsto F(x). \] In many applications one assumes \(F(x)\neq\varnothing\) on a specified region of \(X\), but allowing empty values is sometimes useful, particularly when modeling constraints that may be infeasible.

1.2 Graphs, domains, and images

The graph of \(F\) is the set of pairs \[ \operatorname{Gr}(F)=\{(x,y)\in X\times Y:\ y\in F(x)\}. \] The domain of \(F\) is typically taken as the set of \(x\) for which \(F(x)\) is defined or nonempty (depending on the author’s convention). The image or range of \(F\) is often described by the union of its values: \[ F(X)=\bigcup_{x\in X} F(x)\subseteq Y. \]

1.3 Examples: constraints, solution sets, and “choice” correspondences

A standard source of correspondences is the conversion of an equation or inequality into a solution set.

Constraint map (feasible choices): Given a constraint system \(g(x,y)\le 0\), define

\[ F(x)=\{y\in Y:\ g(x,y)\le 0\}. \] Here \(F(x)\) represents all choices of \(y\) that satisfy the constraint for the parameter \(x\).

Argmin/argmax correspondence: For a function \(f:X\times Y\to \mathbb{R}\), define

\[ F(x)=\operatorname{argmin}_{y\in Y} f(x,y). \] When the minimizer is not unique, \(F(x)\) is a set of minimizers.

Preference or outcome sets: In decision problems, different criteria or uncertainty can yield a set of plausible outcomes. A correspondence can model this set directly, without committing to a single element.

1.4 Single-valued maps as a special case

Any ordinary function \(f:X\to Y\) can be viewed as a correspondence by identifying it with singleton values: \[ F(x)=\{f(x)\}. \] Many properties for correspondences reduce to their classical analogues in this special case, while still allowing the added flexibility needed for multiple outcomes.

2. Operations on Set-valued Maps

2.1 Pointwise set operations

Given correspondences \(F,G: X \rightrightarrows Y\), pointwise operations produce new correspondences.

2.1.1 Union and intersection of images

Define \[ (F\cup G)(x)=F(x)\cup G(x),\qquad (F\cap G)(x)=F(x)\cap G(x). \] These operations preserve the set-valued nature automatically. If one allows empty sets, then \(F(x)\cap G(x)\) may be empty even when both values are nonempty.

2.2 Composition and pullbacks

Composition generalizes the classical idea of feeding outputs into subsequent mappings, but now “outputs” are sets.

2.2.1 Composition with single-valued maps

If \(H:Y\to Z\) is single-valued and \(F:X\rightrightarrows Y\) is set-valued, then the composed correspondence \(H\circ F\) can be defined by \[ (H\circ F)(x)=\{H(y): y\in F(x)\}. \] Similarly, if \(G:W\rightrightarrows X\) is set-valued and \(f:X\to Y\) is single-valued, one may define \[ (F\circ f)(w)=F(f(w)) \] in the appropriate directional sense.

2.2.2 Image and inverse-image constructions

For a subset \(A\subseteq Y\), the image of \(A\) under \(F\) is naturally \[ F(A)=\bigcup_{x\in A} F(x)\subseteq Y, \] while the inverse image (or preimage) of \(A\) is often defined using either pointwise intersection or membership conditions. One common set-valued inverse-image notion is \[ F^{-1}(A)=\{x\in X:\ F(x)\cap A\neq\varnothing\}, \] interpreting membership as “there exists an output landing in \(A\).” Variants appear depending on whether one wants “all outputs lie in \(A\)” or “at least one output lies in \(A\).”

2.3 Restriction, extension, and trimming

- Restriction: If \(U\subseteq X\), define \(F	_U:U\rightrightarrows Y\) by \((F	_U)(x)=F(x)\) for \(x\in U\).

Trimming by values: One may define \(F_A(x)=F(x)\cap A\) to keep only outputs inside a subset \(A\subseteq Y\). This can be used to enforce additional constraints.
Extension: If \(F\) is defined on a subset of \(X\), extending it to a larger set requires specifying new values (often set to \(\varnothing\) where undefined, or defined by a model).

2.4 Cartesian products and induced maps

A correspondence can be combined with additional structure by using products. If \(F:X\rightrightarrows Y\) and \(G:W\rightrightarrows Z\), one defines a correspondence on product domains by \[ (F\times G)(x,w)=F(x)\times G(w), \] yielding a set of pairs in \(Y\times Z\). This pattern is useful in multistage models where decisions are bundled.

3. Graphical and Set-Theoretic Viewpoint

3.1 The graph of a correspondence

Working with \(\operatorname{Gr}(F)\subseteq X\times Y\) provides a unified way to encode the mapping without choosing a topology yet. Statements about \(F\) often translate to statements about properties of \(\operatorname{Gr}(F)\), such as closedness or compactness, once topological or metric structures are present.

3.2 Fibers and selections

For a fixed \(x\in X\), the set \(F(x)\) is the fiber of the graph over \(x\). Conversely, for fixed \(y\in Y\), the set of \(x\) compatible with \(y\) is a fiber of the inverse relation.

3.2.1 Selection functions (single-valued choices)

A selection of \(F\) is a single-valued function \(f:X\to Y\) such that \[ f(x)\in F(x)\quad \text{for all }x\in X \] (typically wherever \(F(x)\) is nonempty). Selections convert the set-valued description into an explicit choice. Not every correspondence admits a selection with desirable regularity (continuity, measurability, etc.), which motivates the study of selection theorems.

3.3 Closedness and other properties of the graph

In a topological setting, a correspondence is often described through the geometry of its graph. For instance, when \(X\) and \(Y\) are topological spaces, closedness of \(\operatorname{Gr}(F)\) can serve as a basic regularity condition. Other properties may be expressed using compactness of values, local boundedness, or graph-like constraints.

3.4 Representations via inequalities and constraints (set-membership form)

Correspondences frequently arise by rewriting constraints in set-membership language: \[ y\in F(x)\quad \Longleftrightarrow\quad \Phi(x,y)\ \text{holds}, \] for some predicate \(\Phi\). Inequality systems, complementarity conditions, and feasibility regions can all be encoded this way, which makes the correspondence framework compatible with optimization and variational analysis.

4.1 Topological preliminaries

Continuity notions for set-valued maps generalize the classical idea of “small changes in input lead to small changes in output,” but the output is a set. As a result, several inequivalent but related concepts exist, capturing different aspects of stability: persistence of nearby outputs, and avoidance of sudden jumps.

4.2 Upper and lower semicontinuity

Two central notions are upper semicontinuity and lower semicontinuity.

4.2.1 Definitions via neighborhood conditions

Let \(x\in X\). Upper semicontinuity (informally) prevents outputs from “escaping” to far-away regions when \(x\) varies slightly; lower semicontinuity prevents outputs from “disappearing” near a target point.

Neighborhood-based formulations are common. For example, upper semicontinuity can be described by requiring that for every open set \(V\subseteq Y\) with \(F(x)\subseteq V\), there exists a neighborhood \(U\) of \(x\) such that \(F(x')\subseteq V\) for all \(x'\in U\). Lower semicontinuity can be described using neighborhoods that intersect \(F(x)\): roughly, if an output neighborhood intersects \(F(x)\), then nearby inputs still have outputs intersecting it.

4.2.2 Equivalent characterizations (e.g., closedness of inverse images)

In many settings these neighborhood definitions admit equivalent descriptions using closedness properties. One frequently used reformulation links upper semicontinuity to the closedness of certain inverse-image constructions. Analogous equivalences relate lower semicontinuity to openness of certain “reachability” sets.

4.3 Continuity of correspondences

A correspondence is often called continuous when both upper and lower semicontinuity hold. Since these properties control different failure modes, imposing both yields a stronger notion akin to classical continuity for single-valued functions.

4.4 Lipschitz-like and metric notions (where applicable)

In metric spaces, one can define Lipschitz-type bounds for correspondences using distances between sets. These notions are used to quantify how fast the images \(F(x)\) move as \(x\) changes. Depending on the exact definition (e.g., using Hausdorff distance or other set distances), the resulting conditions may guarantee existence, stability, or convergence behavior in iterative schemes.

4.5 Set-valued maps in metric spaces: distance-to-set perspectives

Distance-to-set functions provide a bridge between set-valued behavior and real-valued analysis. Given \(A\subseteq Y\), the function \(y\mapsto d(y,A)\) measures how far a point is from the set. By combining such distances with the dependence \(A=F(x)\), one can re-express semicontinuity and regularity conditions in metric terms, facilitating estimates and proofs.

5. Measurability and Selection Theorems

5.1 Measurable correspondences

When \(X\) carries a \(\sigma\)-algebra and \(Y\) carries a measurable structure, the correspondence \(F\) becomes measurable if events determined by membership in \(F(x)\) are measurable.

5.1.1 Measurability criteria in common settings

A typical criterion is expressed through the measurability of sets like \[ \{x\in X:\ F(x)\cap V\neq\varnothing\} \] for open \(V\subseteq Y\), or through measurable selections of support functions. In well-behaved spaces (e.g., Polish spaces under suitable \(\sigma\)-algebras), these criteria often coincide with more technical definitions involving graphs.

In some applications, exact selections are hard to obtain, so one constructs approximate selections that choose elements close to the set \(F(x)\) in an appropriate sense. Refinement procedures can turn a rough correspondence into one with better measurable or continuity properties by shrinking values or replacing them with nearby sets.

5.3 Existence of selections (overview-level results)

Selection theorems supply conditions under which a correspondence admits a selection that is measurable or continuous. The overarching pattern is: if the correspondence has enough regularity (e.g., closed graph, compact values, or suitable semicontinuity), then some form of selection exists. Existence may fail when values behave too irregularly or when measurability structure is insufficient.

5.4 Criteria ensuring continuous or measurable selections

Specific criteria often combine compactness, semicontinuity, and topological regularity. For continuous selection, semicontinuity plus a structure that prevents “topological obstructions” can be relevant. For measurable selections, graph measurability or measurable projections typically play a central role. The exact hypotheses vary by setting, but the goal is always to ensure the correspondence can be represented by an admissible single-valued choice.

6. Fixed Points and Iteration

6.1 Fixed points for set-valued maps

A fixed point for a correspondence \(F:X\rightrightarrows X\) is a point \(x\in X\) such that \[ x\in F(x). \] This generalizes the classical fixed point equation \(x=f(x)\), now allowing multiple candidate updates.

6.1.1 Definition: x belonging to F(x)

The condition \(x\in F(x)\) can be interpreted as: choosing the next state from the allowable set includes the current state. In applications, this often models equilibrium, consistency, or self-compatibility.

6.2 Set-valued iterations and reachable sets

Iteration schemes for correspondences typically produce reachable sets rather than single trajectories. Starting from an initial set \(S_0\subseteq X\), one may define \[ S_{n+1}=\bigcup_{x\in S_n} F(x), \] so \(S_n\) collects all states that can be reached in \(n\) steps by choosing outputs from the sets \(F(x)\). Such dynamics are used when actions are non-deterministic or when uncertainty is represented explicitly.

6.3 Typical hypotheses used in fixed-point existence (high-level)

Fixed point existence results for correspondences usually require some combination of:

compactness or boundedness of values,
semicontinuity of the correspondence,
a convexity-type structure on \(X\) (in vector spaces or ordered settings),
and sometimes condensing or contractive behavior under an appropriate measure of noncompactness.

The detailed hypotheses depend on the theorem, but the theme is that these properties prevent “escape” and enable the identification of an \(x\) that is compatible with its own image set.

6.4 Stability and perturbation viewpoints (conceptual)

Perturbation arguments ask how fixed points change when the correspondence is modified. With appropriate continuity assumptions (upper/lower semicontinuity or metric regularity), one can often prove that approximate fixed points persist or that limit points of approximate solutions are true fixed points.

7. Convergence and Limits

7.1 Modes of convergence for correspondences

Convergence for set-valued maps is not unique because set outputs can vary in multiple ways. One must distinguish whether convergence is based on distances, on sequences of points selected from the values, or on topological behavior of the graphs.

7.2 Kuratowski limits and limsup/liminf of sets

For sequences of sets \(A_n\subseteq Y\), the limsup consists of points that can be approached by points from \(A_n\) infinitely often, while the liminf consists of points that eventually always belong to neighborhoods determined by the sets. These constructs generalize notions of set convergence beyond pointwise membership.

7.3 Convergence of graphs (graphical convergence)

Graphical convergence treats the correspondence as its graph in \(X\times Y\). One considers convergence of \(\operatorname{Gr}(F_n)\) to \(\operatorname{Gr}(F)\) in a topological or variational sense. This approach aligns well with semicontinuity properties and often yields stable conclusions about limit behavior of solutions.

7.4 Stability of semicontinuity under limits

When correspondences \(F_n\) converge, it is natural to ask whether upper semicontinuity or lower semicontinuity is preserved in the limit. Under suitable uniformity or compactness assumptions, semicontinuity can be stable, ensuring that limiting sets do not develop new discontinuities.

8. Applications and Modeling Patterns

8.1 Optimization and argmin/argmax mappings

In optimization, the objective landscape determines a correspondence of minimizers or maximizers. The mapping \(x\mapsto \operatorname{argmin}_y f(x,y)\) is a central example because:

it captures multiple optimal solutions,
it naturally encodes constraints through feasible sets,
and its continuity/semicontinuity properties reflect how solutions vary with parameters.

8.2 Feasibility correspondences and constraint solving

Many constraint satisfaction tasks can be written as feasibility sets: \[ F(x)=\{y:\ \text{constraints relating }x\text{ and }y\}. \] Then solving the task becomes selecting a feasible element from \(F(x)\), or finding fixed points that correspond to consistent constraints.

8.3 Multivalued relations as models of uncertainty

In modeling, uncertainty may lead to a distribution over outcomes or, in more deterministic frameworks, to a set of possible outcomes. A correspondence can represent a “robust” or “admissible” set of answers for each input, supporting worst-case reasoning or conservative guarantees.

8.4 Order-theoretic interpretations (relations as correspondences)

Set-valued maps generalize relations. When outputs are ordered or partially ordered, correspondences can be studied using monotonicity notions. In order-theoretic contexts, fixed points of correspondences correspond to equilibria or least/greatest solutions of recursive constraints.

9. Notation, Edge Cases, and Conventions

9.1 Empty values and domain restrictions

Allowing \(F(x)=\varnothing\) introduces useful flexibility but requires care. Many theorems assume nonempty values on a relevant subset of the domain. When empty values occur, statements about selections or fixed points must be interpreted on regions where solutions exist.

9.2 Nonemptiness assumptions (when and why)

Nonemptiness is often required to define selections, to guarantee existence of solutions, and to make certain continuity notions meaningful in a strong sense. For example, if values can be empty, then upper semicontinuity may hold vacuously while lower semicontinuity fails in a way that reflects actual infeasibility.

9.3 Relationship to relations and inverse relations

A relation \(R\subseteq X\times Y\) can be identified with a correspondence by defining \[ F_R(x)=\{y\in Y:\ (x,y)\in R\}. \] Conversely, the graph of a correspondence is a relation. Inverse relations correspond to “switching roles” of \(X\) and \(Y\), which is useful when discussing preimages and compatibility sets.

9.4 Common notational conventions in the literature

Different authors use different symbols and conventions for:

whether empty values are allowed,
whether the notation emphasizes set inclusion or existence,
and which semicontinuity direction is labeled “upper” versus “lower.”

Despite these variations, the underlying structures are consistent: represent the mapping via its graph, define properties via set behavior, and translate regularity into continuity-like concepts.