24
$\begingroup$

Background

$\DeclareMathOperator\Cl{Cl}$ Let $A$ be a subset of a topological space $X$. An old problem asks, by applying various combinations of closure and complement operations, how many distinct subsets of $X$ can you describe?

The answer is 14, which follows from the observations that $\Cl(\Cl(A))=\Cl(A)$, $\neg(\neg (A)=A$ and the slightly harder fact that $$ \Cl(\neg (\Cl(\neg (\Cl(\neg (\Cl(A))))=\Cl(\neg (\Cl(A))$$ where $\Cl(A)$ is the closure of $A$ and $\neg (A)$ is the complement. This makes every expression in $\Cl$ and $\neg$ equivalent to one of 14 possible expressions, and all that remains is to produce a specific choice of $A$ which makes all 14 possiblities distinct. This problem goes by the name Kuratowski's closure-complement problem, since it was first stated and solved by Kuratowski in 1922.

The problem

A very similar problem recently came up in a discussion that was based on a topological model for modal logic (though the logical connection is unrelated to the basic question). The idea was to take a subset $A$ of $\mathbb{R}$, and to consider all possible expressions on $A$ consisting of closure, complement, and intersection. To be clear, we are allowed to take the complement or closure of any subset we have already constructed, and we are allowed to intersect any two subsets we have already constructed.

The question: Is this collection of subsets always finite?

A potentially harder question: If there are multiple starting subsets $A_1$, $A_2$, $A_3$... (finite in number), is this collection of subsets always finite?

The first question is essentially the Kuratowski question, with the added operation of intersection. There is also the closely related (but slightly stronger) question of whether there are a finite number of formally distinct expressions on an indeterminant subset $A$ (or a collection of subsets $A_1$, $A_2$...).

Some thoughts

My guess to both questions is yes, but the trick is showing it. I can take an example of a set $A$ which realizes all 14 possibilities from Kuratowski's problem, and show that the collection of distinct subsets I can construct from it is finite. However, just because such a set captures all the interesting phenomena which can happen when closing and complementing, doesn't mean this example is missing a property that is only important when intersecting.

It also seems difficult to approach this problem formally. The problem is that there are many non-trivial intersections of the 14 expressions coming from Kuratowski's theorem. Then, each of these intersections could potentially have its own new set of 14 possible expressions using closures and complements. In examples, the intersections don't contribute the full number of 14 new sets, but its hard to show this aside from case-by-case analysis.

$\endgroup$
4
  • $\begingroup$ Greg, I misread your question and had posted an irrelevant answer, which is now deleted. Sorry! $\endgroup$ Apr 1, 2010 at 2:01
  • $\begingroup$ Quite alright. As you indirectly pointed out, the restriction of this problem to any two of the three operators is a very easy problem. However, showing that the addition of the third 'doesn't add too much' seems harder. $\endgroup$ Apr 1, 2010 at 2:05
  • $\begingroup$ (Greg, now that I think about it I think Mike O'Connor had a sharper proof of this.) $\endgroup$ Apr 1, 2010 at 4:32
  • $\begingroup$ @GregMuller There is a good site (mathtransit.com/cornucopia.php) devoted to the Kuratowski Closure-Complement Theorem. $\endgroup$ Aug 1, 2017 at 9:09

3 Answers 3

13
$\begingroup$

From one set, you can generate infinitely many sets.

Let A be a closed set of infinite Cantor-Bendixon rank. That is, the successive finite Cantor-Bendixon derivatives A', A'', and so on are all distinct. The rank of an element x in A is the least n such that x becomes isolated in An, where A0 = A and An+1 = A', the set of limit points of An. Thus, the rank 0 elements are the isolated points of A, and the rank 1 elements are the limits of these points which are not limits of limit points of A, and so on.

Now, let B be the subset of A consisting of the elements of A having even rank. This includes all isolated points of A, but not their limits that are not limits of limits, but does include the limits of limits (as long as they are not limits-of-limits-of-limits) and so on. Define the operation B+ = cl(B) - B, which is obtainable from your operations. Note that cl(B) = A, and that B+ consists of all elements of A having odd rank in A. Similarly, B++ = cl(B+) - B+ consists of all elements having odd rank in cl(B+) = A', which is exactly those elements of A having even rank at least 2 in A. And so on. The set B+n will consist of all elements of A having rank at least n+1, which have even/odd rank depending on the parity of n. Since A has infinite rank, these sets will all be distinct.

Thus, the set B generates infinitely many distinct sets B, B+, B++, B+++, etc.

$\endgroup$
8
  • 1
    $\begingroup$ But what about the closure operator? This is the only operator where I am using the topology of the reals. If I take the Boolean algebra generated by the initial sets, then each of these might have a a closure which has an interesting intersection with any of the previously created sets. A good example is R^+ inside R. Its intersection with its complements closure is the origin, and producing this set requires each of the three operators in a necessary way. $\endgroup$ Apr 1, 2010 at 1:51
  • $\begingroup$ Greg, I have a new argument which now actually answers your question. But now I see that François has also posted an answer---I wonder if this is the same as Tarski's argument? $\endgroup$ Apr 1, 2010 at 3:56
  • $\begingroup$ More or less, McKinsey and Tarski used $x \cap cl(cl(x) - x)$ and worked over the ordinal $\omega^\omega$, which is basically the same idea you had. $\endgroup$ Apr 1, 2010 at 4:06
  • $\begingroup$ (But they attribute the argument to Kuratowski!) $\endgroup$ Apr 1, 2010 at 4:10
  • 1
    $\begingroup$ Greg, it was a great question! $\endgroup$ Apr 1, 2010 at 4:14
8
$\begingroup$

Unfortunately, the free closure algebra with even one generator is infinite! This was shown by McKinsey and Tarski in their classic paper The Algebra of Topology (Annals of Mathematics 45, 1944, MR0009842).

$\endgroup$
1
  • $\begingroup$ +1. Once again, we post nearly at the same time! $\endgroup$ Apr 1, 2010 at 4:10
8
$\begingroup$

As François mentioned, in 1922 Kuratowski gave the first published example of a space and seed set $x_0$ such that the sequence $\lbrace x_i\rbrace$ is infinite, where $x_{i+1}=x_i\cap cl(cl(x_i)-x_i)$.

The following equations give a more detailed picture of why the sequence is infinite:

space = $\lbrace1,2,3,\ldots\rbrace$
topology = $\lbrace {\rm space}, \lbrace \rbrace ,\lbrace 1\rbrace ,\lbrace 1,2\rbrace ,\lbrace 1,2,3\rbrace ,\ldots\rbrace $
$x_0=\lbrace 2,4,6,\ldots\rbrace $
$cl(x_0)=\lbrace 2,3,4,\ldots\rbrace $
$y=cl(x_0)-x_0=\lbrace 3,5,7,\ldots\rbrace $
$cl(y)=\lbrace 3,4,5,\ldots\rbrace $
$x_0\cap cl(y)=\lbrace 4,6,8,\ldots\rbrace $
$\ldots$

$\endgroup$
3
  • 1
    $\begingroup$ Also worthy of note, on p. 34 in their paper "The Kuratowski Closure-Complement Theorem", New Zealand J. Math., 38 (2008) 9-44, MR2491682, nzjm.math.auckland.ac.nz/images/6/63/… Gardner and Jackson make the interesting observation that the combined power of all three operations need not be called upon to obtain an infinite family. It turns out that by merely applying the two operations closure and set difference to a single seed set, infinitely many distinct sets are obtainable. $\endgroup$ Dec 2, 2012 at 22:33
  • $\begingroup$ @Greg Muller But for any chain $\tau_1\subset\cdots\subset\tau_n$ of pairwise comparable topologies on a set $X$ the number of sets that can be obtained from a given set $A\subset X$ by consequtive application of the operations of complement and closure in a topology $\tau_i$ is finite! See, arxiv.org/abs/1508.07703 $\endgroup$ Aug 1, 2017 at 9:02
  • $\begingroup$ A couple years ago I posted a history of the closure-complement-intersection problem here: math.stackexchange.com/a/2317968/32209 $\endgroup$ Jun 22, 2019 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.