23
$\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.

  • 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

15

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 The set is Lebesgue measurable (the measure zero, right?), but not Borel measurable.

  • 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