This site is being phased out.

Set-valued maps

From Mathematics Is A Science
Jump to navigationJump to search

Coincidences of a pair of maps

The surjectivity question is, if $f:N\to M$ is a map, when can we guarantee that the image of $f$ is the whole $M$: $$\operatorname{Im}(f)=M?$$

This problem may appear very different from the fixed point problem but let's compare anyway.

  • Fixed point problem: For $f:M \to M$, is there $a\in M$ with $f(a)=a$?
  • Surjectivity problem: For $f:N\to M$, given $b\in M$, is there an $a\in N$ with $f(a)=b$?

The two problems are united into the following.

Coincidence Problem: Given two maps $f,g: N\to M$, do they have a coincidence, i.e., $$a\in N:f(a)=g(a)=b\in M?$$

First, setting $N:=M,g:=\operatorname{Id}_M$ gives us the fixed point problem.

Second, setting $g(x):=b$, a constant map, gives us the surjectivity problem, if solved for all $b\in M$. Since all constant maps are homotopic (when $M$ is path-connected), the positive answer -- in our homological setting -- for one value of $b$ will give us all.

This generalization is motivated by several related problems.

First, the surjectivity results in the last section rely on the degrees of the maps. Therefore, they apply only to a narrow class of maps, those between manifolds of the same dimension. The forward kinematic map of a control system (below) is a map from a high-dimensional domain space $N$, with the dimension commonly equal to the number of degrees of freedom of the robot, to the $3$-dimensional operating space.

More generally, let's consider discrete dynamical systems. In such a system, the next position or state, $f(x)$, where $f:M \to M$ is a map, depends only on the current one, $x \in M$. What if there is a parameter? Suppose the next position $f(u,x)$ depends not only on the current one, $x \in M$, but also on the input, or control, $u \in U$. Then our map becomes: $$f:N=U\times M \to M.$$ Such a parametrized dynamical system is called a control system. For example, in cruise control, $M$ is the space of all possible values of the car's speed and $U$ is the engine's possible throttle positions as they determine how much power the engine generates.

Then an equilibrium of such a system is a combination of a point $a\in M$ and an input $p\in U$ such that the point remains fixed: $$f(p,a)=a.$$ This point $(p,a) \in N$ is then a coincidence point of this map $f$ and the projection $g: N=U \times M \to M$!

Exercise. Describe the state-control space of the tether-ball:

Tetherball.png

Meanwhile, the surjectivity of the map $f$ ensures what is called the “reachability” of the control system.

Meanwhile, it is possible that, reflecting noise and other uncertainty, the dynamical system is only known imprecisely:

Set-valued dynamical system.png

It is given then by a set-valued map $F:M\to M$ in the sense that its values are subsets of $M$: $$F(x)\subset M.$$

Set-valued maps

For any two spaces $X,Y$, a set-valued map $F:X\to Y$ is a correspondence $$x\mapsto F(x)\subset Y.$$ It can also be thought of as a function to the power set of $Y$: $$F:X\to 2^Y.$$

There are more subtle examples of the emergence of set-valued maps than just uncertainty about the values of a map.

The inverse $f^{-1}:Y\to X$ of a continuous function $f:X\to Y$ doesn't, of course, have to be a continuous function.

Inverse as set-valued map.png

It can be seen as a set-valued map $f^{-1}:Y\to X$ and this map will have a certain continuity property. Indeed, its graph is the same as that of $f$ itself and, therefore, closed. It may have empty values if $f$ isn't surjective.

In fact, any set-valued map $F:X\to Y$ can be understood entirely via its graph $$\operatorname{Graph}(F)=\{(x,y):\ x\in X, y\in Y, y\in F(x)\} \subset X\times Y.$$

Set-valued map.png

Then we face the set-valued fixed point problem for $F:X\to X$: is there $x\in F(x)$? Such a point would have to lie on the diagonal of $X\times X$:

Set-valued map fixed point.png

Another area where set-values maps naturally appear is optimization. For example, for any function of two variables $f:X\times Y\to {\bf R}$ one can define a set-valued map $f^{max}:X\to Y$ by $$f^{max}(x):=\arg\max_{y\in Y}f(x,y).$$ Since the maximum value may be attained for several values of $y$, the value of $f^{max}$ isn't necessarily a single point. This set may even be empty.

