# Principle of measurable choice

Consider the following principle of measurable choice:

Let $$X,Y$$ be complete separable metric spaces and $$E$$ a closed $$\sigma$$-compact subset of $$X\times Y$$. Then $$\pi_1(E)$$ is a Borel set in $$X$$ and there exists a Borel function $$\varphi:\pi_1(E)\to Y$$ whose graph is contained in $$E$$. (Here $$\pi_1$$ denotes the projection of $$X\times Y$$ on $$X$$).

Proof.

Since $$E$$ is $$\sigma$$-compact we can write $$E=\cup_{i=1}^\infty C_i$$ with each $$C_i$$ compact in $$X\times Y$$. Then $$\pi_1(E)=\cup_{i=1}^\infty \pi_1(C_i)$$ with each $$\pi_1(C_i)$$ compact in $$X$$ since $$\pi_1$$ is continuous. Compact subsets of metric spaces are closed, hence Borel. Therefore $$\pi_1(E)$$ is a countable union of Borel sets in $$X$$, hence Borel.

Fix a countable dense subset $$\{y_n:n\in\mathbb{N}\}$$ in $$Y$$. Define $$\varphi_1:\pi_1(E)\to Y$$ by the rule $$\varphi_1(x)=y_{n_1(x)}$$, where $$n_1(x)$$ is the smallest $$n$$ such that $$E\cap \big[\{x\}\times \bar{B}_{1/2}(y_n)\big]\neq \emptyset \quad\quad\quad (1)$$

where $$\bar{B}_{1/2}(y_n):=\{y\in Y: d(y,y_n)\}\leq 1/2\}$$. This is well-defined, since $$x\in \pi_1(E)$$ implies $$(x,y)\in E$$ for some $$y\in Y$$, and by density there exists $$n$$ such that $$d(y_n,y)<1/2$$. Hence the set of $$n$$ satisfying $$(1)$$ is not empty.

Suppose inductively that $$\varphi_k:\pi_1(E)\to Y$$ has been defined for some $$k\geq 1$$. Define $$\varphi_{k+1}:\pi_1(E)\to Y$$ by the rule $$\varphi_{k+1}(x)=y_{n_{k+1}(x)}$$, where $$n_{k+1}(x)$$ is the smallest $$n$$ such that $$E\cap \big[\{x\}\times \bar{B}_{1/2^{k+1}}(y_n)\big]\neq \emptyset \quad \text{and} \quad d(y_n,\varphi_k(x))\leq 1/2^{k-1}\quad\quad\quad (2)$$

This is well-defined, since by definition of $$\varphi_k(x)$$ there exists $$y\in Y$$ such that $$(x,y)\in E\cap \big[\{x\}\times \bar{B}_{1/2^k}(\varphi_k(x))\big]$$, and by density there exists $$n$$ such that $$d(y_n,y)<1/2^{k+1}$$. Then $$(x,y)\in E\cap \big[\{x\}\times \bar{B}_{1/2^{k+1}}(y_n)\big]$$ and by the the triangle inequality $$d(y_n,\varphi_k(x))\leq d(y_n,y)+d(y,\varphi_k(x))\leq 1/2^{k+1}+1/2^k<1/2^{k-1}$$

so the set of $$n$$ satisfying $$(2)$$ is not empty.

Question.

At this point in the proof the author says that a simple induction argument shows that each $$\varphi_k$$ is Borel. This is where am having issues.

Since the range of each $$\varphi_k$$ is contained in $$\{y_n:n\in\mathbb{N}\}$$, it suffices to show that each preimage $$\varphi^{-1}_k(y_n)$$ is Borel in $$\pi_1(E)$$.

Any ideas on how to show it? Thanks for your help.

EDIT. I made some progress below. Any feedback is very appreciated!

Define the following correspondence :

$$\phi:X\to \mathcal P(Y), \quad \phi(x)=\big\{y\in Y: (x,y)\in E\big\}$$

Note that $$\phi(x)\neq\emptyset$$ if and only if $$x\in\pi_1(E)$$. Let $$B$$ a closed set in $$Y$$, and define $$E(B)$$ by

$$E (B):=\big\{x\in X : \phi(x)\cap B\neq \emptyset\big \}=\pi_1\big[(X\times B) \cap E \big]$$

I claim that $$E(B)$$ is Borel in $$\pi_1(E)$$. Indeed $$(X\times B) \cap E=\cup_{i=1}^\infty (X\times B) \cap C_i$$. For each $$i$$, $$(X\times B) \cap C_i$$ is a closed subset of the compact set $$C_i$$ in $$X\times Y$$, and is thus compact in $$X\times Y$$. It follows (as above) that $$\pi_1\big[(X\times B) \cap E \big]=\cup_{i=1}^\infty \pi_1 \big[(X\times B) \cap C_i\big]$$ is a countable union of compact sets in the metric space $$X$$, hence Borel in $$X$$. Clearly, $$\pi_1\big[(X\times B) \cap E \big]\subset \pi_1( E)$$, and so we conclude that $$E(B)$$ is Borel in $$\pi_1(E)$$.

