Examples of non-measurable sets in $\mathbb{R}$

I'm a newcomer in real analysis. I am leaning 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.

-
I'm sure that if you read a little farther in Royden you will see such an example. Be patient. –  Gerry Myerson Nov 1 '12 at 5:01
"In $\mathbb R$, I think a set can either be an interval or a series of isolated points (right?)." No, even many "nice" sets are very far from this description. I suggest looking up the Cantor set. It is closed (and all closed sets are measurable), it contains no intervals, and it contains no isolated points. –  Jonas Meyer Nov 1 '12 at 5:23
@GerryMyerson: I finally know what you mean. There is a section in this book talking about nonmeasrable sets. I didn't notice that before. The book is really splendid by the way. –  Shiyu Nov 1 '12 at 10:00
For the classic constructions –  leo Nov 4 '12 at 1:47

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.

-

It is impossible to give an explicit example of a non-Borel-measurable subset of $\mathbb{R}$. This is because proving the existence of such a subset requires the Axiom of Choice (AC). As you may already know, any construction that relies on AC can never be explicit --- AC yields only existence results.

Before we go into a more detailed explanation, let us introduce some notation first.

1. ZF --- The Zermelo-Fraenkel axioms.
2. ZFC --- ZF + AC.
3. DC --- Axiom of Dependent Choice.
4. $\text{Con}(\text{Statement$ P $})$ --- Statement $P$ is consistent.

It is a well-known set-theoretic result (cf. Theorem 10.6 of the book The Axiom of Choice by Thomas Jech) that $$\text{Con}(\text{ZF}) \Longrightarrow \text{Con}(\text{ZF +  \mathbb{R}  is a countable union of countable sets}).$$ Hence, starting with a model of ZF, we may derive a model $\mathcal{M}$ of ZF in which $\mathbb{R}$ is a countable union of countable sets. Observe that $\mathcal{M}$ cannot satisfy DC. If it did satisfy DC, then as it is provable within ZF + DC that a countable union of countable sets is countable, it would follow that $\mathbb{R}$ is countable in $\mathcal{M}$. This is contradictory because it is provable within ZF that $\mathbb{R}$ is uncountable (see (ZF) Every nonempty perfect set in $\mathbb{R}^k$ is uncountable.).

We now reason within $\mathcal{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 $\displaystyle S = \bigcup_{n=1}^{\infty} (S \cap A_{n})$. As it is provable within ZF that any subset of a countable set is countable, each $S \cap A_{n}$ must be countable. Hence, $S$ is a countable union of countable sets. By definition, a $\sigma$-algebra is closed under a countable union; from the fact that a single point of $\mathbb{R}$ is Borel-measurable, it thus 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, $$\text{Con}(\text{ZF}) \Longrightarrow \text{Con}(\text{ZF + Every subset of  \mathbb{R}  is Borel-measurable}).$$ We now see that it is consistent with ZF alone that every subset of $\mathbb{R}$ is Borel-measurable. However, this situation is not very adequate, because without DC in $\mathcal{M}$, we cannot develop much of real analysis. To establish the $\sigma$-additivity of the standard Borel measure requires DC, which we do not have at our disposal.

If 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: $$\text{Con}(\text{ZFC + An inaccessible cardinal exists}) \iff \text{Con}(\text{ZF + DC + Every subset of  \mathbb{R}  is measurable}).$$ 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 ZF where 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 ZFC.

Actually, it is not so unreasonable to assume that inaccessible cardinals exist. In fact, modern category theory takes their existence for granted by assuming the existence of what are called 'Grothendieck universes' (the 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 $\mathcal{M}$ exists that satisfies 'ZF + DC + Every subset of $\mathbb{R}$ is Borel-measurable'.

We can now demonstrate that the proof of the existence of a non-Borel-measurable subset of $\mathbb{R}$ relies on AC. Assume, for the sake of contradiction, that the proof does not depend on AC, i.e., it is provable within ZF that a non-Borel-measurable subset of $\mathbb{R}$ exists. Then as $\mathcal{M}$ satisfies ZF, we obtain (inside $\mathcal{M}$) a non-Borel-measurable subset of $\mathbb{R}$, which contradicts the fact that $\mathcal{M}$ contains no such set. Therefore, AC (or some weak version thereof) is indeed required for the proof.

-
Be careful in your assertion of Solovay's result. He did not show that "ZF + $\exists$ inaccessible" implies "all sets of reals are Lebesgue measurable". He did show that if "ZFC + $\exists$ inaccessible" is consistent, then so is "ZF + $\neg$AC + all sets of reals are Lebesgue measurable." –  Arthur Fischer Nov 1 '12 at 5:22
Actually it is consistent without an inaccessible cardinal that all sets are Lebesgue measures. However if we want Dependent Choice to hold (which is a good thing if we want to develop analysis without worries) then you must do it with an inaccessible cardinal. –  Asaf Karagila Nov 1 '12 at 8:52
@ArthurFischer: Yes, I have updated the accuracy of my post. –  Haskell Curry Nov 1 '12 at 9:39
@AsafKaragila: I have incorporated more material so as to include Shelah's work. Hence, the latest version should be entirely accurate. –  Haskell Curry Nov 1 '12 at 9:41

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.

-