Monday, 9 April 2012

gn.general topology - The Closure-Complement-Intersection Problem

Background



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.

No comments:

Post a Comment