A question on the proof of 14 distinct sets can be formed by complementation and closure

In Munkres, problem 20 of Section 2-6, it says that 14 distinct sets can be formed by complementation and closure. I see only five so far. Let f be the function of closure mapping and g be the function of complementation mapping. It is clear, f,g, fg,gf, and gfg are the 5 of 15 distinct sets. What are the rests? Was there any topological argument associated with it? How can I understand this intuitively and pictorially?

• Why did you not include $fgf$ in your list? Jul 24, 2014 at 2:03
• I think the question should be reopened. (If the questions are duplicates, they should be closed in the opposite direction.) See also the discussion in chat. Jan 26, 2016 at 15:03

This is known as Kuratowski's closure-complement problem:

"Kuratowski's closure-complement problem asks for the largest number of distinct sets obtainable by repeatedly applying the set operations of closure and complement to a given starting subset of a topological space."

Let $$f$$ denote the closure operation (Wikipedia uses $$k$$) and let $$g$$ denote the complement operation (Wikipedia uses $$c$$). Let $$W$$ be the set of strings (finite ordered lists) using only $$f$$ and $$g$$. For a fixed subset $$S$$ of a topological space $$X$$, and $$w \in W$$, let $$wS$$ denote the set obtained by applying the operations listed in $$w$$, from right to left. For example, if $$w = fgg$$, then $$wS$$ is the set obtained by first taking the complement of $$S$$, then taking the complement of that, and then taking the closure of that.

For a fixed subset $$S$$ of a topological space $$X$$, let $$m(S) = |\{wS \mid w \in W\}|$$. It is not even clear that $$m(S)$$ is finite, but we can simplify matters somewhat by reducing the number of strings we need to consider. In the example above, we took the complement of $$S$$, then took the complement of that; but that's just $$S$$! In general, we see that $$gg$$ has no effect on the set. Therefore, if $$w \in W$$ contains a pair $$gg$$, we can remove it from the string without changing the set $$wS$$. We have a similar simplification for $$f$$, namely $$ff = f$$ (why?). With these two pieces of information at our disposal, we see that we only need to consider strings where there are no consecutive $$f$$'s or $$g$$'s; from this point on, $$W$$ will denote the set of such strings. While these restrictions are substantial, we are still left with infinitely many strings to consider:

$$(\text{empty string}),\ \ f,\ \ g,\ \ fg,\ \ gf,\ \ fgf,\ \ gfg,\ \ fgfg,\ \ gfgf,\ \ fgfgf,\ \ gfgfg,\ \ fgfgfg,\ \ gfgfgf,\ \ fgfgfgf,\ \ gfgfgfg, \dots$$

The key to moving forward is to prove the following:

$$fgfgfgfgS = fgfgS.$$

