# Moore closure and realizing the Kuratowski monoid

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.)

• If something like that exists, then I imagine it wouldn't take long looking at Kuratowski cornucopia to find it – rschwieb Aug 25 '16 at 17:36
• @rschwieb Thanks! Oof, this site doesn't look easy to navigate though. – user43208 Aug 25 '16 at 18:15
• This is the one to start with: mathtransit.com/cornucopia/2008_gj_a.php – rschwieb Aug 25 '16 at 18:50
• You can construct a non-topological example from a topological one: if $(X,C)$ is a closure system, then $X\cup\{\ast\}$ has a closure operator given by $C_\ast(V) = C(V\cap X) \cup \{\ast\}$. $C_\ast$ restricts to $C$, so if the 14 operations are distinct on $X$, then they're certainly distinct on $X\cup\{\ast\}$. I'll post an answer if I can think of a simpler example that does not arise from a topological space. – Slade Aug 25 '16 at 18:52
• @Slade Thanks -- that certainly is an answer to the question. I suppose such examples can be ruled out by demanding that closure fail to preserve binary unions, as opposed to failing that or failing to preserve the empty set. Meanwhile, I think (thanks to rschwieb's lead) that I found an answer to my question, but I'll hold off saying more for a while, to see if others have answers. – user43208 Aug 25 '16 at 19:39

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)$.