# Constructing a subset not in $\mathcal{B}(\mathbb{R})$ explicitly

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.

-
It's consistent with ZF (without choice) that every set of reals is Borel, so I'm not sure what Williams can mean here. –  Chris Eagle Apr 26 '12 at 15:35
@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. –  Sasha Apr 26 '12 at 15:41
A classic is Lusin's set of continued fractions which is analytic but not Borel. This might fit the bill in view of Chris's comment. –  t.b. Apr 26 '12 at 15:43
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. –  GEdgar Apr 26 '12 at 15:56

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<i_1 < i_2 < \cdots, \forall_{k \geqslant 1} a_{i_k} | a_{i_{k+1}} \}$$ The set is Lebesgue measurable (the measure zero, right?), but not Borel measurable.

-
@AndresCaicedo I would appreciate your comment on this answer of mine, as it draws, in part, from your post on MO. Thanks. –  Sasha May 3 '12 at 20:54
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. –  Asaf Karagila May 3 '12 at 21:10
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... :-) –  Asaf Karagila May 3 '12 at 21:22
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) –  Asaf Karagila May 3 '12 at 21:57
@AndresCaicedo: Fremlin in volume 5II of his measure theory 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. –  t.b. May 4 '12 at 19:09