MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 :-)

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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