14
$\begingroup$

This question is related to another one that I asked two days ago.

Question. Does there exist a Borel subset $ M $ of $ \mathbb{R}^{2} $ with the following two properties?

  • The projection of $ M $ onto the first component is a non-Borel analytic subset of $ \mathbb{R} $.
  • Every vertical cross-section of $ M $ is finite, i.e., the set $ \{ y \in \mathbb{R} \mid (x,y) \in M \} $ is finite for every $ x \in \mathbb{R} $.

An affirmative answer to this question will provide a counterexample in the topic of measure theory, as explained in the linked post. It therefore holds some importance.

Thank you very much for your help!

$\endgroup$
  • 2
    $\begingroup$ I think the answer is no, and it could be proved with results from Borel equivalence relations. Consider $M$ as a standard Borel space, and the Borel equivalence relation $E$ on $M$ which is $(x,y) E (x', y')$ iff $x=x'$. Since every equivalence class of $E$ is finite, it has a transversal: a Borel set $A \subset M$ containing one element from each $E$-class. (See Proposition 1.4.4 in homepages.math.uic.edu/~kslutsky/papers/cber.pdf.) Then the projection $\pi : A \to \mathbb{R}$ is an injective Borel function, hence its image $\pi(A) = \pi(M)$ is Borel. $\endgroup$ – Nate Eldredge Nov 2 '16 at 6:45
  • 1
    $\begingroup$ But there should be a more elementary argument. $\endgroup$ – Nate Eldredge Nov 2 '16 at 6:46
  • 1
    $\begingroup$ @Nate: Thank you for your comments, Nate. Yes, a more elementary argument might do away with the requirement that $ M $ be a standard Borel space. Hopefully, a descriptive set theorist will be able to weigh in. $\endgroup$ – Transcendental Nov 2 '16 at 9:56
  • 1
    $\begingroup$ Oh, that part's not a requirement: since $M$ is a Borel subset of $\mathbb{R}^2$ it is already a standard Borel space. I just mean to think of it as a space in its own right, since we don't really want to work with an equivalence relation on all of $\mathbb{R}^2$. $\endgroup$ – Nate Eldredge Nov 2 '16 at 12:51
21
$\begingroup$

No, no such set exists. This is a special case of the Lusin–Novikov theorem; see e.g. Kechris, Classical Descriptive Set Theory, Theorem 18.10.

In general, let $X,Y$ be standard Borel spaces, and suppose $M \subset X \times Y$ is Borel. (Here we are taking $X=Y=\mathbb{R}$.) For $x \in X$, let $M_x = \{y : (x,y) \in M\}$ be the section of $M$ at $x$. The Lusin–Novikov theorem asserts that if all but at most countably many of the $M_x$ are at most countable (i.e. $|\{x : |M_x| > \aleph_0\}| \le \aleph_0$) , then $M$ has a Borel uniformization: there is a Borel set $M^* \subset M$ such that $M^*$ intersects every nonempty section $M_x$ in exactly one point. In particular, the projection map $\pi : X \times Y \to X$, which is Borel, is injective when restricted to $M^*$; so as a consequence (see Kechris Corollary 15.2) we have that $\pi(M^*) = \pi(M)$ is Borel in $X$.

Any set $M$ satisfying your second condition certainly satisfies the hypothesis of Lusin–Novikov (since $\{x : |M_x| > \aleph_0\} = \emptyset$), so its projection is Borel, and thus it does not satisfy your first condition.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Or you can even prove it bare-handedly by noticing there is a borel linear ordering of the space, define the uniformizing function by picking the least element under that $\endgroup$ – Jing Zhang Nov 2 '16 at 16:46
  • $\begingroup$ @JingZhang: So you're suggesting something like let $f(x) = \inf M_x$? I considered that but did not see how to show it's a Borel function. We have to use somewhere the fact that the sections are finite. For general $M$ this will not give a Borel function. $\endgroup$ – Nate Eldredge Nov 2 '16 at 16:53
  • 1
    $\begingroup$ @NateEldredge: Yeah the definition is $(x,y)\in f \Leftrightarrow (x,y)\in B \wedge \forall z<y (x,z)\not \in B$, which is just co-analytic. I believe Luzin-Novikov is needed to reduce $\forall z<y$ to a countable operation. (I thought of Feldman-Moore which states every countable Borel equivalence relation is the same as an orbit equivalence relation generated by some action of a countable group on the space, but I don't think this is any easier than LN). $\endgroup$ – Jing Zhang Nov 2 '16 at 18:04
6
$\begingroup$

The projection is always Borel provided the set is Borel and each cross-section is at most countable. This is an old theorem of Luzin and/or Novikov, valid for sets in any product of two polish spaces, and the countability can be weakened to sigma-compactness (Novikov and/or Kunugui).

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

There is a pure recursion theoretical proof of the result. The idea is as follows: By Spector-Gandy theorem, a lightface Borel set $(x,y)$ is an r.e set over $L_{\omega_1^{CK}}[x,y]$. If there are at most countably many $y$'s corresponded to the $x$ for every $x$, then it can be reduced to $L_{\omega_1^{CK}}[x]$. Then the projection to the first section becomes a $\Pi^1_1$ statement.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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