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$?

Some comments:

  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.

  • 1
    $\begingroup$ 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... $\endgroup$ Jul 12, 2013 at 15:18
  • $\begingroup$ 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. $\endgroup$ Jul 15, 2013 at 22:43
  • $\begingroup$ 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? $\endgroup$ Jul 15, 2013 at 22:54
  • $\begingroup$ Actually, the proof given in the (second) linked paper generalizes to analytic $A$. $\endgroup$ Jul 16, 2013 at 1:19
  • $\begingroup$ @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? $\endgroup$
    – SBF
    Jul 16, 2013 at 9:52

2 Answers 2


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 :-)

  • $\begingroup$ Do you mean that the existence of the exercise hints upon the existence of the counterexample, but you don't know the solution? :) $\endgroup$
    – SBF
    Jul 18, 2013 at 17:43
  • $\begingroup$ 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 :-) $\endgroup$ Jul 18, 2013 at 17:49
  • $\begingroup$ 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 $\endgroup$
    – SBF
    Jul 18, 2013 at 19:57
  • $\begingroup$ 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. $\endgroup$ Jul 18, 2013 at 20:44
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 22, 2013 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.

  • $\begingroup$ Dear George, thanks a lot for the answer - now I need to read it carefully. $\endgroup$
    – SBF
    Aug 28, 2013 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.