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

Solution 1:

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.

Solution 2:

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

http://www.maa.org/sites/default/files/images/upload_library/60/bowron/k14.html

Though the 14-set theorem is more algebraic than topological, constructing a Kuratowski 14-set in the reals will enrich your understanding of topology.