From: Mark Bowron
Subject: new Kuratowski closure-complement (and union) results?
Date: Fri, 31 Dec 1999 06:24:02 GMT
Newsgroups: sci.math.research
Keywords: sets generated from one set using closure, complement, and union.
This message is divided into five parts:
1) The known result.
2) The scaffolding.
3) A couple new results (maybe).
4) A brief remark.
5) Bibliography.
All except the devoutly curious will probably wish to skip part 2).
1) The known result.
====================
A couple days ago I discovered David McIntyre's sci.math.research post
of Sep. 1998 (and replies from Julian Dontchev and Fred Galvin)
regarding the number of sets that can be generated from one set in a
topological space under the operations of closure, complement, and
union. Galvin closed the thread with a demonstration--in the reals
under the usual topology--that the number is indeed infinite. He
credited Edwin Buchman circa 1983, without citing any published
reference.
Stanley Rabinowitz and I published this result as a Monthly problem
sometime in either late '96 or early '97 (I think it may have been
proposed in the Dec. '96 issue; regrettably I have misplaced my copy and
do not remember the problem number). To my knowledge, the result had
never been published before that. Certainly it must have been known for
a long time though, perhaps even before 1983. In 1995 I did an
exhaustive literature search--including topology textbooks--and found no
mention of the problem. The fruit of that search, a fairly
comprehensive bibliography through 1995, appears at the end of this
message.
Our proof was simpler than the one the Monthly chose to publish. It
goes like this: Let the space be the natural numbers with the topology
consisting of all sets of the form {1, 2,..., n} plus the empty set and
the whole space. Let S = {1, 3, 5, 7,...}. The interior of S is {1}.
Union this with the complement of S to get {1, 2, 4, 6,...}. The
interior of this set is {1, 2}. Union this with S to get {1, 2, 3, 5,
7,...}. The interior of this set is {1, 2, 3}. And so on.
It is worth noting that the above proof easily generalizes to the space
of any ordinal number (thought of as the set of its predecessors) under
the topology consisting of all initial segments, so that not only is
there no finite bound to the number of sets that can be generated, no
transfinite bound exists either.
2) The scaffolding.
===================
I worked on this problem for a long time before finally solving it with
Rabinowitz's help in 1996. One of the main reasons it took me so long
is that my intuition was wrong; I thought the number was finite, based
on the Kuratowski 14-set result. My initial approach to the problem
consisted in designing ever more elaborate sets of reals under the usual
topology, to fill in the theoretical possibilities for new sets that one
can obtain by systematically writing down ever more complex compositions
of the three operations applied to a single set. I went back and forth
between finding expressions that could potentially yield new sets (i.e.,
expressions that did not reduce to any previous ones using known
identities), and tacking new constructions onto the seed set to try and
actually produce those new sets. This was kind of fun, but it began to
appear like an endless exercise, so I gave up for several years.
When I revisited the problem in 1995, it occurred to me that this
problem is best attacked with the aid of a computer. All my previous
work had been done by hand. I realized that the final, most elaborate
seed set I had constructed during my previous work could easily be coded
as a finite binary sequence, as well as all the sets generated under the
three operations. Applying this technique, my computer told me that if
the maximal number was finite, it was certainly very large--well over
10,000.
In the MathPro Press office one Saturday afternoon in early 1996,
Stanley Rabinowitz, Peter Gilbert, and I used a C program Rabinowitz had
written the night before to test out various topologies and seed sets on
finite spaces to see how many sets could be generated. Rabinowitz
seemed to have a knack for picking just the right topology and right
seed set to generate the power set of the space under the three
operations; he was able to do this for every cardinality of the
underlying space we tried. (We went up to about 10.) This convinced
all three of us that the answer must be infinite.
The next day while reviewing the results of our experiments, I noticed a
pattern that immediately led me to discover the embarrassingly simple
proof given above.
3) A couple new results (maybe).
================================
During my initial trial and error approach in the reals under the usual
topology, I discovered two curious properties of the family of sets
generated by the three operations. It's doubtful that anyone has ever
noticed these properties before, because no one in their right mind
would ever bother going down the path one seemingly needs to go down, to
get to these results. (But I did.)
Let X be a topological space. For any family F of subsets of X and any
family S of set operations (unary, binary, whatever) defined on the
power set of X, let F(S) denote the smallest family containing F that is
closed under S. For brevity, let (F(S))(T) be written F(S)(T).
Let A be a subset of X and let F = {A}, the family containing the single
set A. Then the following hold:
(a) F(S)(T)(U) - F(S) contains no complementary pairs, where S =
{closure, complement}, T = {union}, and U = {closure}.
(b) F(S)(T)(U)(V)(W) = F(S)(T)(U)(V), where S = {closure, complement}, T
= {union}, U = {closure}, V = {complement}, and W = {closure}.
In other words, if you take all possible unions among Kuratowski's 14
sets (or perhaps fewer than 14 if A isn't elaborate enough to begin
with--regardless, the family generated is obviously finite and contains
at most 2^14 sets), then add in the closures of all those sets, then
throw out Kuratowski's original 14 (or fewer), no complementary pairs
remain. If you don't throw out Kuratowski's sets and instead further
enlarge the generated family by taking complements, the resulting family
is closed under closure.
I briefly attempted to prove these results without success. Or I should
say, I tried to find a proof that might be worth reading. I think
through the course of my laborious search for a maximal finite family I
actually did prove both these results by exhaustion, but it would
probably take a 19th Century-style 100-page effort to catalogue the
proof.
4) A brief remark.
==================
After I did the literature search, I became vaguely interested in the
general notion of starting with a seed set in a space and applying
operations to it to grow ever larger families, or perhaps arrive at a
maximal family. There are problems in recreational mathematics where
one starts with a set of numbers and applies arithmetic operations to
those numbers, to obtain larger sets of numbers or perhaps arrive at a
maximal set of numbers. Such problems remind me of the Kuratowski
problem.
The paper by Peleg [21] hints at the possibility of interesting further
research in this area.
5) Bibliography.
================
1. J. Anusiak and K. P. Shum, Remarks on finite topological spaces,
{\it Colloq. Math.}, {\bf 23} (1971) 217-223.
2. C. E. Aull, Classification of topological spaces, {\it Bull. de
l'Acad. Pol. Sci. Math. Astron. Phys.}, {\bf 15} (1967), 773-778.
3. S. Baron, Advanced problem 5569, {\it Amer. Math. Monthly}, {\bf
75} (1968) 199.
4. J. Berman and S. L. Jordan, The Kuratowski closure-complement
problem, {\it ibid.}, {\bf 82} (1975) 841-842.
5. E. Buchman, Problem E 3144, {\it ibid.}, {\bf 93} (1986) 299.
6. A. V. Chagrov, Kuratowski numbers, Application of Functional
Analysis in Approximation Theory, 186-190, Kalinin Gos. Univ., Kalinin,
1982.
7. T. A. Chapman, A further note on closure and interior operators,
{\it Amer. Math. Monthly}, {\bf 69} (1962) 524-529.
8. J. H. Fife, The Kuratowski closure-complement problem, {\it Math.
Mag.}, {\bf 64} (1991) 180-182.
9. P. C. Fishburn, Operations on binary relations, {\it Discrete
Math.}, {\bf 21} (1978) 7-22.
10. R. L. Graham et al., Complements and transitive closures, {\it
ibid.}, {\bf 2} (1972) 17-29.
11. P. C. Hammer, Kuratowski's closure theorem, {\it Nieuw Arch. Wisk.}
(3), {\bf 8} (1960) 74-80.
12. H. H. Herda and R. C. Metzler, Closure and interior in finite
topological spaces, {\it Colloq. Math.}, {\bf 15} (1966) 211-216.
13. J. L. Kelley, General Topology, Van Nostrand, Princeton, NJ, 1955.
14. W. Koenen, The Kuratowski closure problem in the topology of
convexity, {\it Amer. Math. Monthly}, {\bf 73} (1966) 704-708.
15. C. Kuratowski, Sur l'operation A de l'analysis situs, {\it Fund.
Math.}, {\bf 3} (1922) 182-199.
16. E. Langford, Characterization of Kuratowski 14-sets, {\it Amer.
Math. Monthly}, {\bf 78} (1971) 362-367.
17. ---------------, Problem 6260, {\it ibid.}, {\bf 86} (1979) 226.
18. N. Levine, On the commutativity of the closure and interior
operators in topological spaces, {\it ibid.}, {\bf 68} (1961) 474-477.
19. L. E. Moser, Closure, interior, and union in finite topological
spaces, {\it Colloq. Math.}, {\bf 38} (1977) 41-51.
20. J. R. Munkres, Topology: A First Course, Prentice-Hall, Englewood
Cliffs, NJ, 1975.
21. D. Peleg, A generalized closure and complement phenomenon, {\it
Discrete Math.}, {\bf 50} (1984) 285-293.
22. K. P. Shum, On the boundary of Kuratowski 14-sets in connected
spaces, {\it Glas. Mat. Ser. III}, {\bf 19(39)} (1984) 293-296.
23. -----------------, The amalgamation of closure and boundary
functions on semigroups and partially ordered sets, Proceedings of the
Conference on Ordered Structures and Algebra of Computer Languages,
232-243, World Scientific, Singapore, 1993.
24. A. Smith, Advanced problem 5996, {\it Amer. Math. Monthly}, {\bf
81} (1974) 1034.
25. V. P. Soltan, On Kuratowski's problem, {\it Bull. Acad. Polon. Sci.
Ser. Sci. Math.}, {\bf 28(7-8)} (1981) 369-375.
26. -----------------, Problems of Kuratowski type, {\it Mat. Issled.},
{\bf 65} (1982) 121-131, 155.
Sent via Deja.com http://www.deja.com/
Before you buy.