# Borel kernel over an analytic set implies existence of a Borel map

Let $X$ and $Y$ be standard Borel spaces, and let $A\subseteq X\times Y$ be an analytic set with a full projection on $X$: that is $\pi_X(A) = X$. Suppose that there exists a Borel-measurable kernel $\mu:X\to\mathcal P(Y)$ such that $\mu(x,A_x) = 1$ for all $x\in X$ where $$A_x = \{y\in Y:(x,y)\in A\}$$ is an $x$-section of $A$. Does it follow that there exist a Borel map $f:X\to Y$ such that whose graph is a subset of $A$, i.e. $\mathrm{Gr}[f]\subseteq A$?

1. There always exists a universally measurable $g:X\to Y$ whose graph is a subset of $A$.

2. Clearly, the converse fact always hold true. Given the existence of such $f$ one can come up with a Borel kernel $\mu(C|x) = \delta_{f(x)}(C)$.

3. In case $A$ is Borel, the existence of Borel $f$ follows from the existence of Borel $\mu$ as proven e.g. in Controlled Markov processes or can be also found here.

-
Perhaps a method would be to prove some sort of compactness for the convex set of all such Borel kernels, then use Krein-Milman or so to get an extreme one, which should have the form $x \mapsto \delta_{f(x)}$. Just a guess... – Gerald Edgar Jul 12 '13 at 15:18
You can reduce to the case where $X=Y=[0,1]$ with the usual Borel sigma-algebra, and where $A_x$ has full Lebesgue measure in $[0,1]$ for each $x$. I feel that the result should still be false though. – George Lowther Jul 15 '13 at 22:43
Does there exist a function $g\colon[0,1]\to[0,1]$ whose graph has analytic complement, and intersects the graph of every Borel $f\colon[0,1]\to[0,1]$? If so, then letting $A$ be the complement of the graph of $g$ would give you a counterexample? – George Lowther Jul 15 '13 at 22:54
Actually, the proof given in the (second) linked paper generalizes to analytic $A$. – George Lowther Jul 16 '13 at 1:19
@GeorgeLowther: thanks for the comments. As far as I got from the proof there, if one shows that Lemma 1 holds for analytical $S$ (= there exists a Borel $\tilde S\subset S$ with $\mu_x$-positive closed $x$-sections), then the existence of a Borel graph contained in $S$ is immediate. If that is what you meant, could you suggest how to show existence of $\tilde S$ for analytical $S$? I also don't quite understand, why do they apply Lemma 1 to the completion of $Y$, and why do such $F_k$ exist - we can assume that when $Y$ is completed, it is totally bounded? – Ilya Jul 16 '13 at 9:52

The answer is no since, according to excercise 36.25 in A. Kechris: Classical Descriptive Set Theory, there should be an analytic set $A\subseteq \omega^\omega\times\omega^\omega$ whose vertical sections exclude at most a single point (i.e. $|\omega^\omega\setminus A_x|\leq 1$ for each $x$) which nevertheless does not admit a Borel uniformization. Right now, however, I don't see how to find the set :-)

-
Do you mean that the existence of the exercise hints upon the existence of the counterexample, but you don't know the solution? :) – Ilya Jul 18 '13 at 17:43
Yes :-), Well I assume that, as an excercise, it has a solution. And the solution is a counterexample. I would have left it as a comment, but I can't leave comments due to my low reputation :-) – jonathanverner Jul 18 '13 at 17:49
This still works as an answer, so +1, though let us wait a bit - maybe someone provides a concrete example. I'll try to figure it out by myself, but my descriptive set theory is very basic – Ilya Jul 18 '13 at 19:57
Maybe one can solve the exercise by diagonalization: There are $\mathfrak{c}$ points in $\omega^\omega$ and exactly as many Borel functions. So choose a bijection $x\mapsto f_x$ between Baire space and the Borel functions and let $A=\omega^\omega\times\omega^\omega\backslash\{(x,f_x(x)):x\in\omega^\omega\}$. I don't know how one can ensure $A$ is analytic though. – Michael Greinecker Jul 18 '13 at 20:44
I find this very surprising (mainly because I thought I had proven the opposite while thinking about this question). I'm going to have to have a look at Kechris's book in more detail. – George Lowther Aug 22 '13 at 11:28

