22
$\begingroup$

While reading David Williams's "Probability with Martingales", the following statement caught my fancy:

Every subset of $\mathbb{R}$ which we meet in everyday use is an element of Borel $\sigma$-algebra $\mathcal{B}$; and indeed it is difficult (but possible!) to find a subset of $\mathbb{R}$ constructed explicitly (without the Axiom of Choice) which is not in $\mathcal{B}$.

I am curious to see an example of such a subset.

  • 4
    It's [consistent with ZF](http://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice) (without choice) that every set of reals is Borel, so I'm not sure what Williams can mean here.2012-04-26
  • 0
    @ChrisEagle Thanks for the link. I wanted to add, that I the quoted text can be found in section 1.2 of the said book.2012-04-26
  • 5
    A classic is [Lusin's set of continued fractions](http://planetmath.org/encyclopedia/ALebesgueMeasurableButNonBorelSet.html) which is analytic but not Borel. This might fit the bill in view of Chris's comment.2012-04-26
  • 5
    We can construct explicitly a set that is analytic but not co-analytic. That can be done without AC. Then (with AC) we prove that such a set is not Borel.2012-04-26

1 Answers 1

13

I would like to write up an answer to my question, although I am bringing no input of my own, but compiling from various links provided in comments.

  1. There is a model of ZF in which the set of all real numbers is a union of countably many countable sets. This is theorem 10.6 on page 142 from the book of Tomas J. Jech, "Axiom of Choice".
    This implies that "all sets of reals are Borel" within this model. [Added However, in such a model, it is impossible to define countably additive Lebesgue measure. Thanks to @AsafKaragila for pointing this out.]

  2. Without the use of AC, one can construct a complete analytic set (i.e. a subset of $\mathbb{R}$ that is a continuous image of the space of irrational numbers, $\mathbb{R}\backslash \mathbb{Q}$). One can not prove that this set is non-Borel (here the model of ZF is different from that in item 1), without invoking the axiom of choice.

  3. An example of such an analytic set is due to Lusin, and described in a PlanetMath article by George Lowther, who also contibutes to this site. The set $S$ is defined as a set of continued fractions: $$ S = \{x \in \mathbb{R} : x = [a_0, a_1, a_2, \ldots ], \exists 0

  • 0
    @AndresCaicedo I would appreciate your comment on this answer of mine, as it draws, in part, from your post on MO. Thanks.2012-05-03
  • 0
    @GeorgeLowther Could you please look over this post, making sure that I am understanding your PlanetMath article on Lusin's example of Lebesgue measurable, but not Borel measurable set. Thank you.2012-05-03
  • 1
    Sasha, indeed it is possible to have that the real numbers are a countable union of countable sets, and in such model indeed every set is Borel, in fact the Borel rank is finite. In such model, however, one cannot fully develop the notion of a countably additive Lebesgue measure.2012-05-03
  • 0
    @AsafKaragila Thank you. This helps with understanding. I have expanded the answer to add your observation. By the way, if you happen to know, how would I make my answer a community wiki? Should I do this at all?2012-05-03
  • 1
    If you wish to make the answer CW simply click the checkbox when editing it (should be between the edit box and the preview). Whether or not you should, I don't know. It is up to you... :-)2012-05-03
  • 0
    I do not understand your comment in item 2. There are no models here, you have an explicit construction of a complete analytic set. Do you simply mean that item 2 holds in general, regardless of whether you assume the pathological situation of item 1, or otherwise?2012-05-03
  • 0
    A slightly more subtle thing is that one *can* develop a version of Lebesgue measure, even in the pathological situation described in item 1. The catch is that, rather than arguing about the sets themselves, we argue about their "codes". (There is a natural way to assign codes to Borel sets, that describe how they are constructed from basic open sets.) I am not claiming it is sensible to develop Lebesgue theory this way, of course. I haven't really seen this written in detail anywhere.2012-05-03
  • 0
    @AndresCaicedo Yes, I meant that in item 2 we no longer work with the model of ZF that was described in item 1. Thanks for your comments.2012-05-03
  • 0
    @Andres: Have you looked in Fremlin's book? He has quite a chapter about measure without choice and quite a lot on Borel code-based measures.2012-05-03
  • 0
    @AsafKaragila It may be there, you are right. I'll have to check.2012-05-03
  • 0
    @AsafKaragila The page on PlanetMath uses $a_i = \prod_{k=1}^i d_k$, this way $a_i$ divides $a_j$ for $j>i>0$.2012-05-03
  • 1
    Actually we are both wrong. The set is made of the fractions $[d_0;d_1,\ldots]$ such that there is an infinite subsequence $i_k$ for which $d_{i_k}$ is a divisor of $d_{i_{k+1}}$ for all $i$. This is a notably different condition than both our statements. (I removed my previous comment)2012-05-03
  • 0
    @AsafKaragila Yes, you are correct, of course. Thanks! The set I was talking about is a lot thinner, since it is $a_i | a_j$ for any $j>i>0$.2012-05-03
  • 2
    @AndresCaicedo: Fremlin in volume 5II of his [measure theory](http://www.essex.ac.uk/maths/people/fremlin/mt.htm) has chapter 56 devoted to measure theory without or with little choice and enters quite a bit of detail for Borel-codable sets; that chapter also has a section on what happens under determinacy, so this might be worth a look given your interests. There are ample references there, too.2012-05-04