# Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable?

One might say, "a random subset of $\mathbb{R}$ is not Lebesgue measurable" without really thinking about it. But if we unpack the standard definitions of all those terms (and work in ZFC), it's not so clear.

Let $\Sigma \subset 2^\mathbb{R}$ be the sigma-algebra of all Lebesgue measurable sets. Give $2^\mathbb{R}$ the product measure. (It's a product of continuum many copies of the two-point set.) We want to say that $\Sigma$ is a null set in $2^\mathbb{R}$...but is $\Sigma$ even measurable?

Laci Babai posed this question casually several years ago, and no one present knew how to go about it, but it might be easy for a set theorist.

Also, a related question: Think of $2^\mathbb{R}$ as a vector space over the field with two elements and $\Sigma$ as a subspace. (Addition is xor, that is, symmetric set difference.) What is $\dim\left(2^\mathbb{R}/\Sigma\right)$?

It's not hard to see that $\dim\left(2^\mathbb{R}/\Sigma\right)$ is at least countable, so if $\Sigma$ were measurable, it would be a null set. But that's as far as I made it.

-
Allow me to be the wiseguy that brings it up, in a model of ZF without the axiom of choice, in which all sets of real numbers are measurable the answer is: Yes, $\Sigma$ is measurable and the dimension of this vector space is $1$. :-) –  Asaf Karagila Jul 16 '12 at 20:30
Relevant: terrytao.wordpress.com/2008/10/14/… –  Qiaochu Yuan Jul 16 '12 at 20:44
@Asaf: $\:$ No, in that case the dimension of the vector space is $0$. $\;\;$ –  Ricky Demer Jul 16 '12 at 20:56
Right, thanks Ricky. I keep confusing those finite numbers! :-P –  Asaf Karagila Jul 16 '12 at 21:02
...because the only subset of $\Sigma$ which is measurable with respect to the product sigma-algebra is the empty set, and the only superset of $\Sigma$ which is measurable in this sense is the whole of $2^\mathbb{R}$. This is because measurability of a subset of $2^\mathbb{R}$ can only depend on sampling at a countable set of points in $\mathbb{R}$. Determining whether a set $S$ is in $\Sigma$ requires sampling it at uncountably many points. –  George Lowther Jul 16 '12 at 21:17

## 4 Answers