Max as set-valued map.png

Proposition. Suppose $Y$ is compact and $f:X\times Y\to {\bf R}$ is continuous. Then the graph of $f^{max}$, $\operatorname{Graph}(f^{max})$, is closed and its values, $f^{max}(x)$, are non-empty.

Exercise. (a) Prove the proposition. (b) State and prove the analogue of the proposition where ${\bf R}$ is replaced with a metric space.

Recall that a function $f:X\to {\bf R}$, where $X$ is a convex subset of ${\bf R}^N$, is called convex (or concave down) if $$f(tx_1+(1-t)x_2) \ge tf(x_1)+(1-t)f(x_2),\ \forall t\in [0,1], x_1,x_2\in X.$$

Exercise. Prove that any convex function is continuous on an open set.

Proposition. If $f(x_0,\cdot)$ is convex for each $x_0\in X$, then $f^{max}$ has convex values.

Exercise. Prove the proposition.

There are set-valued maps with properties impossible for their single-valued counterparts. For example, if we identify the top and bottom of this surface, this Mobius band will serve as the graph, which is closed, of a “set-valued retraction” of the disk to the circle:

Mobius band standing up.png

This surface is illustrated by the DNA's double helix and the famous double staircase in the Vatican.

Exercise. Provide a formula for this map. Examine preimages of open sets under this map.

In order to be able to apply all the topological machinery we have developed, we interpret the set-valued map in terms of single-valued maps, as follows:

We set $N$ to be the graph of $F:X\to Y$, $$N:=\operatorname{Graph}(F)$$ and set $f,g$ to be the two projections $$f:N \to X, \ g: N\to Y.$$ When $X=Y$, our fixed point problem, again, becomes a coincidence problem: $$a\in F(a) \Leftrightarrow b=(a,a)\in N \Leftrightarrow f(b)=g(b)=a.$$

We can fully develop a theory of set-valued maps as pairs in this manner. For example, we define the composition of two set-values maps: $$F:X \to Y,\ G: Y \to Z, \ GF:X \to Z,$$ by simply letting $$GF(x):=G(F(x)).$$ This expression can be interpreted in terms of pairs of maps: $$ \newcommand{\ra}[1]{\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} \newcommand{\la}[1]{\!\!\!\!\!\xleftarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\ua}[1]{\left\uparrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ccccccc} \operatorname{Graph}(GF) & \ra{} & \operatorname{Graph}(G) & \ra{Q_Z} & Z \\ \da{} & & \ \da{Q_Y} & \nearrow_G \\ \operatorname{Graph}(F) & \ra{P_Y} & Y & \\ \ \ \da{P_X} & \nearrow_F & \\ X & \end{array} $$

Exercise. Define the inverse of a set-valued map and interpret it in terms of pairs of maps.

How do we define the homology map $F_*:H(X) \to H(Y)$ of a set-valued map $F:X\to Y$ between two polyhedra? Suppose $f:N\to X,\ g:N\to Y$ are its projections. Then $F_*$ could be defined in terms of the homology map of their combination: $$F_*:=(fg^{-1})_*:H(X) \to H(Y),$$ but only if the inverse exists! It does, for example, when one of the projections is a homeomorphism, but in that case our set-valued map is single-valued anyway. Or, the homology map of the pair $f,g$, and that of $F$, could be defined via their homology maps: $$F_*:=f_*(g_*)^{-1}:H(X) \to H(Y),$$ but only if the inverse exists! The theorem below gives us a sufficient condition when this is the case.

The Vietoris Mapping Theorem

Let's compare the homology maps of these two projections.

First, the projection of the cylinder on the circle: $$P: {\bf C}^2 = [0,1] \times {\bf S}^1 \to {\bf S}^1 .$$

Projection of cylinder on circle.png

Second, the projection of the torus on the circle: $$Q : {\bf T}^2 = {\bf S}^1\times {\bf S}^1 \rightarrow {\bf S}^1 .$$

Torus collapse.png

