Selection problem: how to solve?

Question

Here is what we have done. We started from having a system subject to $\dot x(t)=f(x(t),u(t))$ (dropping explicit dependence of $f$ from $t$ for simplicity), with $u(t)\in\mathcal{U}$ for all $t$, and our problem was to minimize the time taken to go from $x(0)=x^0$ to $x(T_f)=x^f$, $T_f$ being the final time at which $x^f$ is reached. We moved to a differential inclusion $\dot x(t)\in F(x(t))=\{f(x(t),u):u\in\mathcal{U}\}$. We proved that, assuming $F(x)$ is compact and convex for all $x$ and that $F$ is upper semicontinuous as specified here, there exists a solution to the minimal-time problem for the inclusion. Then we said: we are not done yet. We still need to find the optimal control $u_\ast$ such that the solution we have found, $x_\ast$, for the minimal-time problem for the inclusion satisfies $x_\ast'(t)=f(x_\ast(t),u_\ast(t))$, and we want to know if we can find a measurable such $u_\ast$. And the professor then said:

Allora, a meno che non ci sia, da parte vostra, una forte domanda, io salterei questa parte, perché è un po' tecnica.

I.e.:

So, unless there is, on your part, a strong question, I would skip this part, since it is a bit technical.

Update

Going on, he mentions the Kuratowski and Ryll-Nardzewski theorem, which goes as follows. First of all, a definition.

Definition

Let $X$ be topological and $\psi:\Omega\to X$ be a function, where $(\Omega,B)$ is a measurable space. We call $\psi$ $B$-weakly measurable if for all $U\subseteq X$ open we have $\{\omega:\psi(\omega)\cap U\neq\varnothing\}\in B$.

The theorem then states that:

Theorem (Kuratowski Ryll-Nardzewski)

If $X$ is Polish (i.e. separable and completely metrizable), $\tilde B$ is the Borel $\sigma$-algebra of $X$, and $\psi:\Omega\to\tilde B$ is a set function taking nonempty closed values which is $B$-weakly measurable (see definition above), then there exists a measurable $f:(\Omega,B)\to(X,\tilde B)$ such that $f(\omega)\in\psi(\omega)$ for all $\omega\in\Omega$.

In the above, we assumed $F$ was compact-valued, so it has closed values. We need non-emptiness, but if there were $x$'s with $F(x)=\varnothing$, for some $x$ there would be no admissible controls, which is not a good idea. Hence we may assume nonemptiness for the images of $F$. The images of $F$ are subsets of metric spaces. So the $X$ we have is metrizable. Since we need the $\mathbb{R}^n$ case, we assume separability and completeness, as $\mathbb{R}^n$ satisfies these requirements. The domain of $F$ is an interval. The $B$ is the Borel $\sigma$-algebra of the interval. I guess the USC condition guarantees the weak measurability condition. Hence, we apply the theorem, and we are done.

But how is that theorem proved? Or how do we prove the special case I need for the problem at hand?

Answer 1

Finding the proof of a named theorem is far easier :). Here is one. I'll copy it here and expand on it, and there is a bit I fear I can't understand yet. Note that I will denote $F^{-1}(A)=\{x:F(x)\cap A\neq\varnothing\}$ in what follows, hence weak measurability is the condition that $F^{-1}(V)$ is measurable for each open set $V$, which is formally identical to measurability of maps.

Proof:

For any weakly measurable $G$ and any open cover $\mathcal{U}=(U_n)_{n\in\mathbb{N}}$ of $Y$ we define $G_{\mathcal{U}}:X\to2^Y$ another closed-valued weakly measurable map by:

$$G_{\mathcal{U}}(x)=\overline{G(x)\cap U_n} \qquad \text{where: }x\in G^{-1}(U_n)\smallsetminus\bigcup_{\nu=1}^{n-1}G^{-1}(U_\nu).$$

Let us immediately check that this map is well-defined. Then the reference lists three properties, including measurability.

