Examples of non-measurable sets in $\mathbb{R}$
Solution 1:
It is impossible to construct an explicit example of a non-Borel-measurable subset of $ \mathbb{R} $ as any proof of the existence of such a subset must require the Axiom of Choice ($ \mathsf{AC} $). As you may already know, any construction that relies on $ \mathsf{AC} $ is never explicit — $ \mathsf{AC} $ yields only pure existence results.
Before we go into a more detailed explanation, let us introduce some notation first.
- $ \mathsf{ZF} $ — The Zermelo-Fraenkel axioms.
- $ \mathsf{ZFC} $ — $ \mathsf{ZF} + \mathsf{AC} $.
- $ \mathsf{DC} $ — Axiom of Dependent Choice.
- $ \text{Con}(\text{Statement $ P $}) $ — Statement $ P $ is consistent.
It is a well-known set-theoretic result (Theorem 10.6 of The Axiom of Choice by Thomas Jech) that $$ \text{Con}(\mathsf{ZF}) \Longrightarrow \text{Con} (\mathsf{ZF} + \mathbb{R} \text{ is a countable union of countable sets}). $$ Hence, from a model of $ \mathsf{ZF} $, we may construct another model $ M $ of $ \mathsf{ZF} $ in which the statement $$ \mathbb{R} \text{ is a countable union of countable sets} $$ is true. Observe that $ M $ cannot satisfy $ \mathsf{DC} $, for if it did, then as it is provable within $ \mathsf{ZF} + \mathsf{DC} $ that a countable union of countable sets is countable, $ \mathbb{R} $ would be countable in $ M $. This is contradictory as it is provable within $ \mathsf{ZF} $ that $ \mathbb{R} $ is uncountable (see here).
We now reason within $ M $. Let $ S \subseteq \mathbb{R} $; the claim is that $ S $ is Borel-measurable. We have, a priori, a sequence $ (A_{n})_{n \in \mathbb{N}} $ consisting of countable subsets of $ \mathbb{R} $ such that $ \displaystyle \mathbb{R} = \bigcup_{n=1}^{\infty} A_{n} $. Then $$ S = \bigcup_{n=1}^{\infty} (S \cap A_{n}). $$ As it is provable within $ \mathsf{ZF} $ that a subset of a countable set is countable, each $ S \cap A_{n} $ is countable. Hence, $ S $ is a countable union of countable sets. As a $ \sigma $-algebra is by definition closed under a countable union, and as singletons in $ \mathbb{R} $ are Borel-measurable, it follows that a countable subset of $ \mathbb{R} $ is Borel-measurable and that $ S $, being a countable union of countable (hence Borel-measurable) subsets of $ \mathbb{R} $, is Borel-measurable. Therefore, \begin{align} \text{Con}(\mathsf{ZF}) \Longrightarrow \text{Con} (\mathsf{ZF} + \text{Every subset of $ \mathbb{R} $ is Borel-measurable}). \end{align} We now see that it is consistent with $ \mathsf{ZF} $ alone that every subset of $ \mathbb{R} $ is Borel-measurable. However, this situation is inadequate, because without $ \mathsf{DC} $ in $ M $, we cannot develop much of real analysis, e.g., we cannot establish the $ \sigma $-additivity of the standard Borel measure.
If $ \mathsf{DC} $ is allowed, what are the implications then? This is explained in the next section.
Work done by Robert Solovay and Saharon Shelah has yielded the following result: \begin{align} & ~ \text{Con}(\mathsf{ZFC} + \text{An inaccessible cardinal exists}) \\ \iff & ~ \text{Con} (\mathsf{ZF} + \mathsf{DC} + \text{Every subset of $ \mathbb{R} $ is measurable}). \end{align} The forward implication was the first to be proved, by Solovay in his famous paper A Model of Set Theory in Which Every Set of Reals is Lebesgue Measurable. Shelah later proved the backward implication in his paper Can You Take Solovay's Inaccessible Away?
One thing is now clear: If one wants a model of $ \mathsf{ZF} $ where $ \mathsf{DC} $ is satisfied so as to be able to do real analysis, and demand at the same time that all subsets of $ \mathbb{R} $ be Borel-measurable, then the price to pay is to posit that the existence of inaccessible cardinals is compatible with $ \mathsf{ZFC} $.
Actually, it is not entirely unreasonable to assume that inaccessible cardinals exist. In fact, modern category theory takes their existence for granted by postulating the existence of Grothendieck universes (a formal proof that the existence of Grothendieck universes is equivalent to the existence of inaccessible cardinals may be found in SGA 4, in the appendix Univers written by Bourbaki). Hence, let us assume, without losing too much sleep, that a model $ M $ exists that satisfies $$ \mathsf{ZF} + \mathsf{DC} + \text{Every subset of $ \mathbb{R} $ is Borel-measurable}. $$
We can now demonstrate that any proof of the existence of a non-Borel-measurable subset of $ \mathbb{R} $ relies on $ \mathsf{AC} $. Assume, for the sake of contradiction, that the proof does not depend on $ \mathsf{AC} $, i.e., it is provable within $ \mathsf{ZF} $ that a non-Borel-measurable subset of $ \mathbb{R} $ exists. Then as $ M $ satisfies $ \mathsf{ZF} $, we obtain (inside $ M $) a non-Borel-measurable subset of $ \mathbb{R} $, which contradicts the fact that $ M $ contains no such set. Therefore, $ \mathsf{AC} $ (or some weak version thereof) is indeed required for the proof.
Solution 2:
Unfortunately, there's no such thing as a constructible nonmeasurable set--that is, we cannot explicitly define one. We always end up relying on some choice principle. Here's an example to give you an idea of what a non-measurable set might look like.
Solution 3:
Shiyu, If m* denotes the Lebesgue outer measure and if the measurability is defined as you did, what you obtain is the Lebesgue measure in $\mathbb{R}$ (a complete measure), which differs from a Borel measure. There are more non-Borel sets and a non-Borel set may still be Lebesgue measurable by a cardinality argument.
As others have pointed out, finding a Lebesgue nonmeasurable set requires AC. Many books in analysis have some standard "constructions" using AC. The following is my preferred method to obtain Lebesgue nonmeasurable sets and functions:
It follows from AC that the vector space $\mathbb{R}$ over the field $\mathbb{Q}$ has a basis (Hamel). A set map from this basis to $\mathbb{R}$ would extend to a $\mathbb{Q}$-linear function from $\mathbb{R}$ to $\mathbb{R}$. This method produces infinitely many $\mathbb{Q}$-linear functions which are not $\mathbb{R}$-linear. An $\mathbb{R}$-linear function from $\mathbb{R}$ to $\mathbb{R}$ always has the form $f(x)=cx$. It is also a good exercise problem to show that every Lebesgue measurable $\mathbb{Q}$-linear function is $\mathbb{R}$-linear. Hence we have obtained many Lebesgue nonmeasurable functions.