What is the smallest cardinality of a Kuratowski 14-set?
A subset $A$ of a topological space $X$ is called a Kuratowski 14-set if exactly 14 different sets (including $A$) can be obtained from $A$ by alternately taking closures and complements.
Are there any examples of 14-sets having finite cardinality? In a finite space, so far the best I can produce is 10 sets from a 3-element subset.
What is the smallest possible cardinality of a 14-set?
Solution 1:
This is Problem 1898 in the latest (June) issue of Mathematics Magazine:
"A subset E of a topological space X is called a 'Kuratowski 14-set' if 14 distinct sets can be obtained by repeatedly applying closure and complement to E in some order. It is known that Kuratowski 14-sets E with |E| = 3 exist. Do any exist with |E| < 3?"
Solutions can be emailed to [email protected]. The acceptance deadline is November 1st for possible publication in the journal.
Given this problem's status as an open journal problem, I feel constrained in saying much at all about its solution. I am the one who proposed it, so I do have a proof.
As a minor, indirect hint, I will at least say that Herda and Metzler's paper (referred to in Gerry Myerson's answer) is one of the very best places to look for ideas.
------------- post-deadline, complete answer added 6 Nov 2012 -------------
Here is my proof:
The answer is no. Let $cE$ denote the complement of $E$, $iE$ the interior of $E$, and $kE$ the closure of $E.$ Let $K(E)$ denote the family of sets generated by $E$ under $k$ and $c.$ Since $i = ckc$ and $k = cic$, $K(E)$ equals the family generated by $E$ under $i$ and $c.$ It is well known that $$K(E)=\{E,iE,ciE,iciE,ciciE,iciciE,ciciciE,cE,icE,cicE,icicE,cicicE,icicicE,cicicicE\},$$ where some of the sets in the list may be equal to one another.
Assume $E=\{a,b\}\subset X$ with $a\neq b.$ Claim |$K(E)$| $\leq12.$ This is obvious when $iE=E$ or $iE=\emptyset$, so we may assume without loss of generality that $iE=\{a\}.$ Note that $a\in icicE$, since $iE\subset ikE=icicE.$
Suppose $b\in icicE.$ Then $E\subset icicE.$ Applying $ic$ to both sides produces $icicicE\subset icE.$ The reverse containment always holds, so $icicicE=icE.$ Since |$K(E)$| is always even, the claim follows.
Suppose $b\not\in icicE.$ Assume there exists a point $x$ such that $x\in icicE\cap iciE.$ Since $x\in icicE$, there exists an open set $U$ such that $x\in U\subset cicE.$ Since $x\in iciE$, there exists an open set $V$ such that $x\in V\subset ciE\ (=X\setminus\{a\}).$ Since $b\not\in icicE$ it follows that $b\not\in U.$ Thus $x\in U\cap V\subset cE$, which contradicts $x\in cicE.$ This contradiction implies $icicE\subset ciciE.$ Applying $i$ to both sides produces $icicE\subset iciciE.$ The reverse containment always holds, so $iciciE=icicE.$ This proves the claim.
The claim obviously implies no singleton can generate 14 sets under closure and complement (since "cloning" its element would produce a 14-set of cardinality 2). The empty seed set generates only two sets. Therefore no Kuratowski 14-sets exist with cardinality less than 3.
It turns out that 12 sets are possible when starting with a 2-point seed set. This can be done in a 6-point space, with the number 6 being minimal by results in Anusiak and Shum, Remarks on finite topological spaces, Colloq. Math. 23 (1971), 217–223, MR0326635 (48 #4978).
Lately I have been working on a free reference website aimed at indexing anything-and-everything Kuratowski 14. Though the site is still in a very unfinished state, I feel I have enough to do the launch less than two weeks from now. (I will mention the URL here immediately upon launch.)
The page's main attractions at launch are going to be (a) a useful C program that generates set families under various operations in various spaces, (b) several English translations of major papers (including Kuratowski's 1922 groundbreaker, originally in French), and (c) references to some "new" old papers I came across during some deep Google- and Bing-searching.
As before, I shall conclude with a hint to a question. This time the question is "What is the title of my page going to be?" Here's the hint: a big motivator for its imminent launch is its alliterative, [North American] holiday-themed title. (If you come up with any guess at all, it's almost certainly correct...)
Talk again soon!
------------- post-launch, new website link added 14 Nov 2012 -------------
The title of my page is Kuratowski's Closure-Complement Cornucopia. Here is the link:
http://www.mathtransit.com/cornucopia.php
Solution 2:
Herda and Metzler, Closure and interior in finite topological spaces, Colloq. Math. 15 (1966) 211–216, MR0202101 (34 #1975) prove that you can do it with 7 points, and not with any fewer. The result can also be found in Berman and Jordan, The Kuratowski closure-complement problem, Amer. Math. Monthly 82 (1975), no. 8, 841–842, MR0388305 (52 #9142).
EDIT: The 7 refers to the number of elements of $X$; examples are given where the set $A$, the actual 14-set, has only 3 elements.
Solution 3:
As I point out in a comment, these questions came to mind while I was doing a related exercise in Munkres' "Topology". I am pleased to see that it is a problem in the Magazine!
I will give here a partial answer that does not affect the problem in the magazine.
Statement: For any given $n\ge 3$ there is a finite topological space containing a 14-set of cardinality $n$.
Proof: For $n\ge 4$, let $m=n+3$, the point set $X=\{1,2,3,\ldots, m\}$, and $\mathcal{B}=\{\emptyset, X, \{1\}, \{6\}, \{1,2\}, \{3,4\}, \{5,6\}\}$ as the basis for the topology on $X$. Then the subset $A=\{1,3,5\}$ is a 14-set of cardinality 3. Therefore, $A'$ (the complement of $A$ in $X$) is a 14-set of cardinality $m-3=n$, as desired.
For $n=3$, let $m=7$ in the previous setting and $A$ is the desired 14-set.
Moreover, we can obtain 14-sets of any desired infinite cardinality as follows: Let $Y$ be a set of cardinality $k\ge \aleph_{0}$, and let $X=\{1,2,3,4,5,6,7\}\cup Y$ with basis for the topology $\mathcal{B}$ as before. Then the set $A$ is a 3-element 14-set in $X$, and $A'$ is a 14-set of cardinality $k$. For example, if $Y=\mathbb{N}$ then $A'$ is a countably infinite 14-set.
Answer added Nov. 18:
The smallest possible cardinality of a Kuratowski 14-set $E$ is $3$. Let $k$, and $i$ denote closure and interior, respectively. Then $E$ is a Kuratowski 14-set iff $E$, $E^{i}$, $E^{iki}$, $E^{ki}$, $E^{ik}$, $E^{kik}$, and $E^{k}$ are all non-empty, distinct sets strictly contained in $X$. If $E$ is empty the answer is trivial. If $|E|=1$ then $E^{i}$ equals either $E$ or is empty. If $E=\{a,b\}$ then we may assume that $E^{i}=\{a\}$. But then $a\notin B=E^{ki}-E^{ik}$, which is an open set contained in $E^{k}$ and so it must intersect $E$ non-trivially. Hence, $b\in B$ from which we obtain $E^{kik}=E^{k}$.
Remark: Since a Kuratowski 14-set $E$ of cardinality 2 or less does not exist, we may ask what is the maximum number of different sets obtainable from $E$ by taking closures and complements.
If $|E|=1$ we have two possibilities:
First, if $E^{i}=E$ then $E^{ik}=E^{kik}=E^{k}$ and $E^{iki}=E^{ki}$. Therefore, at most 6 distinct sets can be obtained from $E$ by taking closures and complements. This bound is possible if $|X|\ge 3$. For example, $X=\{1,2,3\}$ with basis $\{\{3\},X\}$ and $E=\{1\}$.
Second, if $E^{i}=\emptyset$ then $E^{ik}=E^{iki}=\emptyset$ and $E^{kik}=E^{k}$. Therefore, at most $8$ distinct sets can be obtained from $E$ by taking closures and complements. This bound is possible if $|X|\ge 4$. For example, $X=\{1,2,3,4\}$ with basis $\{\{4\},\{1,2\},X\}$ and $E=\{1\}$.
If $E=\{a,b\}$ we may assume that $E^{i}=\{a\}$. But then $a\notin B=E^{ki}-E^{ik}$, which is an open set contained in $E^{k}$ and so it must intersect $E$ non-trivially. Hence, $b\in B$ from which we obtain $E^{kik}=E^{k}$. Therefore, at most 12 distinct sets can be obtained from $E$ by taking closures and complements. This bound is possible if $|X|\ge 6$. For example $X=\{1,2,3,4,5,6\}$ with basis $\{\{1\},\{6\},\{1,2\},\{4,5\},X\}$ and $E=\{1,4\}$.
Solution 4:
I guess there is/was some demand for this answer to be undeleted. Oh well, here it is un-spoilered.
There are no Kuratowski 14-sets of size 2.
Suppose that $A = \{ a , b \}$ is a Kuratowski 14-set in some topological space $X$. Note that, in particular, the following seven sets are distinct:
- $A$;
- $\overline{ A }$;
- $\mathop{Int} ( A )$;
- $\mathop{Int} ( \overline{ A } )$;
- $\overline{ \mathop{Int} ( A ) }$;
- $\overline{ \mathop{Int} ( \overline{ A } ) }$; and
- $\mathop{Int} ( \overline{ \mathop{Int} ( A ) } )$.
(This comes from the fact that $\mathop{Int} ( B ) = X \setminus \overline{ X \setminus B }$ for all $B \subseteq X$. In fact, these seven sets being distinct is equivalent to $A$ being a Kuratowski 14-set -- as the other seven are just the complements of these -- but that is of little importance for the moment.)
Note that as $\mathop{Int} ( A ) \subsetneqq A$, it follows that $\mathop{Int} ( A )$ is one of $\emptyset$, $\{ a \}$, or $\{ b \}$. Since $\overline{ \mathop{Int} ( A ) } \neq \mathop{Int} ( A )$, it follows that $\mathop{Int} ( A )$ must be nonempty, and therefore without loss of generality we may assume that $\mathop{Int} ( A ) = \{ a \}$.
Claim: $A \subseteq \mathop{Int} ( \overline{ A } )$.
Proof of claim: First note that, clearly, $\{ a \} = \mathop{Int} ( A ) \subseteq \mathop{Int} ( \overline{ A } )$.
Next note that $\mathop{Int} ( \overline{ \mathop{Int} ( A ) } ) \subsetneqq \mathop{Int} ( \overline{ A } )$. From this it follows that $U = \mathop{Int} ( \overline{ A } ) \setminus \overline{ \mathop{Int} ( A ) }$ is a nonempty open set. (Clearly $U$ is open. If $U = \emptyset$, then $\mathop{Int} ( \overline{ A } ) \subseteq \overline{ \mathop{Int} ( A ) }$, and so $\mathop{Int} ( \overline{ A } ) \subseteq \mathop{Int} ( \overline{ \mathop{Int} ( A ) } )$, contradicting the fact above.) Trivially, $U \subseteq \overline{ A } = \overline{ \{ a , b \} } = \overline{ \{ a \} } \cup \overline{ \{ b \} }$, but is disjoint from $\overline{ \mathop{Int} ( A ) } = \overline{ \{ a \} }$, and so it must be that $U \subseteq \overline{ \{ b \} }$. So then $b \in U \subseteq \mathop{Int} ( \overline{ A } )$ $\dashv$
Note that we now have that $$\overline{ A } \subseteq \overline{ \mathop{Int} ( \overline{ A } ) } \subseteq \overline{ ( \overline{A} ) } = \overline{A},$$ contradicting our assumption that $A$ is a Kuratowski 14-set!