1. For all $x\in X$, there exists $n:x\in G^{-1}(U_n)$. Indeed, there is a $y\in G(x)$, and the $U_n$'s cover $Y$, so $y$ belongs to at least one $U_n$, hence $x\in G^{-1}(U_n)$;
2. There is at least one $n$ such that $x\in G^{-1}(U_n)\smallsetminus\bigcup_{\nu=1}^{-1}G^{-1}(U_\nu)$; that is the case since, for all $x$, there exists $\overline n(x)=\min\{n\in\mathbb{N}:x\in G^{-1}(U_n)\}$ such that $x\in G^{-1}(U_{\overline n(x)})$ and is in none of the $G^{-1}(U_\nu)$ with $\nu\leq\overline n(x)$;
3. The $n$ in 2. is unique; indeed, if $n\neq m$, $G^{-1}(U_n)\smallsetminus\bigcup_{\nu=1}^{n-1}$ is disjoint from $G^{-1}(U_m)\smallsetminus\bigcup_{\nu=1}^{m-1}G^{-1}(U_m)$, since, assuming $n<m$, the former is included in $G^{-1}(U_n)$ which is included in the union removed from the latter.

Hence, $G_{\mathcal{U}}$ is well-defined, since, using the notation in 2., we can term it alternately as:

$$G_{\mathcal{U}}(x)=\overline{G(x)\cap U_{\overline n(x)}}.$$

Then $G_{\mathcal{U}}$ has the following properties:

$$\sup_{x\in X}\operatorname{diam}G_{\mathcal{U}}(x)\leq\sup_{n\in\mathbb{N}}\operatorname{diam}(U_n). \qquad\qquad (i)$$

For all $x\in X$, $G(x)$ is included in $U_{\overline n(x)}$, hence:

$$\operatorname{diam}G(x)\leq\operatorname{diam}(U_{\overline n(x)})\leq\sup_n\operatorname{diam}(U_n),$$

and (i) follows.

$$\forall x\in X,\,G_{\mathcal{U}}(x)\subseteq G(x). \qquad\qquad (ii)$$

$G_{\mathcal{U}}(x)\subseteq\overline{G(x)\cap U_{\overline n(x)}}$. Let $y\in G_{\mathcal{U}}(x)$. Then we have $y_n\to y$ with $\{y_n\}\subseteq G(x)\cap U_{\overline n(x)}\subseteq G(x)$, but $G(x)$ is closed, hence $y\in G(x)$, proving (ii).

$$\forall\text{ open }V\subseteq Y,\,G^{-1}_{\mathcal{U}}(V)=\bigcup_{n\in\mathbb{N}}\left[G^{-1}(V\cap U_n)\smallsetminus\bigcup_{\nu=1}^{n-1}G^{-1}(U_\nu)\right]\text{, which is measurable.} \qquad\qquad (iii)$$

$\supseteq$ Let $y$ be in the right-hand side. Hence, $y\in G^{-1}(V\cap U_{\overline n})\smallsetminus\bigcup_1^{\overline n-1}G^{-1}(U_\nu)$ for some $n$. This set is included in the set appearing in the definition of $G_{\mathcal{U}}$, hence $G_{\mathcal{U}}(x)=\overline{G(x)\cap U_{\overline n}}$, aka $\overline n=\overline n(x)$ with $\overline n(x)$ as in 2. above. In particular, $G_{\mathcal{U}}(x)$ intersects $U_{\overline n}$. Now we need to show it actually intersects $V$. We know $G(x)$ intersects $V$. Actually, we know $G(x)\cap V\cap U_{\overline n}\neq\varnothing$, so in particular $G_{\mathcal{U}}(x)\cap V=\overline{G(x)\cap U_{\overline n}}\cap V\neq\varnothing$, proving $\supseteq$.

$\subseteq$ If $x\in G_{\mathcal{U}}^{-1}(V)$, then $G_{\mathcal{U}}(x)=\overline{G(x)\cap U_{\overline n(x)}}$ intersects $V$. Take $y$ in that intersection. $y$ is the limit point of a sequence $\{y_m\}\subseteq G(x)\cap U_{\overline n(x)}$. But then $y_m$ eventually lies in $V$, hence $V$ intersects $G(x)\cap U_{\overline n(x)}$, hence $x\in G^{-1}(V\cap U_{\overline n(x)})$. The above assumed $y$ was not an isolated point, but if it is, then it is in $G(x)\cap U_{\overline n(x)}$ and there is no need to call upon a sequence $y_m$. By definition of $\overline n(x)$, $x\in X\smallsetminus\bigcup_1^{\overline n(x)-1}G^{-1}(U_\nu)$, hence $x$ is in the RHS of (iii), proving $\subseteq$ and (iii).