The homology map of the first, $$[P_1] : H_1({\bf C}^2)={\bf R} \to H_1({\bf S}^1)={\bf R},$$ is an isomorphism and that of the second, $$[Q_1] : H_1({\bf T}^2)={\bf R}^2 \to H_1({\bf S}^1)={\bf R},$$ is another projection.

Why the difference?

Clearly, $Q$ collapses the other circle to a point and, as one would expect, $[Q_1]$ “kills” its homology class. The effect of $P$ on the homology classes of the cylinder is nil.

Now, can we predict this without actually computing the homology maps?

The answer is Yes. All we have to look at is the preimages of points (aka “fibers”) of the two maps.

  • For $P$, the preimages are segments. Therefore, they are homologically trivial, acyclic.
  • For $Q$, they are circles and, therefore, not homologically trivial.

In the latter case, these cycles collapse to points and, therefore, their homology classes are lost. It remains to be shown that in the former case, there can be no such collapsing.

The following important theorem is the answer.

Theorem (Vietoris Mapping Theorem). Let $h:K \to L$ be a surjective simplicial map. Suppose that the preimages $h^{-1}(b)$ of simplicies in $L$ are acyclic subcomplexes of $K$. Then, the homology map $$h_*: H(K) ^{\underrightarrow{~\ \ \ \cong\ \ \ ~~}} H(L)$$ of $h$ is an isomorphism.

We build $(h_*)^{-1}$ -- without $h^{-1}$! We start with a vertex map $q_0:K^{(0)}\to L^{(0)}$ by choosing, arbitrarily, $q_0(A):=V\in h^{-1}(A)$. To extend it to the rest of the cells, we use the Chain Extension Theorem that we restate now as a lemma.

Lemma. Suppose $K$ and $L$ are simplicial complexes and $Q_a$ is an acyclic subcomplex of $L$ for every cell $a$ in $K$. (1) Suppose $g_0:K^{(0)}\to L^{(0)}$ is a map of vertices that satisfies the following condition: $$a=A_0A_1 ...A_n \in K \Rightarrow g_0(A_0),g_0(A_1),...,g_0(A_n) \in Q_a.$$ Then there is such a chain map (extension) $g=\{g_i\}:C(K)\to C(L)$ that $g(a) \subset Q_a$ for every cell $a$ in $K$. (2) If two chain maps $g$ and $g'$ satisfy this condition, $g(a),g'(a) \subset Q_a,a\in K$, then $g$ and $g'$ are chain homotopic, $g\simeq g'$.

Chain extension.png

We apply part (1) of the lemma to $g_0:=q_0$ with $Q_a :=h^{-1}(a)$. Then $q_0$ has a chain extension, a chain map $q:C(K)\to C(L)$, with $q(a) \subset h^{-1}(a)$ for every cell $a$ in $K$.

Exercise. Prove that $h_{\Delta}(q(a)) = a$.

It follows that $h_{\Delta}q={\rm Id}_{C(K)}$ and, furthermore, $h_{*}q_*={\rm Id}_{H(K)}$.

We apply part (2) of the lemma to $Q_a :=h^{-1}h(a)$ and the two chain maps, $g:=qh_{\Delta}$ and the identity map $g':= \operatorname{Id}_{C(L)}$ of $L$. Then these two chain maps are chain homotopic: $qh_{\Delta}\simeq \operatorname{Id}_{C(L)}$. Therefore, $q_*h_{*}= \operatorname{Id}_{H(L)}$.

Therefore, $h_*$ is invertible, which concludes the proof of the theorem.

Exercise. State the up-to-homotopy version of this theorem. Is its converse true? Hint: degrees.

The ability to “reverse” a homology map comes handy when one studies set-valued maps.

We will use the following key result without proof.

Proposition. If $h:X\to Y$ has acyclic preimages $h^{-1}(y),y\in Y$, then there is a simplicial approximation $p:K\to L$ of $h:X\to Y$ such that $p^{-1}(a)$ is acyclic for every cell $a$ in $L$.

Let $G={\rm Graph}(F)$ be the graph of a set-valued map $F:X\to Y$. It is a subset of $X \times Y$. Then there are two projections $P:G \to X$ and $Q: G \to Y$. These projections are continuous and, therefore, their homology maps $P_*,Q_*$ are well-defined -- provided all spaces involved, including the graph $G$, are polyhedra. Suppose $F$ is acyclic-valued: $F(x)$ is an acyclic subset of $Y$ for each $x \in X$.