Now let $$A_n=E(B_n)$$ with $$B_n=\bar{B}_{1/2}(y_n)$$ for each $$n$$. Since each $$B_n$$ is closed in $$Y$$, each $$A_n$$ is Borel in $$\pi_1(E)$$ by the previous claim. Moreover, we see that

$$\varphi_1^{-1}(y_n)=A_n\setminus \cup_{i=1}^{n-1}A_i \quad\quad\quad (3)$$

for each $$n$$, and so each preimage is Borel in $$\pi_1(E)$$. It follows that $$\varphi_1$$ is Borel measurable.

Now assume inductively that $$\varphi_k$$ is Borel measurable for some $$k\geq 1$$. Let $$A_n=E(B_n)$$ with $$B_n=\bar{B}_{1/2^{k+1}}(y_n)$$ for each $$n$$. As before each $$A_n$$ is Borel in $$\pi_1(E)$$. Let

$$C_n=A_n\cap \varphi_{k}^{-1}\big[\bar{B}_{1/2^{k-1}}(y_n)\big]$$ for each $$n$$. Since $$\bar{B}_{1/2^{k-1}}(y_n)$$ is closed in $$Y$$ and $$\varphi_k$$ is Borel measurable by assumption, we have that each $$C_n$$ is Borel in $$\pi_1(E)$$. Moreover we have

$$\varphi_{k+1}^{-1}(y_n)=C_n\setminus \cup_{i=1}^{n-1}C_i \quad\quad\quad (4)$$

for each $$n$$, and so each preimage is Borel in $$\pi_1(E)$$. It follows that $$\varphi_{k+1}$$ is Borel measurable.

By induction it follows that each $$\varphi_k$$ is Borel measurable. Note that in $$(3)$$ and $$(4)$$ I assumed each $$y_n$$ to be distinct. The case of a finite dense subset can be handled in the same way.

• May I know this is from which book? Aug 8, 2021 at 16:14
• @user284331 It is the first theorem from this AMS paper: jstor.org/stable/2039503 . Aug 8, 2021 at 16:19
• Can you show that $\varphi_1 (x)$ is Borel? Aug 8, 2021 at 16:52
• @pseudocydonia I made an attempt. Do you think its ok? Aug 9, 2021 at 16:35
• @user284331 I tried to answer in the EDIT section of my post. Do you think this is correct? Aug 9, 2021 at 19:23

For completeness I will finish the proof of the theorem. We have constructed a sequence of Borel functions $$\varphi_k:\pi_1(E)\to Y$$. The next step is to show that this sequence is uniformly Cauchy:

Let $$m>n$$. Then, by the triangle inequality,

$$d(\varphi_m(x),\varphi_n(x))\leq d(\varphi_m(x),\varphi_{m-1}(x))+\dots+d(\varphi_{n+1}(x),\varphi_n(x)) \leq \frac{1}{2^{m-2}}+\dots+\frac{1}{2^{n-1}}=\sum_{i=n}^{m-1}\frac{1}{2^{i-1}}$$

where the second inequality follows from the definition of $$\varphi_k$$ in $$(2)$$ above. Since $$\sum_{i=1}^{\infty}\frac{1}{2^{i-1}}<\infty$$, for any given $$\epsilon>0$$ there exists $$N$$ such that $$\sum_{i=N}^{\infty}\frac{1}{2^{i-1}}<\epsilon$$. Then $$m>n\geq N$$ implies $$d(\varphi_m(x),\varphi_n(x))<\epsilon$$. It follows that $$(\varphi_k)$$ is uniformly Cauchy.

From $$(\varphi_k)$$ uniformly Cauchy and the fact that $$Y$$ is a complete metric space, it follows that $$(\varphi_k)$$ is uniformly convergent to some function $$\varphi:\pi_1(E)\to Y$$. We now use the fact that the pointwise limit of a sequence of measurable functions taking values in a metric space (with its Borel $$\sigma$$-algebra) is again measurable (see here). Therefore $$\varphi$$ is Borel measurable.

It remains to show that the graph of $$\varphi$$ is contained in $$E$$. Consider the distance function on $$X\times Y$$ defined by $$z\mapsto d[E,z]=\inf\{d(w,z) : w\in E\}$$. This function is continuous. Since

$$(x,\varphi_k(x))\to (x,\varphi(x)) \quad \text{as} \quad k\to \infty$$

we obtain $$d[E,(x,\varphi_k(x))]\to d[E,(x,\varphi(x))] \quad \text{as} \quad k\to \infty$$ for all $$x\in \pi_1(E)$$. Moreover, the definition of $$\varphi_k$$ in $$(1),(2)$$ above implies that $$d[E,(x,\varphi_k(x))]\leq\frac{1}{2^k}\to 0$$ as $$k\to\infty$$, and so we conclude that $$d[E,(x,\varphi(x))]=0$$ for all $$x\in \pi_1(E)$$. As $$E$$ is closed, this implies that $$(x,\varphi(x))\in E$$ for all $$x\in \pi_1(E)$$, as desired.

Remark: Only the completeness and separability of $$Y$$ was needed.