Tensor products of power sets
Greg Kuperberg
arises:
The sigma-completed tensor product P(R) tensor P(R), where R is the real
numbers and P(R) is its power set, is naturally a subset of P(R x R).
Does it equal P(R x R)? That is, can every subset of the plane be
expressed as a countable Boolean word in rectangular subsets?
--
/\ Greg Kuperberg (UC Davis)
/ \
\ / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/
\/ * All the math that's fit to e-print *
James Dolan
greg kuperberg <gr...@manifold.math.ucdavis.edu> wrote:
>I am teaching measure theory this quarter and the following question
>arises:
>
>The sigma-completed tensor product P(R) tensor P(R), where R is the real
>numbers and P(R) is its power set, is naturally a subset of P(R x R).
>Does it equal P(R x R)? That is, can every subset of the plane be
>expressed as a countable Boolean word in rectangular subsets?
how about the diagonal? isn't that an obvious counterexample?
not sure i understand the question, though, since you seem to be
mixing a few different styles of terminology together in a way that
makes it hard to be sure i'm not lacking knowledge of some definition
of some key term.
[Mod. note: The original poster clarifies as follows:
> What I mean is the sigma-algebra on R x R
> generated by sets of the form A x B. A sigma-algebra is closed with
> respect to complementation and countable intersections.
So for example the diagonal is _not_ a counterexample; it is e.g.
\intersection_{n>1} \union_{m>1} B_{n,m} x B_{n,m}
where B_{n,m} is an interval of radius 1/2^n centered at the m-th
(in any fixed ordering) real number of the form (integer)/2^n.
Also: please post with a working email address; occasionally it is useful
for moderators to be able to contact posters. -- Mod.]
Ilias Kastanas
I wondered about this a couple of years ago... It can be cast in other
ways, e.g. is every sigma-algebra (of sets of reals) with cardinality c
contained in some countably generated sigma-algebra? A posting on sci.math
had said the answer to the original question was "no", i.e. the sigma-algebra
of abstract rectangles is not equal to the powerset of the plane.
Well, that might be true; but one thing is certain: it is not provable
in ZFC... because CH implies the answer is "yes". Under CH, R x R is
the union of countably many function graphs (heh... a likely story!), and a
function graph can be dealt with pretty much like above; its complement is
the union of sets A_q x {q} "below", q rational, A_q = {x : f(x) < q}, and
similar sets "above".
I suspected it wouldn't be refutable in ZFC either. I asked Solovay, and he
said he seemed to recall it was indeed independent, by results of Kunen and
Mansfield. I don't have an exact reference, though.
Ilias
Dave L. Renfro
[sci.math.research Fri, 3 May 2002 21:02:48 +0000 (UTC)]
http://mathforum.org/epigone/sci.math.research/coxwheebloo
wrote
> I am teaching measure theory this quarter and the following
> question arises:
>
> The sigma-completed tensor product P(R) tensor P(R), where R
> is the real numbers and P(R) is its power set, is naturally
> a subset of P(R x R). Does it equal P(R x R)? That is, can
> every subset of the plane be expressed as a countable Boolean
> word in rectangular subsets?
If we restrict ourselves to Borel sets or to measurable sets,
then I believe the answer is NO. I know of two or three papers
on this topic, but they're in my office and I'm at home
now and don't remember much about them. [Richard B. Darst
or Roy O. Davies may be an author of at least one of them
that I think appeared in the mid 1960's.] However, if you
do "Borel rectangles" and "measurable rectangles" phrase
searches at google.com and at MathSciNet, you might find
what you want.
Dave L. Renfro
Dave L. Renfro
[sci.math.research 4 May 02 18:38:37 -0400 (EDT)]
http://mathforum.org/epigone/sci.math.research/coxwheebloo
wrote
>> I am teaching measure theory this quarter and the following
>> question arises:
>>
>> The sigma-completed tensor product P(R) tensor P(R), where R
>> is the real numbers and P(R) is its power set, is naturally
>> a subset of P(R x R). Does it equal P(R x R)? That is, can
>> every subset of the plane be expressed as a countable Boolean
>> word in rectangular subsets?
>
> If we restrict ourselves to Borel sets or to measurable sets,
> then I believe the answer is NO. I know of two or three papers
> on this topic, but they're in my office and I'm at home
> now and don't remember much about them. [Richard B. Darst
> or Roy O. Davies may be an author of at least one of them
> that I think appeared in the mid 1960's.] However, if you
> do "Borel rectangles" and "measurable rectangles" phrase
> searches at google.com and at MathSciNet, you might find
> what you want.
What I said isn't correct, plus the papers I was thinking about
have nothing to do with this question. [What I was thinking of were
some papers that show if A and B are Borel subsets of the reals,
then {a + b: a in A and b in B} does not have to be Borel.]
Let's see if I can straighten this out. Let R be the set of
real numbers.
Let B1 and B2 be the Borel sets in R and R^2.
Let M1 and M2 be the Lebesgure measurable sets in R and R^2.
Let P1 and P2 be all subsets of R and R^2.
Finally, given a collection C of subsets in some specified set,
let S[C] be the sigma-algebra generated by C.
Theorems 1 and 2 relate to what I posted earlier and Theorem 3
relates to what I think your question is about.
Theorem 1: B2 = S[B1 x B1].
This can be proved by straightforward methods. See, for example,
the first page of Chapter 5 (p. 154) of Donald L. Cohn's book
"Measure Theory".
Theorem 2: M2 does not equal S[M1 x M1].
Let Y be a nonmeasurable subset of R and r be an element of R.
Then Y x {r} belongs to M2 but not to S[M1 x M1]. On the other
hand, every element of S[M1 x M1] belongs to M2.
Theorem 3: Assuming the continuum hypothesis, P2 = S[P1 x P1].
This is proved in B. V. Rao, "On discrete Borel spaces and
projective sets", Bull. Amer. Math. Soc. 75 (1969), 614-617
[MR 39 #4014]. You can also find it on page 88 of S. M. Srivastava,
"A Course on Borel Sets", Graduate Texts in Mathematics #180,
Springer-Verlag, 1998. The term "Ulam's rectangle problem" is
used for this problem in a 1987 paper by Ciesielski and Galvin
(see below). The question of whether P2 is equal to S[P1 x P1]
is apparently asked in S. Ulam's book "A Collection of Mathematical
Problems", Interscience, 1960, although I don't have a copy of
this book to verify this and to see if Ulam gives any history
about the problem.
Here is a more general result that I found. In what follows,
X and Y are sets and P(X) and P(Y) are the power sets of X and Y
(i.e. the collections of all the subsets of X and Y). My use of
the 'S' operation is the same as above.
B. V. Rao, "On discrete Borel spaces" Acta Math. Acad. Sci.
Hungar. 22 (1971-72), 197-198. [MR 44 #6503]
Assume CH. Then P(X x Y) = S[P(X) x P(Y)] if and only if
(i) or (ii) holds:
(i) Both X and Y have cardinality at most 2^(aleph_0).
(ii) At least one of X and Y is countable.
The following two corollaries of Rao's result can also be found
on the same page of the Srivastava book that I mentioned earlier:
(1) [doesn't require CH, in fact] If the cardinality of X is
greater than 2^(aleph_0), then P(X^2) is not equal to
S[P(X) x P(X)].
(2) Under CH, P(X^2) = S[P(X) x P(X)] <==> X has cardinality
at most 2^(aleph_0).
Some or all of what Rao proved can also be found in Kenneth Kunen's
1968 Ph.D. Dissertation at Stanford.
Other papers along these same lines include:
R. H. Bing, W. W. Bledsoe, and R. E. Mauldin, "Sets generated by
rectangles", Pacific J. Math. 51 (1974), 27-36. [MR 50 #9592]
Andrzej Pelc, "Solution of a problem of Ulam on countable
sequences of sets", Fund. Math. 114 (1981), 113-118. [MR 84h:04006]
K. Ciesielski, and F. Galvin, "Cylinder problem", Fund. Math.
127 (1987), 171-176. [MR 89e:03079]
Dave L. Renfro
David C. Ullrich
Kastanas) wrote:
[...]
>>in article <aautto$gq1$1...@manifold.math.ucdavis.edu>,
>>greg kuperberg <gr...@manifold.math.ucdavis.edu> wrote:
[Is the sigma algebra generated by the sets A x B (A, B subsets
of R) equal to the powerset of R x R?]
>>
>>So for example the diagonal is _not_ a counterexample; it is e.g.
[...]
>
>I wondered about this a couple of years ago... It can be cast in other
>ways, e.g. is every sigma-algebra (of sets of reals) with cardinality c
>contained in some countably generated sigma-algebra? A posting on sci.math
>had said the answer to the original question was "no", i.e. the sigma-algebra
>of abstract rectangles is not equal to the powerset of the plane.
>
>Well, that might be true; but one thing is certain: it is not provable
>in ZFC... because CH implies the answer is "yes". Under CH, R x R is
>the union of countably many function graphs (heh... a likely story!),
Seems extremely unlikely, unless I'm misinterpreting what you mean by
"function graph": If R x R is the union of the graphs of the functions
f_1, ... then every (0, y) is equal to (0, f_n(0)) for some n and
hence R is countable (making this more suitable for sci.math than
here.)
>and a
>function graph can be dealt with pretty much like above; its complement is
>the union of sets A_q x {q} "below", q rational, A_q = {x : f(x) < q}, and
>similar sets "above".
This part sounds like by "function graph" you mean literally "graph of
a function"... huh???
>I suspected it wouldn't be refutable in ZFC either. I asked Solovay, and he
>said he seemed to recall it was indeed independent, by results of Kunen and
>Mansfield. I don't have an exact reference, though.
>
>
>
> Ilias
>
>
>
David C. Ullrich
Greg Kuperberg
>However, if you do "Borel rectangles" and "measurable rectangles" phrase
>searches at google.com and at MathSciNet, you might find what you want.
This is a good suggestion, and it leads to an arXiv article by Arnold
Miller, math.LO/9211206, which begins with a good review of the matter:
As another poster reported - although I didn't previously understand
what he was saying - this article says that it is independent of ZFC
whether the sigma-algebra generated by all set-theoretic rectangles in
R x R is all of P(R x R), or in other words whether
P(R) tensor_sigma P(R) = P(R x R).
Rao showed that the equality is implied by the Continuum Hypothesis
(which to review, states that every infinite subset of R is either
countable or as big as R). Kunen showed that its denial is consistent
with ZFC. Miller's article has many other interesting facts as well.
Greg Kuperberg
> (1) [doesn't require CH, in fact] If the cardinality of X is
> greater than 2^(aleph_0), then P(X^2) is not equal to
> S[P(X) x P(X)].
This is elementary result was part of the motivation for my question.
(Presumably Ulam had it in mind too.) If X is bigger than 2^{aleph_0},
then the diagonal of X^2 does not lie in P(X) tensor_sigma P(X) for
the same reason that if X is infinite, the diagonal does not lie in the
algebraic (or Boolean) tensor product P(X) tensor P(X).
Fred Galvin
> The question of whether P2 is equal to S[P1 x P1] is apparently
> asked in S. Ulam's book "A Collection of Mathematical Problems",
> Interscience, 1960, although I don't have a copy of this book to
> verify this and to see if Ulam gives any history about the
> problem.
This is problem 99 from the "Scottish book". You can find the problem
statement (translated into English, by Ulam I believe), Mauldin's
commentary and a bibliography of six items on pp. 181-182 of _The
Scottish Book_, edited by R. Daniel Mauldin, Birkhaeuser Boston, 1981,
ISBN 3-7643-3045-7. Here is the statement in Ulam's (English) words:
"By a product set in the unit square, we understand the set of all
pairs (x,y) where x belongs to a given set A, y to a given set B. Do
there exist sets which cannot be obtained through the operations of
forming countable sums and differences of sets starting from product
sets? Do there exist nonprojective sets with respect to product
subsets?"
Ilias Kastanas
David C. Ullrich <ull...@math.okstate.edu> wrote:
>On 4 May 2002 18:52:29 GMT, ika...@alumnus.caltech.edu (Ilias
>Kastanas) wrote:
>
>[...]
>>>in article <aautto$gq1$1...@manifold.math.ucdavis.edu>,
>>>greg kuperberg <gr...@manifold.math.ucdavis.edu> wrote:
>
>[Is the sigma algebra generated by the sets A x B (A, B subsets
>of R) equal to the powerset of R x R?]
>
>>>
>>>So for example the diagonal is _not_ a counterexample; it is e.g.
>
>[...]
>
>>
>>I wondered about this a couple of years ago... It can be cast in other
>>ways, e.g. is every sigma-algebra (of sets of reals) with cardinality c
>>contained in some countably generated sigma-algebra? A posting on sci.math
>>had said the answer to the original question was "no", i.e. the sigma-algebra
>>of abstract rectangles is not equal to the powerset of the plane.
>>
>>Well, that might be true; but one thing is certain: it is not provable
>>in ZFC... because CH implies the answer is "yes". Under CH, R x R is
>>the union of countably many function graphs (heh... a likely story!),
>
>Seems extremely unlikely, unless I'm misinterpreting what you mean by
>"function graph": If R x R is the union of the graphs of the functions
>f_1, ... then every (0, y) is equal to (0, f_n(0)) for some n and
>hence R is countable (making this more suitable for sci.math than
>here.)
Who's being snippy now?! Poor sci.math... David, when you get
banned, don't say I didn't warn you.
Yes, I do mean "function graph"... without, uh, banning the second
R from being the domain; i.e. {(x, f_n(x)}'s as well as {(g_n(y), y)}'s.
>>and a
>>function graph can be dealt with pretty much like above; its complement is
>>the union of sets A_q x {q} "below", q rational, A_q = {x : f(x) < q}, and
>>similar sets "above".
>
>This part sounds like by "function graph" you mean literally "graph of
>a function"... huh???
No mystery to it... let h_x(n) enumerate {x} U {predecessors of x in
the w_1 wellordering} (with repetitions if need be), and set f_n(x) = h_x(n);
then tilt your head by pi/2 and set g_m(y) = h_y(m).
>>I suspected it wouldn't be refutable in ZFC either. I asked Solovay, and he
>>said he seemed to recall it was indeed independent, by results of Kunen and
>>Mansfield. I don't have an exact reference, though.
>>
>>
>> Ilias
>>
>
>David C. Ullrich
I did a little checking. Kunen, in his thesis, showed that P(R) X P(R)
not equal to P(R x R) is consistent; the model was the one with Cohen reals.
A. Miller showed the consistency of a universal analytic subset of R x R not
being in P(R) X P(R). In ZFC one can go as far as proving that a universal
analytic set is not in the sigma-algebra of A x B 's, with arbitrary A and
measurable B.
Ilias
Dan Asimov
of R^2. This creates a set S that consists of just those points for
which the coin came up heads.
I strongly suspect that if the theory of probability were adequately
extended to the space {0,1}^(R^2), then with probability one the
subset S would not be expressable as a countable Boolean word in
rectangular subsets.
Dan Asimov
David C. Ullrich
Kastanas) wrote:
>In article <3cd52d91...@nntp.sprynet.com>,
>David C. Ullrich <ull...@math.okstate.edu> wrote:
> >On 4 May 2002 18:52:29 GMT, ika...@alumnus.caltech.edu (Ilias
> >Kastanas) wrote:
> >
> >[...]
> >>
> >>Well, that might be true; but one thing is certain: it is not provable
> >>in ZFC... because CH implies the answer is "yes". Under CH, R x R is
> >>the union of countably many function graphs (heh... a likely story!),
> >
> >Seems extremely unlikely, unless I'm misinterpreting what you mean by
> >"function graph": If R x R is the union of the graphs of the functions
> >f_1, ... then every (0, y) is equal to (0, f_n(0)) for some n and
> >hence R is countable (making this more suitable for sci.math than
> >here.)
>
>
> Who's being snippy now?! Poor sci.math... David, when you get
>banned, don't say I didn't warn you.
Ok.
> Yes, I do mean "function graph"... without, uh, banning the second
>R from being the domain; i.e. {(x, f_n(x)}'s as well as {(g_n(y), y)}'s.
Ah. I figured you weren't babbling nonsense, so I considered the
possibility that you were talking about rotated graphs. But the next
paragraph didn't sound like you were talking about rotated graphs -
didn't consider the possibility that you were rotating by pi/2.
> >>and a
> >>function graph can be dealt with pretty much like above; its complement is
> >>the union of sets A_q x {q} "below", q rational, A_q = {x : f(x) < q}, and
> >>similar sets "above".
> >
> >This part sounds like by "function graph" you mean literally "graph of
> >a function"... huh???
>
>
> No mystery to it... let h_x(n) enumerate {x} U {predecessors of x in
>the w_1 wellordering} (with repetitions if need be), and set f_n(x) = h_x(n);
>then tilt your head by pi/2 and set g_m(y) = h_y(m).
Sure enough, thanks. Conjecturing that you were claiming R was
countable was more fun, though.
David C. Ullrich
Greg Kuperberg
Actually, that is a perfectly well-defined measure space and it
is entirely rigorous to ask whether A = P(R) tensor_sigma P(R) is a
measurable subset of P(R x R), and if so, whether it is a null set. But,
as others have explained, the answer likely depends on which model of set
theory you use. Assuming the Continuum Hypothesis, A
is all of P(R x R), and therefore is measureable and has full measure.
I imagine that there are models in which A is a
null set, but it is conceivably a non-measurable set in some models.
Clearly if it is measurable, then it is either a null set or full-measure
set: A is a vector subspace of P(R x R) with respect to the Z/2 vector
space structure, and if it is not all of P(R x R) it has infinite
codimension. In the second case P(R x R) is comprised of infinitely
many cosets of A, all of which have the same measure.
It also occured to me that the role of Continuum Hypothesis is really
relatively simple and does not require set theory at the level of
Cohen's work. Let Omega be the first uncountable ordinal. Then, fact:
P(Omega x Omega) = P(Omega) tensor_sigma P(Omega) (*)
The reasoning follows other postings in this thread.
Exercise 1: If X is a set with |X| <= |R|, then the graph of any function
f from X to X lies in P(X) tensor_sigma P(X). (The idea for the function
f(x) = x works in the general case.) It follows that any subset of the
graph of f lies in P(X) tensor_sigma P(X).
Exercise 2: If X is a set with |X| <= |R|, then a countable union Y of
graphs of functions from X to X also lies in P(X) tensor_sigma P(X),
as does any subset. (Use Exercise 1.) Such a set Y can be described
as a subset of X x X whose vertical fibers are all countable.
Exercise 3: Omega x Omega can be decomposed into the diagonal, a set
Y as in Exercise 2, and the diagonal flip of Y. (Set Y to be the set
of all pairs (a,b) with b<a in the ordering on Omega. Omega has the
property that any subset with an upper bound is countable.)
The result (*) follows from observing that |Omega| <= |R| in ZFC, by
Cantor's argument that |R| > |N|.
Given this fact about the first uncountable ordinal Omega, the only role
of the Continuum Hypothesis is to assert that |R| = |Omega|.
Interestingly, if you modify Omega slightly you can show that Omega x
Omega can be *partitioned* into countably many graphs of functions and
sideways graphs of functions. Namely let Omega' be Omega preceded by -N,
the negative integers, and follow the hint in Exercise 3.