Moore closure and realizing the Kuratowski monoid

Question

It is well-known result of Kuratowski that starting from a topological closure operation $C: P(X) \to P(X)$ (taking a subset $A \subseteq X$ to its closure $C(A)$ relative to a given topology on $X$) and the complementation operation $\neg: P(X) \to P(X)$, and taking the closure of $C, \neg$ under composition, we can get no more than 14 operations on $P(X)$. These are

$$1, \qquad \neg, \qquad C, \qquad \neg C, \qquad C \neg, \qquad \neg C \neg, \qquad C \neg C, \qquad \neg C \neg C, \qquad C \neg C \neg, \qquad \neg C \neg C \neg, \qquad C \neg C \neg C, \qquad \neg C \neg C \neg C, \qquad C \neg C \neg C \neg, \qquad \neg C \neg C \neg C \neg $$

where $1$ denotes the identity operator $P(X) \to P(X)$.

This result alone isn't particularly topological: if $C: P(X) \to P(X)$ is any Moore closure operator (meaning $A \subseteq C(A)$ and $CC(A) = C(A)$ and $C(A) \subseteq C(B)$ whenever $A \subseteq B$), then again there is a maximum of 14 possible such operations. In a nutshell, one may prove that $C \neg C \neg C \neg C = C \neg C$ just by playing with the Moore closure axioms, and observe that the free monoid in letters $C, \neg$, modulo the relations $\neg \neg = 1$, $C C = C$, and $C \neg C \neg C \neg C = C \neg C$, results in the 14-element monoid indicated above, called the Kuratowski monoid.

Part of the lore here is an exercise in point-set topology: give a topology for which all 14 such operations are distinguished, i.e., exhibit a space $X$ and a subset $A \subseteq X$ where you get 14 distinct subsets by applying these operations. (One solution: take $\mathbb{R}$ with its usual topology, and $A = (0, 1) \cup (1, 2) \cup \{3\} \cup ([4, 5] \cap \mathbb{Q})$.)

But there are many, many types of Moore closure operations (e.g., for any algebraic theory $T$ and $T$-algebra $X$, define $C(A)$ to be the smallest subalgebra containing $A$). Most of them don't satisfy the axioms that make a closure operator topological, viz.: $C(\emptyset) = \emptyset$ and $C(A \cup B) = C(A) \cup C(B)$.

Question: is there a reasonably simple example of a non-topological Moore closure operator $C$ for which the 14 Kuratowski operations are all distinct?

(I'm having trouble thinking of really good tags; please feel free to add more or re-tag.)

Answer 1

Thanks to the link (provided by rschwieb in a comment) to "Kuratowski's Closure-Complement Cornucopia", I was able to locate what I consider a reasonably satisfactory example in

• Janusz Brzozowski, Elyot Grant, Jeffrey Shallit, Closures in Formal Languages and Kuratowski’s Theorem, http://arxiv.org/pdf/0901.3761.pdf.

In essence the article analyzes the situation where we consider a free monoid $\Sigma^\ast$ on a set $\Sigma$, consisting of words in the alphabet $\Sigma$, and closure operators $C_+$, $C_\ast$ on $P(\Sigma^\ast)$ which take a subset $A \subseteq \Sigma^\ast$ (aka a formal language in the alphabet $\Sigma$) to the subsemigroup $C_+(A) \subseteq \Sigma^\ast$ generated by $A$, or to the submonoid $C_\ast(A) \subseteq \Sigma^\ast$ generated by $A$. If $K$ denotes the 14-element Kuratowski monoid, then for each of these closure operators there is an induced monoid map

$$K \to \hom(P(\Sigma^\ast), P(\Sigma^\ast))$$

taking $C$ to $C_+$ or $C_\ast$ and $\neg$ to complementation. Each induces a $K$-action $K \times P(\Sigma^\ast) \to P(\Sigma^\ast)$, and the authors analyze the possible structures of orbits $\text{orb}(A) = \{k \cdot A: k \in K\}$. In particular, there exists an $A \in P(\Sigma^\ast)$ whose orbit (wrt the closure operator $C_\ast$) has 14 elements, so indeed all 14 Kuratowski operations on $P(\Sigma^\ast)$ are distinguished.

Meanwhile, the closure operators $C_+, C_\ast$ are certainly not topological. For example, $a^5$ belongs to $C_\ast(\{aa\} \cup \{aaa\})$, but clearly not to $C_\ast(\{aa\}) \cup C_\ast(\{aaa\})$, so $C_\ast$ does not preserve unions. In fact, this sort of "$T$-subalgebra example" of closure operation (mentioned in the OP) was just what I was hoping to find; here $T$ is the algebraic theory of monoids.

An example of a language $A \subseteq \{a, b\}^\ast$ whose orbit $\{A, \neg A, C_\ast(A), \neg (C_\ast(A)), \ldots\}$ has 14 elements is $\{a, ab, bb\}$. A tedious case-by-case verification shows this works, but the authors show that in order to get the 14 elements, it suffices to observe that (1) $A$ is neither $C_+$-closed nor $C_+$-open (i.e., not a fixed point of $\neg C_+ \neg$), (2) $C_+(A)$ is not $C_+$-open and $\neg C_+ \neg(A)$ is not $C_+$-closed, (3) the closure of the interior differs from the interior of the closure: $C_+ \neg C_+ \neg (A) \neq \neg C_+ \neg C_+ (A)$.