Just like the rules about $$gg$$ and $$ff$$, we can use the above to consider a smaller set of strings. In particular, whenever a string $$w$$ contains $$fgfgfgfg$$ we can replace that part by $$fgfg$$ without changing the set $$wS$$. Now note that if a string $$w$$ has length nine, it must contain $$fgfgfgfg$$, so there is a string $$w'$$ of length five such that $$wS = w'S$$ (note that $$w'$$ is the string obtained from $$w$$ by replacing $$fgfgfgfg$$ with $$fgfg$$). Likewise, if $$w$$ is a string of length $$n \geq 9$$, there is a string $$w'$$ of length $$n - 4$$ such that $$wS = w'S$$. If $$w'$$ has length greater than or equal to nine, we can apply the same reasoning to obtain a shorter string $$w''$$ such that $$w'S = w''S$$. After a finite number of steps, we obtain a string $$w_0$$ with length at most eight such that $$wS = w_0S$$. Therefore,

$$\{wS \mid w \in W\} = \{wS \mid w \in W\ \text{has length at most eight}\}.$$

But one of the strings of length eight is precisely $$fgfgfgfg$$ which can be replaced with the length four string $$fgfg$$. As for the other string of length eight, I'll leave it as an exercise as to why $$gfgfgfgf$$ can be replaced with $$gfgf$$. As $$fgfgfgfgS = fgfgS$$ and $$gfgfgfgfS = gfgfS$$, we obtain the slightly stronger result

$$\{wS \mid w \in W\} = \{wS \mid w \in W\ \text{has length at most seven}\}.$$

Note, we could still have two strings $$w, w'$$ of length at most seven, with $$wS = w'S$$, so

\begin{align*} m(S) &= |\{wS \mid w \in W\}|\\ &= |\{wS \mid w \in W\ \text{has length at most seven}\}|\\ &\leq\ \text{number of strings of length at most seven}. \end{align*}

How many strings are there of length at most seven? Fifteen, as can be seen in the list above. Using the same trick which allows us to replace the string $$gfgfgfgf$$ by $$gfgf$$, we can replace the length seven string $$fgfgfgf$$ by the string $$fgf$$ (alternatively, you can use the method Arthur Fischer uses in his comment below). So, for any topological space $$X$$, and any subspace $$S$$, $$m(S) \leq 14$$ (we don't need to consider the string $$fgfgfgf$$).

Note, the value of $$m(S)$$ does change depending on $$S$$; for example, for $$S = X \neq \emptyset$$, $$m(S) = 2$$, while for $$S = \{0\}$$ and $$X = \mathbb{R}$$, $$m(S) = 4$$. So how good is the upper bound of $$14$$? It may be the case that $$m(S)$$ is actually less than fourteen for every possible choice of $$S$$. It turns out that this is not the case, so the upper bound is optimal. That is, there is a subset $$S$$ of a topological space $$X$$ such that $$m(S) = 14$$. An example is $$X = \mathbb{R}$$ and $$S = (0, 1)\cup(1,2)\cup\{3\}\cup([4, 5]\cap\mathbb{Q})$$. Therefore, the answer to Kuratowski's closure-complement problem is fourteen.

Let's list the fourteen different sets obtained from $$S = (0, 1)\cup(1,2)\cup\{3\}\cup([4, 5]\cap\mathbb{Q})$$:

1. $$S = (0, 1)\cup(1,2)\cup\{3\}\cup([4, 5]\cap\mathbb{Q})$$,
2. $$fS = [0, 2]\cup\{3\}\cup[4, 5]$$,
3. $$gS = (-\infty, 0]\cup\{1\}\cup[2,3)\cup(3, 4)\cup([4, 5]\cap(\mathbb{R}\setminus\mathbb{Q}))\cup(5, \infty)$$,
4. $$fgS = (-\infty, 0]\cup\{1\}\cup[2,\infty)$$,
5. $$gfS = (-\infty, 0)\cup(2, 3)\cup(3, 4)\cup(5, \infty)$$,
6. $$fgfS = (-\infty, 0]\cup[2, 4]\cup[5, \infty)$$,
7. $$gfgS = (0, 1)\cup(1, 2)$$,
8. $$fgfgS = [0, 2]$$,
9. $$gfgfS = (0, 2)\cup(4, 5)$$,
10. $$fgfgfS = [0, 2]\cup[4, 5]$$,
11. $$gfgfgS = (-\infty, 0)\cup(2, \infty)$$,
12. $$fgfgfgS = (-\infty, 0]\cup[2, \infty)$$,
13. $$gfgfgfS = (-\infty, 0)\cup(2, 4)\cup(5, \infty)$$,
14. $$gfgfgfgS = (0, 2)$$.

Note, taking the closure of either of the last two sets results in a set which is already on the list.

• Smallish quibble: There are 15 such strings of length at most seven: the empty string is among them. If $gfgfgfgf = gfgf$, it follows that $fgfgfgf = ggfgfgfgf = ggfgf = fgf$. Jul 24, 2014 at 2:43
• @ArthurFischer: Good pickup. That was rather careless of me. I have edited the post, though I have a different proof of $fgfgfgf = fgf$ in mind (one that is inline with the proof of $gfgfgfgf = gfgf$). Jul 24, 2014 at 2:53
• @MichaelAlbanese can you please also explicitly show that for the set $$S \colon= (0,1) \cup (1,2) \cup \{3\} \cup \left( [4,5] \cap \mathbb{Q} \right),$$ all the $14$ strings actually produce distinct sets? Jan 26, 2016 at 7:40
• @SaaqibMahmuud: I have added this to my answer. Jan 26, 2016 at 10:06

The following page lists the rest, and since it lets you experiment in real time, may also accelerate your intuitive and pictorial understanding: