Last year on this blog, I sketched out a non-rigorous probabilistic argument justifying the following well-known theorem:
Theorem 1. (Non-measurable sets exist) There exists a subset
of the unit interval
which is not Lebesgue-measurable.
The idea was to let E be a “random” subset of . If one (non-rigorously) applies the law of large numbers, one expects E to have “density” 1/2 with respect to every subinterval of
, which would contradict the Lebesgue differentiation theorem.
I was recently asked whether I could in fact make the above argument rigorous. This turned out to be more difficult than I had anticipated, due to some technicalities in trying to make the concept of a random subset of (which requires an uncountable number of “coin flips” to generate) both rigorous and useful. However, there is a simpler variant of the above argument which can be made rigorous. Instead of letting E be a “random” subset of
, one takes E to be an “alternating” set that contains “every other” real number in
; this again should have density 1/2 in every subinterval and thus again contradict the Lebesgue differentiation theorem.
Of course, in the standard model of the real numbers, it makes no sense to talk about “every other” or “every second” real number, as the real numbers are not discrete. If however one employs the language of non-standard analysis, then it is possible to make the above argument rigorous, and this is the purpose of my post today. I will assume some basic familiarity with non-standard analysis, for instance as discussed in this earlier post of mine.
We begin by selecting a non-principal ultrafilter and use it to construct non-standard models
of the natural numbers
and the unit interval
by the usual ultrapower construction. We then let
be an unlimited non-standard number, i.e. a non-standard natural number larger than any standard natural number. (For instance, one could take N to be the equivalence class in
of the sequence
.)
We can partition the non-standard unit interval into
(non-standard) intervals
for
(the overlap of these intervals will have a negligible impact in our analysis). We then define the non-standard set
to be the union of those
with j odd; this is the formalisation of the idea of “every other real number” in the introduction. The key property about *E that we need here is the following symmetry property: if
is any standard dyadic interval, then the (non-standard counterpart to the) interval I can be partitioned (modulo (non-standard) rationals) as the set
and its reflection
. This demonstrates in particular that
has (non-standard) density 1/2 inside I, but we will need to use the symmetry property directly, rather than the non-standard density property, because the former is much easier to transfer to the standard setting than the latter.
We now return to the standard world, and introduce the standard set , defined as the collection of all standard
whose non-standard representative
lies in
. This is certainly a standard subset of
. We claim that it is not Lebesgue measurable, thus establishing Theorem 1. To see this, recall for any standard dyadic interval
, that every non-standard irrational element of I lies in exactly one of *E or
. Applying the transfer principle, we conclude that every standard irrational element of I lies in exactly one of E or
. Thus, if E were measurable, the density of E in the dyadic interval I must be exactly 1/2. But this contradicts the Lebesgue differentiation theorem, and we are done.
Remark 1. One can eliminate the non-standard analysis from this argument and rely directly on the non-principal ultrafilter p. Indeed, if one inspects the ultrapower construction carefully, one sees that (outside of the terminating binary rationals, which do not have a unique binary expansion), E consists of those numbers in whose 1s in the binary expansion lie in p. The symmetry property of E then reflects the non-principal ultrafilter nature of p, in particular the fact that membership of a set
in p is insensitive to any finite modification of A, and reversed by replacing A with its complement. On the other hand, one cannot eliminate the non-principal ultrafilter entirely; once one drops the axiom of choice, there exist models of the real line in which every set is Lebesgue measurable, and so it is necessary to have some step in the proof of Theorem 1 that involves this axiom. In the above argument, choice is used to find the non-principal ultrafilter p.
Remark 2. It is tempting to also make the original argument, based on randomness, work, but I was unable to push it through completely. Certainly, if one sets to be a (non-standardly) random collection of the
, then with probability infinitesimally close to 1, the (non-standard) density of
in any standard dyadic interval (or indeed, any standard interval) is infinitesimally close to 1/2, thanks to the law of large numbers. However, I was not able to transfer this fact to tell me anything about E; indeed, I could not even show that E was non-empty. (Question: does there exist a non-standard subset of
of positive (non-infinitesimal) measure which avoids all standard real numbers? I don’t know the answer to this.)
[Update, Oct 14: some LaTeX quirks fixed.]
18 comments
Comments feed for this article
14 October, 2008 at 11:36 am
g
Typo alert: in the paragraph beginning “We begin”, you’re missing the star on the first instance of *N. [Corrected – T.]
14 October, 2008 at 12:42 pm
gowers
That reminds me of a proof I once spotted of the existence of non-Ramsey colourings of the infinite subsets of the natural numbers. (I don’t claim to have been the first to spot it though.) Recall that a non-Ramsey colouring is a red-blue colouring where every infinite set of natural numbers has at least one red subset and at least one blue subset. The usual proof that such colourings exist is to call two sets equivalent if they have a finite symmetric difference, to choose one set from each equivalence class (using the axiom of choice) and to colour each set red if it differs from the representative of its equivalence class by an even amount and blue otherwise. But one can achieve the same in a rather pretty way using a non-principal ultrafilter
. Given an infinite set
, define a set
to be the set of all
such that the size of
is even. Then if
is infinite, so is
. Now colour
red if
belongs to
. Then if you change one element of
, you end up changing every element of
from that point on. Thus, if
differs from
by a single element, then
is differs from the complement of
by a finite amount. So the colour of
is different from the colour of
. I like to think of this as assigning a “parity” to the infinite sets.
14 October, 2008 at 2:05 pm
gowers
PS Two further tiny comments. First, in what I said above the fact that if
is infinite then so is
is irrelevant. Secondly, there’s a sort of not-quite-typo at the beginning of your second paragraph, where you have a pair of nested turnings out. And while I’m at it, you have “recall that … that” in the middle of the last paragraph before remark 1. [Fixed – T.]
14 October, 2008 at 8:52 pm
jozsef
Dear Terry,
Could you please compare your construction to the “classical” constructions?
I’m not sure that I understood correctly but it seems that your construction – similarly to previous examples – finds a tiling of [0,1] and chooses exactly one element from each tile to get E. In classical examples one can choose an everywhere dense countable additive subgroup and its cosets for tiling. Your tiling seems to be more general. Anyways, if you could point out the basic differences/similarities that would be very helpful.
15 October, 2008 at 1:15 am
gowers
Somehow this question of yours won’t let me go, and I’ve thought of a rather strange way of producing a random subset of [0,1]. In fact, it’s strange enough that I think I may have made a mistake, as I’ll explain later.
The idea is very simple, however. I’ll choose a random set of 01-sequences rather than reals, because it’s more convenient. I begin by choosing a random collection
of finite 01-strings. That is, for each string of length
, I randomly decide whether or not it belongs to
. I also let
be a non-principal ultrafilter. And then for each infinite string
I let
be the set of all
such that the
th initial segment of
belongs to
. I then choose
if and only if
belongs to
.
Now I’ll argue slightly less rigorously, so if there’s a mistake anywhere then it’s here. I want to claim that the choices I’ve just made are independent in the strongest possible sense: that if
is a string and I know for every other string
whether I’ve chosen it or not, then the probability that I’ve chosen
is still 1/2. To prove this, WLOG
is the string of all zeros. I claim that if I change the choices I made about which strings of the form
belong to
, then the only infinite string that I can affect is the all-zero string. And indeed, that is the case because for all other strings I’ve affected at most finitely many initial segments and therefore perturbed
by at most a finite set, which doesn’t affect whether or not it belongs to
. But since what I do to finite strings of zeros is completely arbitrary, the probability that
is 1/2.
It’s at this point that I see my mistake. Since an ultrafilter is a non-measurable set, I can’t in fact talk about the probability that a random sequence belongs to it. Nevertheless, I’ll leave this comment here as for me at any rate it clarified the problem. I was going to go on to point out a “paradox”: that I made countably many independent choices and used them to generate uncountably many independent choices.
Having said that, since one is trying to construct a non-measurable set, it is in a sense necessary that one will not in fact be able to prove rigorous probabilistic statements. So perhaps the above construction isn’t a complete waste of time. In some sense, it really does feel as though the probability that
is 1/2, since if you reverse all your decisions about whether the initial segments belong to
, then you reverse the outcome. So that feels like a bijective proof that the probability is 1/2.
15 October, 2008 at 5:53 am
K. P. Hart
To Jozsef: the tiling of the unit interval is by pairs of numbers whose sets of ones in their binary expansion are complementary; the ultrafilter picks one from each pair.
As such it is akin to Van Vleck’s construction, which can be found on jstor:
* On Non-Measurable Sets of Points, with an Example
* Edward B. Van Vleck
* Transactions of the American Mathematical Society, Vol. 9, No. 2 (Apr., 1908), pp. 237-244
* Published by: American Mathematical Society
* Stable URL: http://www.jstor.org/stable/1988654
15 October, 2008 at 6:02 am
Kevin O'Bryant
It’s a matter of taste, of course, but I find the following exposition of the definition of
simpler. Let
be an unlimited (i.e., infinite) natural number, and
is the set of (standard) irrational real numbers
for which the
-th binary digit of
is 1.
By the way, this construction (and a proof of Ramsey’s theorem akin to gowers’ comment) can be found in Goldblatt’s magnificent introduction to nonstandard analysis “Lectures on the Hyperreals”.
15 October, 2008 at 6:34 am
K. P. Hart
Addendum:
here is Sierpinski’s proof that from an ultrafilter one can construct directly a non-measurable subset of [0,1]:
http://matwbn.icm.edu.pl/ksiazki/fm/fm30/fm30116.pdf
15 October, 2008 at 7:20 am
wonghang
Hi Terry,
I am not a expert in mathematics. Hope that I do not misunderstand your argument.
I do not understand what do you mean by “E is nonempty”? E is a random set, how to define nonempty random set? To prove there is a non-measurable set using randomness argument. We are trying to use Law of Large Numbers, which is talking about “average” behavior. Do we need to define a “expected value” of a random set in order to prove the theorem?
15 October, 2008 at 10:48 am
Terence Tao
Dear Tim: Somewhat amusingly, even if your argument doesn’t quite construct a random subset of [0,1], it does at least achieve (non-constructively) the original aim in this post, namely to construct a non-measurable set, since if the event that the random sequence lies in the ultrafilter is non-measurable, it is not hard to convert that fact to produce a non-measurable subset of [0,1]. So I guess this does achieve a proof of the existence of non-measurable sets which is somewhat in the spirit of my original intention…
Dear Jozsef: the textbook construction of nonmeasurable sets follows quite directly from the axiom of choice, whereas the one here is very closely tied to the existence of an ultrafilter (one can, for instance, recover the ultrafilter from the set E). The existence of non-principal ultrafilters follows easily from Zorn’s lemma, of course, but I don’t know of any way to build these objects directly from the axiom of choice without basically repeating the entire proof of Zorn’s lemma, which is not entirely trivial. So I would imagien that the two constructions are genuinely different from each other, even if tiling is the key idea in both of them.
Dear Wonghang: I corrected some slight LaTeX errors in the post. My main question can be stated without randomness: does there exist a nonstandard subset *E of the nonstandard interval *[0,1] of positive (non-infintesimal) Lebesgue measure, such that the standard portion E of *E is empty (i.e. *E contains no standard real numbers)? I don’t know the answer to this. I am specifically interested in the case when *E is a random collection of intervals of length 2^{-n} for some unlimited integer n, in which case I would like the statement to be true for “generic” choices of such sets (whatever that means).
Dear Kevin and K.P.: Thanks for the references!
16 October, 2008 at 12:22 am
K. P. Hart
For those who like to go back to the sources: here are links to papers of
Ulam: http://matwbn.icm.edu.pl/ksiazki/fm/fm14/fm14118.pdf and
Tarski: http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm1515.pdf
Both construct non-trivial finitely additive 0-1-valued measures that vanish on singletons; the sets of measure 1 form an ultrafilter.
17 October, 2008 at 10:41 pm
jhusdhui
Dear Terry,
Can you elaborate on the original question: how to prove that a “random” subset of the reals isn’t measurable?
20 October, 2008 at 11:38 am
K. P. Hart
In (at least) one sense this cannot be done. A subset of [0,1] is a point in the product $\latex 2^{[0,1]}$ and this product carries a product measure induced by the measure $\latex \mu(\{0\})=\mu(\{1\})=1/2$. Every element of the sigma-algebra generated by the cylinders is determined by countably many coordinates, which means that every such set of positive measure contains both points that represent measurable sets and points that represent non-measurable sets. This implies that the sets M (points that represent measurable sets) and N (points that represent non-measurable sets) both have outer measure 1 and hence are not measurable with respect to the coin-tossing measure. This means that tossing a coin once for each real does not automatically lead to a non-measurable set.
9 September, 2010 at 10:55 pm
245A, Notes 1: Lebesgue measure « What’s new
[…] events as “ is Lebesgue measurable”. (For some further discussion of this point, see this post.) So we now turn to more rigorous arguments that establish the existence of non-measurable sets. […]
12 November, 2013 at 7:23 am
Koushik Ghosh
Sir, is it not possible to make the argument free of non-standard analysis language.
12 November, 2013 at 7:31 am
Koushik Ghosh
i mean also ultrafilter. a elementary language proof
15 April, 2015 at 3:28 am
Anonymous
sir help me about the topics & exa. cauchy pde of first order
17 May, 2018 at 6:43 am
Alexander Pruss
For what it’s worth, if we have enough saturation in the non-standard model, there will be a *-finite internal set F containing every element of the standard interval [0,1]. Then *[0,1] \ F will have full *-measure but won’t meet any reals. I assume, though, your non-standard model is based on an ultrafilter on the naturals, so this trivial observation won’t help you.