12
$\begingroup$

I am working on measurable sets and I have been coming across this, so called "fact" about unit circle. More precisely, some of proofs I am studying based on the following observation:

There is a Borel set in the unit square whose projection onto the first coordinate is not a Borel set in the interval $[0,1]$.

I can't give a proof or visual image of this set. I thought two- dimensional Cantor sets i.e., $\mathcal{C}\times \mathcal{C}$.

$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

The other answers are absolutely correct; let me add to them by giving an explicit example of such a set.

There is (think Godel numbering) a way to represent linear orderings with domain $\mathbb{N}$ by real numbers. Similarly, we can represent infinite sequences of natural numbers by real numbers. So we can define the following set:

$X$ is the set of pairs $(r, s)$ of real numbers such that $r$ codes a linear ordering and $s$ codes an infinite descending sequence through (the linear order coded by) $r$.

Let $Y$ be the projection of $X$ onto the first coordinate; then $Y$ is the set of reals which code non-well-orderings (or which fail to code linear orderings). This set, it turns out, is non-Borel! Meanwhile - as long as the coding scheme we used above is non-silly - $X$ is Borel.

Most of this is fairly straightforward; the hard part, of course, is proving that $Y$ is indeed not Borel. This is a bit technical, so I'm not going to get into it here; the citations in the other answers say more.

$\endgroup$
3
  • $\begingroup$ Cool.There's some hand waving at math.stackexchange.com/q/1857699 that I "know" is correct; if you felt like confirming that I'd appreciate it. $\endgroup$
    – David C. Ullrich
    Jul 14, 2016 at 13:50
  • $\begingroup$ Been thinking about this, I think it's starting to make sense. The set $X$ is defined by finitely man conditions, each of which involves finitely many quantifiers over $\Bbb N$. So $X$ is Borel, in fact it appears at some finite stage of the hierarchy. On the other hand the definition of $Y$ involves quantifying over all sequences. Not a proof that $Y$ is not Borel, but it makes it clear that $Y$ is not "obviously" Borel the way $X$ is. Heh. $\endgroup$
    – David C. Ullrich
    Jul 15, 2016 at 13:55
  • $\begingroup$ Regarding how one proves that $Y$ is not Borel, you could tell me something. A set of relations on $\Bbb N$ is the same as $S\in\mathcal P(K)$, where $K=\mathcal P(\Bbb N\times\Bbb N)$, the Cantor set. "All one has to do" is concoct a property $P$ such that (i) it's straightforward to show that every Borel set $S$ satisfes $P$ and (ii) $P(S)$ implies that $S\ne Y$. No hints regarding what such a $P$ might be please, but Q: Is there a $P$ such that once I figure out what $P$ is the rest should work? $\endgroup$
    – David C. Ullrich
    Jul 15, 2016 at 14:03
8
$\begingroup$

You are not alone in finding this tough, as Lebesgue himself believed (in 1905) he had proved that the projection of a Borel set in $\mathbb{R}^2$ onto one of the axes was a Borel set. His error was discovered by Souslin which lead (I believe) to the process of Souslin schemes/hierarchy that he developed to investigate this problem.

R. M. Dudley "Real Analysis and Probability"

In my oldish edition it is covered in chapter 13, although my edition is by Chapman and Hall, whereas the Amazon edition is published by Cambridge. I am not sure that he actually gives a proof of the existence of such a set, but it is a good place to start, and he gives lots of references at the end of each chapter.

There is also another (older) book by Rogers on "Analytic Sets", but I don't have a copy so I can't check it.

$\endgroup$
5
$\begingroup$

The projection of a Borel set in the square onto the $x$-axis is a so-called analytic set or Souslin set in the line. So you are asking for an analytic set in the interval that is not a Borel set. That is, an analytic set whose complement is not analytic. Any text on descriptive set theory should have such a construction. For example:

Donald L. Cohn, Measure Theory (Birkhäuser, 1980) Corollary 8.2.17, page 269

There is an analytic subset of $\mathcal N$ that is not a Borel set.

Here, $\mathcal N$ is homeomorphic to the irrationals in $(0,1)$, for example.

As a consequence, any uncountable complete metric space has such a set as well.

$\endgroup$
1
  • 3
    $\begingroup$ I don't quite follow. If this Borel set in $\mathbb{R}^2$ exists, then its projection is analytic, but not Borel. So if you construct such an analytic set on the line, how does this give you the counterexample in $\mathbb{R}^2$? $\endgroup$
    – user940
    Dec 12, 2013 at 21:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .