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.