The answer to your second question (assuming the axiom of choice, to dodge Asaf's comment) is that $2^{\mathbb R}/\Sigma$ has dimension $2^{\mathfrak c}$, where $\mathfrak c=2^{\aleph_0}$ is the cardinality of the continuum. The main ingredient of the proof is a partition of $[0,1]$ into $\mathfrak c$ subsets, each of which intersects every uncountable closed subset of $[0,1]$. To get such a partition, first note that there are only $\mathfrak c$ closed subsets of $[0,1]$, so you can list them in a sequence of length (the initial ordinal of cardinality) $\mathfrak c$ in such a way that each closed set is listed $\mathfrak c$ times. Second, recall that every uncountable closed subset of $[0,1]$ has cardinality $\mathfrak c$. Finally, do a transfinite inductive construction of $\mathfrak c$ sets in $\mathfrak c$ steps as follows: At any step, if the closed set at that position in your list is $C$ and if this is its $\alpha$-th occurrence in the list, then put an element of $C$ into the $\alpha$-th of the sets under construction, being careful to use an element of $C$ that hasn't already been put into another of the sets under construction. You can be this careful, because fewer than $\mathfrak c$ points have been put into any of your sets in the fewer than $\mathfrak c$ preceding stages, while $C$ has $\mathfrak c$ points to choose from. At the end, if some points in $[0,1]$ remain unassigned to any of the sets under construction, put them into some of these sets arbitrarily, to get a partition of $[0,1]$.

Once you have this partition, notice that every piece has outer measure 1, because otherwise it would be disjoint from some closed set that has positive measure and is therefore uncountable. This implies that, among the $2^{\mathfrak c}$ sets that you can form as unions of your partition's pieces, only $\varnothing$ and $[0,1]$ can be measurable. In particular, no finite, nonempty, symmetric difference of these pieces is measurable. That is, they represent linearly independent elements of $2^{\mathbb R}/\Sigma$.

-
Nice argument. Thanks for the answer! –  Gene S. Kopp Jul 16 '12 at 23:47

$\Sigma$ is clearly not a measurable set in the product sigma-algebra, moreover it is so non-measurable that every measurable set containing it is the whole set (any any measurable set contained in it is trivial).

Proof: Consider the set of sets of sets of real numbers consisting of all sets of sets of real numbers $S$ where whether a set of real numbers $T$ is contained in $S$ is determined by $T \cap U$ for some countable set of real numbers $U$. That is, if $T' \cap U=T \cap U$, then $T' \in S$ if and only if $T \in S$. Less formally, this set of sets of sets of real numbers consists of all properties that can be checked by only looking at countably many points.

This is clearly a sigma-algebra. It contains the product sigma-algebra because it contains sets of the form $\{T\in 2^{\mathbb R}| x\in T\}$ for each real number $x$. And it clearly does not contain the set of measurable sets, nor any proper set containing the set of measurable sets, nor any nontrivial set contained in the set of measurable sets, because one can add or remove arbitrary countable sets from a measurable/non-measurable set and preserve its measurability/non-measurability, and both measurable and non-measurable sets exist.

-
+1. Ah, of course. The product sigma-algebra contains only sets $\mathcal{S}$ of sets of real numbers in which membership $S \in \mathcal{S}$ is determined by membership $s \in S$ for countably many real numbers $s$. Thanks! –  Gene S. Kopp Jul 16 '12 at 23:46

The problem of choosing subsets at random has been studied in a rather different context in mathematical economics. Suppose we choose a subset of $[0,1]$ by independently throwing a fair coin for each number. Heuristically, such a set should have measure $1/2$. For what we do is randomly choose an indicator function with pointwise expectation $1/2$. By some intuitive apeal to a law of large numbers, the sample realizations should have the same expectation. This kind of reasoning is widely used in economics. A large population is modeled by a continuum and even when each person faces individual uncertainty, there should be no aggregate uncertainty.

For the reason given by Will Sawin, the naive approach doesn't work quite well. For Lebesgue measure, some intuition comes from Lusin's theorem to the effect that every measurable function is continuous on a "large" subset. Continouity is a condition to the effect that the value at a point is closely related to the value at nearby points. If you choose independently at each value, you wouldn't expect to get a function continuous on a large set.

The general tradeoff between independence and measurable sample realizations is strongly expressed in the following result of Yeneng Sun:

Proposition: Let $(I,\mathcal{I},\mu)$ and $(X,\mathcal{X},\nu)$ be probability spaces with (complete) product probability space $(I\times X,\mathcal{I}\otimes\mathcal{X},\mu\otimes\nu)$ and $f$ be a jointly measurable function from $I\times X$ to $\mathbb{R}$ such that for $\mu\otimes\mu$-almost all $(i,j)$ the functions $f(i,\cdot)$ and $f(j,\cdot)$ are independent. Then for $\mu$-almost all $i$, the function $f(i,\cdot)$ is constant.

Note that the independence condition in this result is quite weak. Sun calls it almost sure pairwise independence. But an important discovery by Sun was that if joint measurability and almost sure pairwise independence were compatible, one could obtain an exact law of large numbers for a continuum of random variables by an application of Fubini's theorem. In particular, such a law of large numbers holds for extensions of the product spaces that allow for the conclusion of Fubini's theorem to hold and still allow for nontrivial (a.s. pairwise) independent processes. He called such extensions rich Fubini extensions and gave one example of such a product space: The Loeb product of two hyperfinite Loeb spaces. So one can get natural random sets for some spaces. The reference is: The exact law of large numbers via Fubini extension and characterization of insurable risks (2006)

A systematic study of rich Fubini extensions was done by Konrad Podczeck in the paper On existence of rich Fubini extensions (2010), in which he has essentially shown that one can choose random subsets of a probability space if and only if the probability space has the following property, which he called super-atomlessnes (and which is known by a lot of other names such as saturation):

For any subset $A$ with positive measure, the measure algebra of the trace on $A$ does not coincide with the measure algebra of a countably generated space.

Lebesgue measure on the unit interval does not satisfy this condition, but there exists extensions of Lebesgue measure that are superatomless.

Conclusion: One cannot obtain random Lebesgue measurable sets in a sensible way by choosing independently elements, but one can choose random sets in an extension of Lebesgue measure this way.

-

See this amazing paper ...

Fremlin, David H.; Talagrand, Michel
A decomposition theorem for additive set-functions, with applications to Pettis integrals and ergodic means. Math. Z. 168 (1979), no. 2, 117–142.

-