The following is a construction of an analytic set $A\subseteq\omega^\omega\times\omega^\omega$ whose vertical sections exclude at most a single point, and which does not admit a Borel uniformization. This is as stated in jonathanverner's answer, although that did not include a construction - only mentioning exercise 36.25 in Kechris: Classical Descriptive Set Theory. The construction below is after viewing the hint in Kechris's book. I'll use the notation $\mathcal{N}$ for Baire space $\omega^\omega$.

Construction. Let $S$ be a universal subset of $\mathcal{N}\times\mathcal{N}^3$ (i.e., $S$ is closed and every closed subset of $\mathcal{N}^3$ is a vertical section $S_x$ of $S$ for some $x\in\mathcal{N}$). Then, let $A\subseteq\mathcal{N}^2$ consist of the points $(x,y)$ such that whenever, for any such $x$, there is a unique $(u,v)\in\mathcal{N}^2$ with $(x,x,u,v)\in S$ we have $y\not=u$. The set $A$ satisfies the required properties.

It is clear the sections $A_x$ exclude at most a single point. More precisely, it excludes the point $y$ if and only if there is a unique $(u,v)\in\mathcal{N}^2$ with $(x,x,u,v)\in S$ and $y=u$.

$A$ does not have a Borel section: Suppose that $\Gamma\subseteq\mathcal{N}^2$ is Borel. I'll now use the fact that every Borel subset of a Polish space is a continuous bijective image of a closed subset of $\mathcal{N}$ (Kechris, Theorem 13.7). By taking the graph of such a continuous bijection, there exists a closed set $C\subseteq\mathcal{N}^2\times\mathcal{N}$ whose projection onto $\mathcal{N}^2$ is one-to-one and has image $\Gamma$. Write $C=S_x$ for some $x\in\mathcal{N}$. Then, $(x,y)\in\Gamma$ if and only if $(x,x,y,v)\in S$ for some $v$, which is then unique. If $\Gamma_x$ consists of the single point $y$ then $(y,v)$ is unique such that $(x,x,y,v)\in S$ and, by construction, $(x,y)\not\in A$. So, $\Gamma$ is not a section of $A$.

$A$ is analytic: The set $T=\lbrace(x,y,z)\colon(x,x,y,z)\in S\rbrace$ is a closed subset of $\mathcal{N}^3$ and $(x,y)\in A$ iff whenever there is unique $(u,v)\in\mathcal{N}^2$ with $(x,u,v)\in T$ we have $y\not=u$. We can write $A=B\cup(\mathcal{N}^2\setminus C)$ where \begin{align} &B = \left\lbrace(x,y)\in\mathcal{N}^2\colon(x,y^\prime,z)\in T, {\rm some\ }y^\prime\not=y\right\rbrace\\ &C=\left\lbrace(x,y)\in\mathcal{N}^2\colon\exists ! z\in\mathcal{N}{\rm\ with\ }(x,y,z)\in T\right\rbrace. \end{align} As $B$ is the projection onto $\mathcal{N}^2$ of the (Borel) set of $(x,y,y^\prime,z)\in\mathcal{N}^2\times\mathcal{N}^2$ with $(x,y^\prime,z)\in T$ and $y\not=y^\prime$, it is analytic. Finally, $\mathcal{N}^2\setminus C$ is analytic by the following (surprising) result from Kechris (originally by Lusin).

Theorem (Kechris, Thm 18.11). Let $X,Y$ be standard Borel spaces and $B\subseteq X\times Y$ be Borel. Then, $$\left\lbrace x\in X\colon\exists ! y\in Y{\rm\ s.t.\ }(x,y)\in B\right\rbrace$$ is coanalytic.

-
Dear George, thanks a lot for the answer - now I need to read it carefully. – Ilya Aug 28 '13 at 9:15
Thanks for providing the details! – jonathanverner Sep 4 '13 at 9:20