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.
 A: 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.
