Example of a Lebesgue measurable set that can't be constructed from Borel sets and projections?

Question

The Borel sigma algebra on $\mathbb{R}^n$ is obtained by starting with open sets and repeatedly applying the operations of complement, countable union, countable intersection. Now Henri Lebesgue famously made the mistake of thinking that the projection of a Borel set is always a Borel set. In reality, the projection of a Borel set need not be a Borel set, although it is still Lebesgue measurable. So that is a way of constructing a Lebesgue measurable set that is not a Borel set.

But my question is, what is an example of a Lebesgue measurable set that cannot be constructed in this way? That is, what is a Lebesgue measurable set that cannot be constructed by starting with open sets in $\mathbb{R}^n$ and repeatedly applying the operations of complement, countable union, countable intersection, and projection?

Answer 1

Start with a set $A$ of measure zero. Choose some insane subset $B\subseteq A$ (e.g. a Bernstein set if $A$ is closed, or a Vitali set if it makes sense). Then $B$ is Lebesgue measurable, but not analytic.

Also, somewhat trivially (relative to the fact that analytic sets are measurable), every coanalytic set is Lebesgue measurable (in particular, a coanalytic, non-Borel set is not analytic, but measurable). Similarly, every countable Boolean combination of analytic sets is measurable.

More generally, every Lebesgue measurable (or, indeed, measurable with respect to any given regular measure) is of the form $G\mathbin\triangle N$, where $G$ is a $G_\delta$ set and $N$ is of measure $0$. It will be as well behaved as $N$ is (more or less).

Note that you cannot give an "explicit" example, as without axiom of choice, it is consistent that every set of reals is Borel (or even a countable union of countable sets).

Answer 2

As tomasz mentioned, there is not any truly "explicit" example. However, you can give a simple cardinality argument that such a set must exist. Namely, the cardinality of the collection of sets that can be constructed using your operations is $2^{\aleph_0}$ (the proof of this is almost exactly the same as for Borel sets, just with projection added as an extra operation, see cardinality of the Borel $\sigma$-algebra of a second countable space for instance). On the other hand, if $N$ is a null set of cardinality $2^{\aleph_0}$, then $N$ has $2^{2^{\aleph_0}}$ different subsets and all of them are Lebesgue measurable, so not all of them can be constructed from your operations.

Answer 3

This kind of question can always be answered via a brute-force diagonalization argument (assuming a bit of Choice of course):

• Fix your favorite size-continuum measure-zero set $X$.

• Show that the class $\mathcal{C}$ of sets you care about - e.g. Borel, or projective, or ... - has size continuum: that is, there are real "codes" for each set. This will rely on $\mathcal{C}$ being generated from a "small" set (e.g. $\{$opens$\}$) by a "small" number of "simple" operations (e.g. finitely many finitary or countable-arity operations). This is the bit that uses choice! Without choice, e.g., "Borel" and "Borel-coded" are distinct.

• Now fix a bijection $b:X\cong \mathcal{C}$, and let $$A=\{x\in X: x\not\in b(x)\}.$$ $A$ will always be measurable, since it's a subset of a measure-zero set.

Note that this approach is actually fairly constructive, relative to the "coding" notion in the second bulletpoint, and this coding usually isn't too bad. For example, the relation "$r$ is in the Borel set coded by $x$," using the usual notion of "code" in this context, is Borel once we restrict to $x$ in the set of Borel codes, and this latter set is coanalytic; so the whole relation $$\{\langle r,x\rangle: \mbox{$x$ is a Borel code for a Borel set containing $r$}\}$$ is coanalytic or $\Pi^1_1$ ("$x$ is a Borel code, and there is no realizer to $r$ being in the code for the complement of $x$").