Set-valued map -- graph and values.png

Then the preimages of $P$, $P^{-1}(x)=\{x\}\times F(x)$, are also acyclic. By the theorem, $P$ generates an isomorphism: $$P_*: H(G) ^{\underrightarrow{~\ \ \ \cong\ \ \ ~~}}H(X).$$

Definition. Given a set-valued map $F:X\to Y$ between polyhedra, with acyclic images and polyhedral graph, the homology map $F_*: H(X) \to H(Y)$ of $F$ is defined as $$F_*:=Q_*(P_*)^{-1}.$$

So, the homology operator of this set-valued map is single-valued!

Exercise. What happens to the homology maps under compositions of set-valued maps?

With the help of this construction, we can now re-interpret the homology of maps. Recall that we define the homology map of a general, not necessarily cell map, $f:X\to Y$, where $X,Y$ are two polyhedra, via a simplicial approximation of $f$ and subdivisions of the domain $X$. What if, instead, we replace map $f$ with a set-valued map? Specifically, what if the new map has whole cells as values? In other words, given a map $f: X \to Y$ define a set-valued map $F:X \to Y$ by setting $F(x)$ equal to the carrier of $f(x)$, the cell to the interior of which $f(x)$ belongs. Then $$f(x)\in F(x),\ \forall x\in X.$$

This is what the graph of a set-valued “approximation” $F$ of $f$ might look like:

Cubical set-valued approximation.png

Exercise. For a given $f$, define $F$ in such a way that the projections are cubical maps, and $F_*=f_*$.

A more general case is that of a pair of arbitrary maps $P:G \to X$ and $Q: G \to Y$, where $X,Y,G$ are polyhedra. Indeed, we can define a set-valued map $F:X\to Y$ by $F(x):=QP^{-1}$.

Suppose one of them, $P$, has acyclic preimages. Then this pair of maps, $$X \quad \xleftarrow{~\ \ \ P \ \ \ ~~} \quad G \quad \xrightarrow{~\ \ \ Q \ \ \ ~~} \quad Y, $$ produces a pair of linear operators: $$H(X) \quad \xleftarrow{~\ \ \ P_*\cong \ \ \ ~~} \quad H(G) \quad \xrightarrow{~\ \ \ Q_* \ \ \ ~~} \quad H(Y).$$ But unlike the former diagram, in the latter, the first arrow is reversible!

Definition. The homology map of the pair is defined as $$Q_*P_*^{-1}:H(X)\to H(Y).$$

The Lefschetz number of a pair of maps

What if we are to study coincidences of maps or fixed points of set-valued maps?

The homology map of the pair -- when one of them has acyclic preimages -- is: $$f_*g_*^{-1}:H(M)\to H(M).$$ Then, we can define the Lefschetz number of the pair of maps via the same trace formula: $$\Lambda (f,g):=L(f_*g_*^{-1})=\sum _n (-1)^n {\rm Tr} ([f_n][g_n]^{-1}).$$ The main result is stated without proof (see Saveliev).

Theorem (Lefschetz Coincidence Theorem). Suppose $M$ and $N$ are polyhedra and $f,g:N \to M$ are maps. Suppose also that $g$ has acyclic preimages. Then, if $$\Lambda (f,g) \ne 0,$$ then the pair has a coincidence.

The proof of the following important result relies on the Brouwer Fixed Point Theorem.

Theorem (Kakutani Fixed Point Theorem). Let $X$ be a non-empty, compact and convex subset of some Euclidean space. Let $F: X \to X$ be a set-valued map with a polyhedral graph and each $F(x)$ is non-empty and convex for all $x \in X$. Then $F$ has a fixed point: $a \in F(a)$.

Exercise. Show that this result generalizes the Brouwer Fixed Point Theorem.

Exercise. Derive the Kakutani Fixed Point Theorem from the Lefschetz Coincidence Theorem.

