10
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Why did you not include $fgf$ in your list? $\endgroup$
    – user642796
    Jul 24, 2014 at 2:03
  • $\begingroup$ 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. $\endgroup$ Jan 26, 2016 at 15:03

2 Answers 2

24
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – user642796
    Jul 24, 2014 at 2:43
  • $\begingroup$ @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$). $\endgroup$ Jul 24, 2014 at 2:53
  • $\begingroup$ @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? $\endgroup$ Jan 26, 2016 at 7:40
  • $\begingroup$ @SaaqibMahmuud: I have added this to my answer. $\endgroup$ Jan 26, 2016 at 10:06
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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