11
$\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

25
$\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
  • 1
    $\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
  • 1
    $\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
5
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .