Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T13:24:32Z http://mathoverflow.net/feeds/question/102386 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102386/is-a-random-subset-of-the-real-numbers-non-measurable-is-the-set-of-measurable Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? Gene S. Kopp 2012-07-16T20:21:25Z 2012-11-29T22:24:54Z <p>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.</p> <p>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?</p> <p>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.</p> <p>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)$?</p> <p>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.</p> http://mathoverflow.net/questions/102386/is-a-random-subset-of-the-real-numbers-non-measurable-is-the-set-of-measurable/102388#102388 Answer by Andreas Blass for Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? Andreas Blass 2012-07-16T21:02:59Z 2012-07-16T21:02:59Z <p>The answer to your second question (assuming the axiom of choice, to dodge Asaf's comment) is that <code>$2^{\mathbb R}/\Sigma$</code> 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]$.</p> <p>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 <code>$2^{\mathbb R}/\Sigma$</code>.</p> http://mathoverflow.net/questions/102386/is-a-random-subset-of-the-real-numbers-non-measurable-is-the-set-of-measurable/102390#102390 Answer by Will Sawin for Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? Will Sawin 2012-07-16T21:23:20Z 2012-07-16T21:23:20Z <p>$\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).</p> <p>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.</p> <p>This is clearly a sigma-algebra. It contains the product sigma-algebra because it contains sets of the form <code>$\{T\in 2^{\mathbb R}| x\in T\}$</code> 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.</p> http://mathoverflow.net/questions/102386/is-a-random-subset-of-the-real-numbers-non-measurable-is-the-set-of-measurable/102392#102392 Answer by Gerald Edgar for Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? Gerald Edgar 2012-07-16T21:50:34Z 2012-07-16T21:50:34Z <p>See this amazing paper ...</p> <p>Fremlin, David H.; Talagrand, Michel<br> A decomposition theorem for additive set-functions, with applications to Pettis integrals and ergodic means. <em>Math. Z.</em> 168 (1979), no. 2, 117–142. </p> <p><a href="http://www.ams.org/mathscinet-getitem?mr=544700" rel="nofollow">http://www.ams.org/mathscinet-getitem?mr=544700</a> </p> http://mathoverflow.net/questions/102386/is-a-random-subset-of-the-real-numbers-non-measurable-is-the-set-of-measurable/102409#102409 Answer by Michael Greinecker for Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? Michael Greinecker 2012-07-17T00:12:59Z 2012-07-17T00:12:59Z <p>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. </p> <p>For the reason given by Will Sawin, the naive approach doesn't work quite well. For Lebesgue measure, some intuition comes from <a href="http://en.wikipedia.org/wiki/Lusin%2527s_theorem" rel="nofollow">Lusin's theorem</a> 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.</p> <p>The general tradeoff between independence and measurable sample realizations is strongly expressed in the following result <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2689" rel="nofollow">of Yeneng Sun</a>: </p> <p><strong>Proposition:</strong> 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.</p> <p>Note that the independence condition in this result is quite weak. Sun calls it <em>almost sure pairwise independence</em>. 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 <em>rich Fubini extensions</em> 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: <a href="http://www.sciencedirect.com/science/article/pii/S0022053104002224" rel="nofollow">The exact law of large numbers via Fubini extension and characterization of insurable risks (2006)</a> </p> <p>A systematic study of rich Fubini extensions was done by Konrad Podczeck in the paper <a href="http://www.springerlink.com/content/l071408382mp0177/" rel="nofollow">On existence of rich Fubini extensions (2010)</a>, 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 <em>super-atomlessnes</em> (and which is known by a lot of other names such as <a href="http://mathoverflow.net/questions/101855/applied-problems-in-probability-which-can-not-be-modelled-on-polish-spaces/101876#101876" rel="nofollow">saturation</a>): </p> <p>For any subset $A$ with positive measure, the <a href="http://www.encyclopediaofmath.org/index.php/Measure_algebra_%28measure_theory%29" rel="nofollow">measure algebra</a> of the trace on $A$ does not coincide with the measure algebra of a countably generated space. </p> <p>Lebesgue measure on the unit interval does not satisfy this condition, but there exists extensions of Lebesgue measure that are superatomless. </p> <p><strong>Conclusion:</strong> 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.</p> http://mathoverflow.net/questions/102386/is-a-random-subset-of-the-real-numbers-non-measurable-is-the-set-of-measurable/114936#114936 Answer by Chad Brewbaker for Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable? Chad Brewbaker 2012-11-29T22:24:54Z 2012-11-29T22:24:54Z <p>R isn't even computationally enumerable. Any computational scheme you come up with to define your random set will be by definition non-random since you are only hitting a computable subset or excluding a computable subset. Essentially R = random subset of R, IMHO. The question could be simplified to "Is R Lebesgue measurable?"</p>