6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If something like that exists, then I imagine it wouldn't take long looking at Kuratowski cornucopia to find it $\endgroup$ – rschwieb Aug 25 '16 at 17:36
  • $\begingroup$ @rschwieb Thanks! Oof, this site doesn't look easy to navigate though. $\endgroup$ – user43208 Aug 25 '16 at 18:15
  • $\begingroup$ This is the one to start with: mathtransit.com/cornucopia/2008_gj_a.php $\endgroup$ – rschwieb Aug 25 '16 at 18:50
  • $\begingroup$ 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. $\endgroup$ – Slade Aug 25 '16 at 18:52
  • $\begingroup$ @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. $\endgroup$ – user43208 Aug 25 '16 at 19:39
1
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.