So open sets have measurable preimages, since the preimages are countable uninos of measurable sets because $V\cap U_n$ and $U_\nu$ are open, hence by weak measurability their $G^{-1}$'s are measurable. What becomes of $G_{\mathcal{U}}^{-1}(A)$ for $A$ measurable? If $G_{\mathcal{U}}$ were a function, we know there are properties of preimage that make it enough to have preimages of generators of a $\sigma$-algebra measurable to have the map measurable. If the same properties hold for set functions like $G_{\mathcal{U}}$, then it is weakly measurable, since the preimages of open sets are measurable by the above and the open sets generate the Borel $\sigma$-algebra which is the one we are considering for measurability. So we need to prove that:

\begin{gather*} G^{-1}\left(\bigcup_{i=1}^\infty A_i\right)=\bigcup_{i=1}^infty G^{-1}(A_i), \\ G^{-1}\left(\bigcap_{i=1}^\infty A_i\right)=\bigcap_{i=1}^\infty G^{-1}(A_i), \\ G^{-1}(Y\smallsetminus A)=X\smallsetminus G^{-1}(A), \end{gather*}

where $G$ is now any set function, perhaps closed-valued, and $G_{\mathcal{U}}$ from above will be weakly measurable.

1. If $G(x)$ intersects a union, then it intersects at least one of the $A_i$, hence $x\in G^{-1}(A_i)$, hence $x\in\bigcup G^{-1}(A_i)$; if $x$ is in that union, then it is in one of the $A_i$, meaning $G(x)$ intersects $A_i$, hence it intersects the union;
2. If $G(x)$ intersects an intersection, it must intersect all the $A_i$, hence $x\in\bigcap G^{-1}(A_i)$; I leave the vice versa to the reader, who should simply imitate the vice versa of 1.;
3. If $G(x)$ intersects a complement… hm, I'm afraid this doesn't hold, because $G(x)$ may intersect both $A$ and its complement; all I need, though, is that $G^{-1}(Y\smallsetminus A)$ be measurable; $X\smallsetminus G^{-1}(A)\subseteq G^{-1}(Y\smallsetminus A)$, so if I prove $G^{-1}(A^C)\smallsetminus(G^{-1}(A))^C$ ($^C$ for complementation in their supersets), then I am done; but how do I prove this? The problem is $\{x:G(x)\cap A\neq\varnothing,G(x)\cap A^C\neq\varnothing\}$; is it measurable? I seem to be unable to prove it.

Now, for every $n\in\mathbb{N}$, we choose a countable open cover $\mathcal{U}_n$ of $Y$ with $\operatorname{diam}(U)\leq\frac1n$ for all $U\in\mathcal{U}_n$,

this is possible since $Y$ is separable, so every open cover admits a countable subcover (cfr here), hence there are countably many balls of radius $\frac1n$ that cover $Y$, for any $n$,

and define:

$$F_1:=F_{\mathcal{U}_1},\quad F_{n+1}:=(F_n)_{\mathcal{U}_{n+1}}.$$

By definition, $F_i(x)$ is closed for all $i$ and $x$. By the above, the $F_i$ are weakly measurable. By definition again, $F_{n+1}(x)=\overline{F_n(x)\cap U_{n,m}}\subseteq\overline{F_n(x)}=F_n(x)$ for all $x$, where $m$ is what I called $\overline n(x)$ in 2., but I called it $m$ to avoid the confusion with $n$, and $U_{n,m}$ is the $m$th element of $\mathcal{U}_n$. Hence, $F_n(x)$ is a decreasing sequence of closed sets for all $x$. Also, by (i), $\operatorname{diam}F_n(x)\leq\frac1n$, meaning those diameters tend to zero for fixed $x$ and $n\to\infty$.

Since $Y$ is complete and, for each $x\in X$, $(F_n(x))_{n\in\mathbb{N}}$ is a decreasing sequence of closed sets whose diameter tends to zero, we know that $\bigcap_{n\in\mathbb{N}}F_n(x)$ is a singleton.

That intersection, being contained in each $F_n(x)$, must have diameter zero, and hence be either a singleton or empty. For all $n$, $F_n(x)$ is nonempty, so we have $y_n\in F_n(x)$. Naturally, since the sequence $F_n(x)$ decreases, if $n\leq m$, $y_n,y_m\in F_n(x)$. Hence:

$$d(y_n,y_m)\leq\operatorname{diam}(U_{\min\{n,m\}})\leq\frac{1}{\min\{n,m\}}\xrightarrow{n,m\to\infty}0.$$

Hence, $y_n$ is Cauchy in $Y$, which is complete, so $y_n\to y$ for some $y\in Y$. Now $y$ is the limit of a sequence which is eventually in each $F_n(x)$, and each $F_n(x)$ is closed, hence $y$ must belong to each $F_n(x)$, proving the intersection of the $F_n(x)$ is a singleton.

