Exercise 17.21 (Kuratowski's closure-complement problem)

Question

(Kuratowski) Consider the collection of all subsets $A$ of the topological space $X$.
The operations of closure $A 	o \overline{A}$ and complementation $A 	o X - A$ are functions from the collection to itself.
\begin{enumerate}[label=(\alph*)]
  \item Show that starting with a given set $A$, one can form no more than 14 distinct sets by applying these two operations successively.
  \item Find a subset $A$ of ${\mathbb{R}}$ (in its usual topology) for which the maximum of 14 is obtained.
\end{enumerate}

Dan Whitman · Accepted Answer

For the following, we introduce the following notation to make things simpler. If $A$ is a subset of a topological space $X$ then denote
\begin{align*}
  cA &= \overline{A} &
                       xA &= X - C \
  iA &= \mathrm{Int}\,{A} &
                            bA &= \mathrm{Bd}\,{A} \,.
\end{align*}
We can consider these ($c$, $x$, $i$, and $b$) as operators on sets that can be chained together in an obvious way so that, for example, $cxiA = \overline{X - \mathrm{Int}\,{A}}$.

\begin{lemma}\label{lem:closedlim:part}
  For a subset $A$ of topological space $X$, $X = cA \cup ixA$, and $cA$ and $ixA$ are disjoint
\end{lemma}
\begin{proof}
  First, it is obvious that $cA \cup ixA \subset X$ since each of the sets in the union is a subset of $X$.
  Now consider any $x \in X$ and suppose that $x 
otin cA = \overline{A}$.
  Then by Lemma~17.5 part~(a) there is an open set $U$ containing $x$ where $U$ does not intersect $A$.
  For any $y \in U$ we thus have that $y 
otin A$ and hence $y \in X - A = xA$.
  This shows that $U \subset xA$ since $y$ was arbitrary, which suffices to show that $x \in \mathrm{Int}\,(xA) = ixA$ since $U$ is a neighborhood of $x$.
  This of course shows that $x \in cA \cup ixA$ so that $X \subset cA \cup ixA$ since $x$ was arbitrary.
  This completes the proof that $X = cA \cup ixA$.

To show that $cA$ and $ixA$ are disjoint, consider any $x \in cA$.
  Consider any neighborhood $U$ of $x$ so that $U$ intersects $A$ by Lemma~17.5 part~(a).
  Hence there is a point $y \in U$ where also $y \in A$, from which it follows that $y 
otin X - A = xA$.
  This suffices to show that $U$ is not a subset of $xA$.
  Since $U$ is an arbitrary neighborhood, this shows that $x 
otin \mathrm{Int}\,(xA) = ixA$.
  This of course shows that $cA$ and $ixA$ are disjoint as desired.
\end{proof}

\begin{lemma}\label{lem:closedlim:idents}
  For a subsets $A$ and $B$ of topological space $X$ where $A \subset B$, we have the following:
  \begin{multicols}{3}
    \begin{enumerate}[label=(\alph*)]
    \item $cA \subset cB$
    \item $iA \subset iB$
    \item $ccA = cA$
    \item $iiA = iA$
    \item $xxA = A$
    \item $xcA = ixA$
    \item $xiA = cxA$
    \item $icicA = icA$
    \item $ciciA = ciA$.
    \end{enumerate}
  \end{multicols}
\end{lemma}
\begin{proof}
  (a) This was shown in Exercise~17.6 part~(a).

(b) Consider any $x \in iA$ so that there is a neighborhood $U$ of $x$ that is totally contained in $A$.
  Then clearly $U$ is also totally contained in $B$ as well since, for any $x \in U$, we have that $x \in A$ and hence $x \in B$ since $A \subset B$.
  This shows that $x \in iB$ since $U$ is a neighborhood of $x$.
  Hence $iA \subset iB$ since $x$ was arbitrary.

(c) Since $cA = \overline{A}$ is closed, we clearly have $ccA = cA$.

(d) Since $iA = \mathrm{Int}\,{A}$ is open, its interior is itself, i.e.  $iiA = iA$.

(e) Obviously $xxA = X - (X - A) = A$ since $A \subset X$.

(f) We have by Lemma~ef{lem:closedlim:part} that $X = cA \cup ixA$ where $cA$, and $ixA$ are mutually disjoint.
  From this it follows that $ixA = X - cA = xcA$.

(g) We have
  \begin{align*}
    cxA &= xxcxA & 	ext{(by (e))} \
        &= xixxA & 	ext{(by (f))} \
        &= xiA & 	ext{(by (e) again)}
  \end{align*}
  as desired.

(h) First we have that $icA = iicA$ by (d).
  Also clearly $icA = c(icA) = cicA$ since a set is always a subset of its closure.
  Hence by (b) we have that $icA = iicA = i(icA) \subset i(cicA) = icicA$.
  Now, we also have that $icA = i(cA) \subset cA$ since the interior of a set is always a subset of the set.
  Hence by (a) and (c) we have $cicA = c(icA) \subset c(cA) = ccA = cA$.
  It then follows from (b) that $icicA = i(cicA) \subset i(cA) = icA$ as well.
  This of course shows that $icicA = icA$ as desired.

(i) Lastly, we have
  \begin{align*}
    ciciA &= cicixxA & 	ext{(by (e))} \
          &= cicxcxA & 	ext{(by (f))} \
          &= cixicxA & 	ext{(by (g))} \
          &= cxcicxA & 	ext{(by (f))} \
          &= xicicxA & 	ext{(by (g))} \
          &= xicxA & 	ext{(by (h))} \
          &= cxcxA & 	ext{(by (g))} \
          &= cixxA & 	ext{(by (f))} \
          &= ciA & 	ext{(by (e))}
  \end{align*}
  as desired.
\end{proof}

extbf{Main Problem.}

(a)
\def\pres{	ext{(previous result)}}

ewcommand\lemref[1]{	ext{(by Lemma~ef{lem:closedlim:idents}#1)}}
\begin{proof}
  We are interested in sequences applying the operators $c$ and $x$ to a subset $A$.
  By Lemma~ef{lem:closedlim:idents} (c) and (e) we have that $ccA = cA$ and $xxA = A$.
  Thus there is no point in ever applying $c$ or $x$ twice in a row since that would clearly result in a set that we have seen before.
  We are then interested only in sequences that apply alternating $c$ and $x$.
  If we apply the closure $c$ first, we obtain the following sequence:
  \begin{align*}
    A &= A \
    cA &= cA \
    xcA &= ixA & \lemref{f} \
    cxcA &= cixA & \pres \
    xcxcA &= xcixA & \pres \
      &= ixixA & \lemref{f} \
      &= icxxA & \lemref{g} \
      &= icA & \lemref{e} \
    cxcxcA &= cicA & \pres \
    xcxcxcA &= xcicA & \pres \
      &= ixicA & \lemref{f} \
      &= icxcA & \lemref{g} \
      &= icixA & \lemref{f}
  \end{align*}
  If we apply the next operation we obtain
  \begin{align*}
    cxcxcxcA &= cicixA & \pres \
             &= cixA \,, & \lemref{i}
  \end{align*}
  which is the same as the fourth set above.
  Therefore we can get at most 7 distinct sets by applying $c$ first, including $A$ itself.
  If we instead apply $x$ first then we get the following sequence:
  \begin{align*}
    xA &= xA \
    cxA &= cxA \
    xcxA &= ixxA & 	ext{(corresponding result above)} \
       &= iA & \lemref{e} \
    cxcxA &= ciA & \pres \
    xcxcxA &= xciA & \pres \
       &= ixiA & \lemref{f} \
       &= icxA & \lemref{g} \
    cxcxcxA &= cicxA & \pres \
    xcxcxcxA &= xcicxA & \pres \
       &= ixicxA & \lemref{f} \
       &= icxcxA & \lemref{g} \
       &= icixxA & \lemref{f} \
       &= iciA & \lemref{e}
  \end{align*}
  Again if we try to apply the next operation we get
  \begin{align*}
    cxcxcxcxA &= ciciA & \pres \
              &= ciA\, & \lemref{i}
  \end{align*}
  which as before is the same as the fourth set in the sequence.
  Hence we have at most 7 distinct sets in this sequence for a total of 14 potentially distinct sets as desired.
\end{proof}

Note that this only shows that there can be \emph{no more than} 14 distinct sets.
It could be that there are always fewer than 14 in general.
While there are certain sets that generate less than 14 distinct sets, the next part shows the existence of a topology and a set that does result in 14 distinct sets.
This of course shows that 14 is the lowest possible bound in general.

(b) We claim that $A = (-3, -2) \cup (-2, -1)  \cup ([0,1] \cap {\mathbb{Q}}) \cup \left\{2ight\}$ in the standard topology on ${\mathbb{R}}$ is a set that results in 14 distinct sets when the operational sequences from part~(a) are applied.
We do not prove each sequential operation as this is easy but would be prohibitively tedious.
First, we enumerate the first sequence, starting with $A$.
\begin{center}
  \begin{tabular}{c|c}
    Operations & Set \
    \hline
    $A$ & $(-3, -2) \cup (-2, -1) \cup ([0,1] \cap {\mathbb{Q}}) \cup \left\{2ight\}$ \
    $cA$ & $[-3,-1] \cup [0,1] \cup \left\{2ight\}$ \
    $xcA = ixA$ & $(-\infty, -3) \cup (-1, 0) \cup (1,2) \cup (2, \infty)$ \
    $cxcA = cixA$ & $(-\infty, -3] \cup [-1,0] \cup [1, \infty)$ \
    $xcxcA = icA$ & $(-3, -1) \cup (0, 1)$ \
    $cxcxcA = cicA$ & $[-3, -1] \cup [0, 1]$ \
    $xcxcxcA = icixA$ & $(-\infty, -3) \cup (-1,0) \cup (1, \infty)$
  \end{tabular}
\end{center}
Next, we enumerate the next sequence of 7 sets, starting with $xA$:
\begin{center}
  \begin{tabular}{c|c}
    Operations & Set \
    \hline
    $xA$ & $(-\infty,-3] \cup \left\{-2ight\} \cup [-1,0) \cup \left((0,1) - {\mathbb{Q}}ight) \cup (1,2) \cup (2, \infty)$ \
    $cxA$ & $(-\infty -3] \cup \left\{-2ight\} \cup [-1, \infty)$ \
    $xcxA = iA$ & $(-3, -2) \cup (-2, -1)$ \
    $cxcxA = ciA$ & $[-3, -1]$ \
    $xcxcxA = icxA$ & $(-\infty, -3) \cup (-1, \infty)$ \
    $cxcxcxA = cicxA$ & $(-\infty, -3] \cup [-1, \infty)$ \
    $xcxcxcxA = iciA$ & $(-3, 1)$
  \end{tabular}
\end{center}
It is easy to see that these are 14 distinct sets.

We do note that, in an interval containing only rationals (or only irrationals), such as $[0,1] \cap {\mathbb{Q}}$ used as part of $A$, clearly every point in the interval is a limit point, including any irrational (or rational) points.
This is because any open interval containing any real always contains both rationals and irrationals on account of ${\mathbb{Q}}$ being order-dense in ${\mathbb{R}}$.
For the same reason, no point of such an interval of rationals (or irrationals) is in its interior.
If, for example $C = [0,1] \cap {\mathbb{Q}}$, this clearly then results in $cC = [0,1]$ and $iC = \varnothing$.
Indeed this property of this part of $A$ is crucial in its success in generating 14 distinct sets.

Exercise 17.21 (Kuratowski's closure-complement problem)

Answers

Comments

Operations	Set

$A$	$(- 3, - 2) \cup (- 2, - 1) \cup ([0, 1] \cap ℚ) \cup {2}$
$cA$	$[- 3, - 1] \cup [0, 1] \cup {2}$
$xcA = ixA$	$(- \infty, - 3) \cup (- 1, 0) \cup (1, 2) \cup (2, \infty)$
$cxcA = cixA$	$(- \infty, - 3] \cup [- 1, 0] \cup [1, \infty)$
$xcxcA = icA$	$(- 3, - 1) \cup (0, 1)$
$cxcxcA = cicA$	$[- 3, - 1] \cup [0, 1]$
$xcxcxcA = icixA$	$(- \infty, - 3) \cup (- 1, 0) \cup (1, \infty)$

Operations	Set

$xA$	$(- \infty, - 3] \cup {- 2} \cup [- 1, 0) \cup ((0, 1) - ℚ) \cup (1, 2) \cup (2, \infty)$
$cxA$	$(- \infty - 3] \cup {- 2} \cup [- 1, \infty)$
$xcxA = iA$	$(- 3, - 2) \cup (- 2, - 1)$
$cxcxA = ciA$	$[- 3, - 1]$
$xcxcxA = icxA$	$(- \infty, - 3) \cup (- 1, \infty)$
$cxcxcxA = cicxA$	$(- \infty, - 3] \cup [- 1, \infty)$
$xcxcxcxA = iciA$	$(- 3, 1)$

Exercise 17.21 (Kuratowski's closure-complement problem)

Answers

Comments

Add answer