Examples of non-measurable sets in $\mathbb{R}$ I'm a newcomer in real analysis. I am learning the concept of measurable by myself using Royden's book "Real Analysis". I have a question regarding measurable sets. The following definition comes from Royden's book (page 35).
Definition: A set $E$ is said to be measureable provided for any set $A$,
$$m^*(A)=m^*(A\cap E)+m^*(A\cap E^C)$$
where $m^*(\cdot)$ denotes the outer measure of a set.
To me, intuitively the above equation holds for all sets.
In $\mathbb{R}$, I think a set can either be an interval or a series of isolated points (right?). It seems these kinds of sets are all measurable by the definition. Can anybody give me an example of non-measureable sets so that I can have an intuitive understanding regarding this concept? Thanks.
 A: 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.
A: 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.
A: Consider that the cardinal ordinal $c=2^{\omega}$ is the cardinal of the set $D$ of  uncountable closed subsets of $\mathbb R$ and that $c$ is also the cardinal of every member of $D.$ 
Let $D=\{E(x): x<c\}.$  For $x<c$ let $f(x), g(x)$ be unequal members of $$E(x)\; \backslash \; \cup_{y<x} \{f(y),g(y)\} .$$ 
Let $A=\{f(x):x<c\}.$ Neither $A$ nor $\mathbb R$ \ $A$ has an uncountable closed subset, so both $A$ and $\mathbb R \backslash A$ have Lebesgue inner measure $0,$ so $A$ is not Lebesgue measurable.
A: 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.