The map $f:X\to Y$ defined by:

$$f(x)\in\bigcap_{n\in\mathbb{N}}F_n(x)$$

is obviously a selection for $F$.

Indeed, that big intersection is contained, e.g., in $F_1(x)$, which is contained in $F(x)$ (yeah, in $\overline{F(x)\cap U_{1,n}}$ for some $n$, which is contained etc as I did above in a similar situation).

To conclude, we must prove $f$ is measurable w.r.t. the $\sigma$-algebra $\mathfrak{A}$ on $X$ and the Borel $\sigma$-algebra on $Y$ $\mathcal{B}(Y)($.

To prove that $f$ is $\mathfrak{A}$-$\mathcal{B}(Y)$-measurable, let an open $V\subseteq Y$ be given. We set $V_n:=\{y\in Y:d(y,V^C)>\frac1n\}$. Then $V_n$ is open,

indeed, $V_n^C=\{y:d(y,V^C)\leq\frac1n$, suppose $y_m\to y$ and $\{y_m\}\subseteq V_n^C$, then $d(y,V^C)=\lim_{m\to\infty}d(y_m,V^c)\leq\frac1n$, so $V_n^C$ is closed, so $V_n$ is open,

and we will show:

$$f^{-1}(V)=\bigcup_{n\in\mathbb{N}}F_n^{-1}(V_n),$$

hence $f^{-1}(V)\in\mathfrak{A}$.

$f$ is now a map, so we know that if the preimages of open sets are measurable, as we now are setting out to prove, then the preimages of all Borel sets are measurable, hence $f$ is measurable as desired.

"$\subset$" Let $x\in F^{-1}(V)$ be arbitrary. Then there exists an $n\in\mathbb{N}$ with $d(f(x),V^C)>\frac1n$,

that is what I cannot seem to manage proving: why should it be? I mean, suppose it weren't true. Then $d(f(x),V^C)=0$, and since $V^C$ is closed $f(x)\in V^C$. Then what? Well, $F(x)$ intersects $V$, but nothing seems to imply any of the $F_n(x)$ do…

i.e. $f(x)\in V_n$. Since $f(x)\in F_n(x)$, we deduce $F_n(x)\cap V_n\neq\varnothing$, i.e. $x\in F_n^{-1}(V_n)$. Thus we have $\subset$.

"$\supset$" For $x\in F_n^{-1}(V_n)$ we have $F_n(x)\cap V_n\neq\varnothing$. Since $\operatorname{diam}(F_n(x))\leq\frac1n$, the definition of $V_n$ implies $F_n(x)\cap V^C=\varnothing$,

if there were $y\in F_n(x)\cap V^C$, $d(y,f(x))\leq\frac1n$ because $y\in F_n(x)$ which has diameter less than $\frac1n$, yet $d(y,f(x))>\frac1n$ by definition of $V_n$, contradiction,

hence $f(x)\in F_n(x)\subset V$, which proves $\bigcup_{n\in\mathbb{N}}F_n(x)\subset f^{-1}(V)$.

"which proves" that $x\in f^{-1}(V)$, but $x$ was arbitrary in $F_n^{-1}(V_n)$, hence $\bigcup F_n^{-1}(V_n)\subseteq f^{-1}(V)$.

So modulo getting the missing bits proved, we have the theorem proved.

Now we only need to prove USC implies weakly measurable. I will try after dinner, or leave a comment saying I was unable to conclude.

Update

1. The complement thing is useless, since weak measurability only concerns preimages of open sets, which we dealt with already;
2. Just as I feared, I got stuck on proving u.s.c. implies w.m.; could anyone help me?

Update 2

I just realised the problematic passage is problematic only due to a typo. Specifically, the passage reads:

"$\subset$" Let $x\in F^{-1}(V)$ be arbitrary. Then there exists an $n\in\mathbb{N}$ with $d(f(x),V^C)>\frac1n$,

and that $F$ should be lowercase. $x\in f^{-1}(V)$ means $f(x)\in V$, but $V$ is open, hence $f(x)\in V$ implies $d(f(x),V^C)>0$, since $V^C$ is closed and $d(f(x),V^c)=0$ would imply $f(x)\in V^C$ which is not the case, and so there must be an $n$ as said above. Thus, the proof no longer has any trouble.

It remains to prove that a USC map is weakly measurable. Hopefully I'll get an answer to that question.