IV.4 · Open & Closed Sets — Problem 4 #

← Back to IV. Open & Closed Sets, Problem 4

Problem. Starting from a subset \(T \subseteq \mathbb{R}\) and repeatedly applying the operations “take the complement” and “take the closure,” what is the largest number of distinct sets you can produce? Exhibit a set \(T\) achieving the maximum.

Hint #

Call the closure operation \(k\) and complementation \(c\). The crucial fact is that the interior operation \(i = kck\,c\) (complement, close, complement) is idempotent on closures: applying closure–interior–closure–interior collapses. In fact one can prove the identity \(kckckck = kck\). This forces the list of obtainable sets to stop after finitely many — at most \(14\). Then hunt for a single \(T \subseteq \mathbb{R}\) (mixing an open interval, an isolated point, and a dense-but-incomplete piece like the rationals) that actually realizes all \(14\).

Solution #

This problem is known as the Kuratowski Closure–Complement problem, and can be posed for any metric space, not just \(\mathbb{R}\). In our setting, the answer is 14. Note that if we were using the discrete metric, closure is a useless operator (as all sets are closed) and the answer is \(2\) — a set and its complement!

(The instructor’s notes here are brief, referring the reader to a paper by James Fife, “The Kuratowski Closure–Complement Problem,” for the details; see https://www.jstor.org/stable/2691300. A full self-contained argument — both the upper bound \(14\) and an explicit set of \(\mathbb{R}\) achieving it — is given below.)

Long solution #

Strategy. The answer is \(14\), and the proof has two independent halves. Upper bound: think of “complement” and “closure” as operators \(c\) and \(k\) that can be composed into words like \(kckc\). Two obvious relations (\(cc = \mathrm{id}\) and \(kk = k\)) shrink the supply of words to alternating ones, and one non-obvious relation — \(kckckck = kck\), proved via the interior operator — cuts the alternating words down to exactly \(14\) distinct operators. So no starting set can ever produce more than \(14\) sets. Lower bound: exhibit one set \(T \subseteq \mathbb{R}\) for which all \(14\) operators give genuinely different answers. The trick is to build \(T\) out of several “features” (an interval with a point deleted, an isolated point, a dense set of rationals) that react differently to closure and interior, so no two words can collapse on it.

Throughout, write \(c\) for complementation \(A \mapsto A^c = \mathbb{R} \setminus A\) and \(k\) for closure \(A \mapsto \overline{A}\). Words compose right-to-left: \(kc(T) = \overline{T^c}\) means “complement first, then close.”

Step 1: two basic relations.

• \(c\) is an involution: \(cc = \mathrm{id}\). Removing a set from \(\mathbb{R}\) and then removing the result recovers the original set: \(x \in (A^c)^c \iff x \notin A^c \iff x \in A\).
• \(k\) is idempotent: \(kk = k\). By Problem 3, \(\overline{A}\) is a closed set; and a closed set \(F\) equals its own closure, because \(\overline{F}\) is the smallest closed set containing \(F\), and \(F\) itself is a closed set containing \(F\), so \(\overline{F} \subseteq F \subseteq \overline{F}\).

Consequently, in any word in \(c\) and \(k\) we may cancel any adjacent pair \(cc\) and merge any adjacent pair \(kk\). Repeating until nothing cancels, every word reduces to an alternating word: \(kckck \cdots\) or \(ckckc \cdots\) (or \(\mathrm{id}\)).

We will also need that \(k\) is monotone: if \(A \subseteq B\) then \(\overline{A} \subseteq \overline{B}\). This follows from Problem 3 as well: \(\overline{B}\) is a closed set containing \(B \supseteq A\), and \(\overline{A}\) is the smallest closed set containing \(A\), so \(\overline{A} \subseteq \overline{B}\).

Step 2: the key collapse \(kckckck = kck\).

Define \(i := ckc\). Applied to a set \(A\), this gives \(i(A) = \big(\overline{A^c}\big)^c\), which is exactly the interior \(\mathrm{int}(A)\) — the largest open set contained in \(A\). (Reason: \(\overline{A^c}\) is the smallest closed set containing \(A^c\); taking complements reverses inclusions and swaps closed with open, turning “smallest closed superset of \(A^c\)” into “largest open subset of \(A\).”) In particular \(i(A)\) is always open, and \(i(U) = U\) when \(U\) is open.

Lemma (closure–interior collapse). For every open set \(U\),

$$ \overline{\mathrm{int}\big(\overline{U}\big)} = \overline{U}, \qquad \text{i.e.} \qquad k\,i\,k\,(U) = k(U). $$

In words: once you have closed an open set, alternating interior and closure produces nothing new.

Proof of Lemma. We prove the two inclusions separately.

(\(\supseteq\)) Since \(U\) is open and \(U \subseteq \overline{U}\), the set \(U\) is an open subset of \(\overline{U}\); since \(\mathrm{int}(\overline{U})\) is the largest open subset of \(\overline{U}\), we get \(U \subseteq \mathrm{int}(\overline{U})\). Applying the monotone operator \(k\) to both sides: \(\overline{U} \subseteq \overline{\mathrm{int}(\overline{U})}\).

(\(\subseteq\)) The interior of any set is contained in the set, so \(\mathrm{int}(\overline{U}) \subseteq \overline{U}\). Applying \(k\) and using \(kk = k\): \(\overline{\mathrm{int}(\overline{U})} \subseteq \overline{\overline{U}} = \overline{U}\).

The two inclusions give equality. \(\square\)

Now let \(A\) be an arbitrary set and apply the Lemma to the open set \(U = i(A)\):

Translate into \(c\) and \(k\) by substituting \(i = ckc\) and cancelling every adjacent pair \(cc\):

so the identity reads \(kckckckc = kckc\). Composing both sides on the right with \(c\) (which is invertible, since \(cc = \mathrm{id}\)) removes the trailing \(c\) from each side:

Step 3: only 14 words survive.

By Step 1 every word reduces to an alternating word. Identity \((†)\) says the 7-letter block \(kckckck\) may be replaced by \(kck\); any alternating word of length \(\geq 8\), and the length-7 word beginning with \(k\), contains this block and therefore collapses to a strictly shorter alternating word. (An alternating word of length 8 contains two 7-letter windows, one of which begins with \(k\).) Iterating, every word reduces to one of:

together with \(\mathrm{id}\). Note the asymmetry: \(kckckck\) reduces by \((†)\), but the length-7 word \(ckckckc\) does not contain the block \(kckckck\), so it survives; its length-8 extensions \(kckckckc\) and \(ckckckck\) both contain the block and reduce (to \(kckc\) and \(ckck\) respectively), so the lists stop where shown. The count is

Therefore no subset of \(\mathbb{R}\) can yield more than 14 distinct sets under closure and complementation. (The \(14\) surviving words might in principle still coincide on particular sets — the point of Step 4 is that on a well-chosen set they do not.)

Step 4: a set achieving all 14.

Take

Each piece is chosen to defeat a different potential coincidence: the two open intervals share the missing point \(1\) (closure fills it in, interior does not restore it); \(3\) is an isolated point (it survives closure but is destroyed by interior); and \([4,5] \cap \mathbb{Q}\) is dense in \([4,5]\) but has empty interior (closure inflates it to a full interval, interior annihilates it).

The first few sets in the orbit of \(T\). Closure (\(kT\)) fills the missing point \(1\), the endpoints, and the gaps in the rational dust; interior (\(ckcT\)) instead deletes the isolated point \(3\) and the dust entirely. Following with another closure gives \([0,2]\) — already the fourth distinct set.

We now compute all \(14\) sets. Each computation is one application of \(c\) (complement in \(\mathbb{R}\)) or \(k\) (closure) to the line above it; recall that the closure of an interval fills in its endpoints, and that \([4,5] \cap \mathbb{Q}\) and \([4,5] \setminus \mathbb{Q}\) are each dense in \([4,5]\), so both have closure \([4,5]\).

Spot-checking two rows to show how the computations go. For \(kc\): the complement \(cT\) (row 8) closes up as follows — \((-\infty,0]\) is already closed; \(\{1\}\) is closed; \([2,3) \cup (3,4)\) closes to \([2,4]\); \([4,5] \setminus \mathbb{Q}\) is dense in \([4,5]\), so it closes to \([4,5]\); and \((5,\infty)\) closes to \([5,\infty)\). The union is \((-\infty,0] \cup \{1\} \cup [2,\infty)\). For \(ckc\): complementing \(kcT\) leaves \((0,2)\) minus the point \(1\), i.e. \((0,1) \cup (1,2)\) — which is exactly \(\mathrm{int}(T)\), as it should be since \(ckc = i\).

As a consistency check on identity \((†)\): applying \(k\) to row \(ckckck\) gives \(\overline{(-\infty,0) \cup (2,4) \cup (5,\infty)} = (-\infty,0] \cup [2,4] \cup [5,\infty)\), which is indeed the row \(kck\) again — the orbit has closed up, exactly as \((†)\) predicts.

Finally, the \(14\) sets listed are pairwise distinct. This can be read off the table directly: only two rows involve the rational “dust” (\(\mathrm{id}\) and \(c\), distinguishable since one contains \(\frac{1}{2}\) and the other does not); among the remaining twelve, no two have the same collection of endpoints, bounded/unbounded pieces, and isolated points. So the orbit of \(T\) has exactly \(14\) members.

Conclusion. The maximum number of distinct sets obtainable from a subset of \(\mathbb{R}\) by successively applying closure and complementation is exactly

The upper bound is Steps 1–3 (the operator identity \(kckckck = kck\) leaves only \(14\) reduced words), and the bound is attained by the set of Step 4.

Remark. The bound \(14\) is a theorem about the operators, so it holds verbatim in any topological space; a space merely may or may not contain a set realizing it (\(\mathbb{R}\) does — such sets are called 14-sets). At the other extreme, in a discrete metric space the closure operator does nothing (\(k = \mathrm{id}\), since every set is closed), and the orbit of any set \(T\) is just \(\{T,\, T^c\}\) — at most \(2\) sets. This problem is the classical Kuratowski closure–complement problem (1922). \(\blacksquare\)