Another version of the Lefschetz coincidence theorem (P. Saveliev, Lefschetz coincidence theory for maps between spaces of different dimensions, Topology and Its Applications, 116 (2001) 1, 137-152) does not require acyclic preimages. We state only its corollary: the following homological solution to the surjectivity problem.

Theorem (Surjectivity Theorem). Suppose $N$ is a polyhedron, $M$ is an orientable compact connected manifold, $\dim M=n$, and $f:N \to M$ is a map. If $$[f_n]: H_{n}(N) \to H_{n}(M)$$ is nonzero, then every map homotopic to $f$ is onto.

Exercise. Show that this result generalizes the surjectivity theorem for maps of non-zero degree.

Motion planning in robotics

Recall that the configuration space of a two-joint robotic arm is the torus: $${\bf T}^2={\bf S}^1 \times {\bf S}^1 .$$

Rotating rod 2.png

Its operational space is parametrized by the locations of its end: $$x=R_1\cos \phi_1 + R_2 \cos\phi_2,\ y=0,\ z=R_1\sin \phi_1 + R_2 \sin\phi_2.$$ Under the assumption $R_1>R_2$, the operational space is the annulus. Since these functions are periodic, they can be seen combined as a map from the torus to the space.

It is an example of the forward kinematics map of a robot, i.e., the map from its configuration space to the operational space that associates a location of the end of the arm to each configuration.

Exercise. A telescoping arm with a joint has the cylinder, $[0,1] \times {\bf S}^1$, as its configuration space. Find its forward kinematics map.

The forward kinematics map is used for motion planning. Especially when the topology of the operation space is non-trivial, looking at the homology map of this map is a way to learn about the possible solutions.

Example. In the above example of a two-joint arm, the forward kinematics map is a map $$f:{\bf T}^2 \to A,$$ where $A$ is the annulus. Whatever the exact map is, its homology map $$f_1:H_1({\bf T}^2)={\bf R}\times{\bf R} \to H_1(A)={\bf R}$$ can be easily understood. It is the projection. Indeed, either of the generators of the $1$st homology group $H_1({\bf T}^2)={\bf R}^2$ is the cycle that represents a single turn of the joint. However, only the first one is mapped to the generator of $H_1(A)={\bf R}$. The image of the second generator doesn't go around the annulus and, therefore, its homology class collapses under $f$. This wouldn't be the case if $R_1 < R_2$, but in that case the homology of the operational space is trivial anyway.

$\square$

One can use this information to try to match the required operational space with the configuration possible space or vice versa.

One may ask whether a given robotic arm design is appropriate to spray paint on a topologically complex surface $S$:

Robotic arm with spray can.png

The maps to consider are of this form: $$f:{\bf S}^1 \times ... \times {\bf S}^1 \times {\bf S}^2 \to S.$$ The analysis of possible homology maps between the homology groups of these manifolds will help to rule out some designs. Since we want to be able to paint the whole surface, the question becomes, is this map onto?

Example. In the case of a two-joint arm, the map is $$f:{\bf T}^2\to S.$$ If, for example, $S={\bf T}^2$, then, of course, we can choose the identity map and this map is onto. What if our knowledge of the robot is imperfect? Then we need to deal with the perturbations of this map. Are all maps homotopic to it also surjective? The answer is Yes.

$\square$

Exercise. Prove that all maps homotopic to the identity map of the torus are surjective.

However, a more typical object to paint is homeomorphic to the sphere $S={\bf S}^2$. Then the answer is No since every map ${\bf T}^2 \to {\bf S}^2$ is homotopic to the constant map!

Example. This is the configuration space of a $3$d two-joint arm:

Torus conf space.png

It has the two rods (first red, second green) perpendicular to each other. Then the configuration space and the operational space are homeomorphic via the obvious forward kinematics map. Its homology map is the identity.

$\square$

For more precise tasks, such as drawing or cutting, one may need the end of the arm to follow a particular path in the operational space. An example is the task of drawing a specified curve on a surface. Then one needs to find the values of the configuration parameters that will make this happen. This is called the inverse kinematic problem.

Rotating rod 2 w pen.png

Specifically, given a continuous path $p:[0,1] \to A$, in the operational space, find a path $q:[0,1] \to C$, in the configuration space, such that $p=fq$, where $f$ is the forward kinematic map. If such a solution exists, we say that the problem is “well-posed”.

