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.

Solution 1:

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.