If, in addition, we assume that these paths are loops, the existence of a solution for this problem can studied via the maps of the fundamental group induced by $f$. Or, indirectly, one can study the loops via their $1$-homology classes.

Exercise. Consider the inverse kinematic problem for drawing a curve on the torus that may be (a) a meridian, (b) longitude, or (c) the diagonal. What if the robot has many joints but only one rotational joint?

Social choice: standstill in hostilities

Example (the game of chicken). Suppose we have a road and two cars approaching from the opposite directions. Both have a continuum of strategies: from keeping all the way to the left to keeping all the way to the right. The goal of either of the two drivers is to minimize the damage and each strategy will produce a different outcome relative to this goal. There are two Nash equilibria: both keep right or both keep left.

Red and green car Nash.png

One can see that the response maps are set-valued.

$\square$

We generalize the setting for a hostile game from two to multiple players.

Suppose we have $m>1$ players each with a space of choices: $$X_i,\ i=1,2,...,m.$$ The choice of $i$th player is determined by the choices of the rest of the players. The $i$th response map is a (possibly set-valued) map $$r_i:X_1\times ...\times [X_i] \times ... \times X_m \to X_i,$$ where the bracket indicates that the $i$th item is excluded. The combined response function of the game is a (possibly set-valued) map $$R: X_1\times ...\times X_m \to X_1\times ...\times X_m$$ given by $$R(x_1,...,x_m):=(r_1([x_1],x_2,...,x_m),...,r_m(x_1,...,x_{m-1},[x_m])).$$ A Nash equilibrium of the game is a fixed point of the combined response function $R$.

We already know that the Brouwer Fixed Point Theorem implies that, for $X$ an acyclic polyhedron, any pair of self-maps of $X$ allows a Nash equilibrium. For the case when the response isn't unique, we have to apply the Kakutani Fixed Point Theorem instead.

Theorem. Suppose the choice spaces $X_i,\ i=1,2...,m$, are acyclic polyhedra and the response maps have polyhedral graphs and non-empty convex values. Then the game has a Nash equilibrium.

Suppose now that each player tries to maximize some utility of his own: $$u_i:X_1\times ...\times X_m \to {\bf R},\ i=1,2,...m.$$ Then the response functions of this game are set-valued: $$r_i(y)=\arg\max_{x_i\in X_i}u_i(x_1,...,x_m).$$

Theorem. Suppose $X$ is an convex polyhedron and the utilities are convex. Then the game above allows a Nash equilibrium.

Exercise. Prove the theorem.

Exercise. Provide definitions for the utilities in the above example of the game of chicken and find its Nash equilibria. How does the game change as the road becomes wider? What if the road is a cylinder?

Exercise. Does haggling over a price have a Nash equilibrium?

The space of choices may be a simplicial complex with every simplex seen as the probability simplex. In that case, the choices are the mixed strategies.

Below we will be more specific about the origin of the utilities.

Recall the set-up of the social choice problem. Suppose there are $m$ agents, who are now the players, making their moves:

  • the space of choices: a polyhedron $X$;
  • the choice made by the $k$th player: a point $x_k\in X,\ k=1,2,...,m$;
  • the game outcome: the choice function $f:X^m\to X$.

For the game to be fair, we require, as before, the choice function satisfy the following three conditions:

  • continuity;
  • symmetry: $f(s(u))=f(u),\ \forall u\in X^m,\forall s\in \mathcal{S}_m;$
  • diagonality: $f(x,x,...,x)=x,\ \forall x \in X.$

Finally, the $i$th player tries to maximize his utility function $u_i=U_if$, where $U_i:X\to {\bf R}$, is some location-dependent function, such as the negative of the distance to $i$th perfect location.

Exercise. State and prove a theorem about existence of a Nash equilibrium for this setting.

We know that if the space of choices is path-connected and has torsion free homology, then, for the social choice problem to have a solution, the space of choices has to be acyclic. Our conclusion was, when the space of choices is acyclic, a compromise-producing rule is possible and now we also know that if the participants try to manipulate its outcome, they arrive to a standstill.