Cierre de Moore y al darse cuenta el monoid de Kuratowski

Question

Es bien conocido el resultado de Kuratowski que a partir de un topológico de cierre de la operación $C: P(X) \to P(X)$ (tomando un subconjunto $A \subseteq X$ a su cierre $C(A)$ en relación a una determinada topología en $X$) y la complementación de operación $\neg: P(X) \to P(X)$, y tomando el cierre de $C, \neg$ en la composición, podemos obtener no más de 14 operaciones en $P(X)$. Estos son

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

donde $1$ denota la identidad del operador $P(X) \to P(X)$.

Este resultado por sí solo no es particularmente topológicos: si $C: P(X) \to P(X)$ es cualquier Moore cierre de operador (significado $A \subseteq C(A)$ $CC(A) = C(A)$ $C(A) \subseteq C(B)$ siempre $A \subseteq B$), a continuación, de nuevo hay un máximo de 14 posibles tales operaciones. En pocas palabras, uno puede demostrar que el $C \neg C \neg C \neg C = C \neg C$ jugando con las Moore cierre de axiomas, y observar que el libre monoid en letras $C, \neg$, modulo de las relaciones $\neg \neg = 1$, $C C = C$, y $C \neg C \neg C \neg C = C \neg C$, los resultados del 14-elemento monoid indicado anteriormente, llama la Kuratowski monoid.

Parte de la historia aquí es un ejercicio en el punto-conjunto de topología: la topología para que todos los 14 de tales operaciones se distinguen, es decir, una exposición, un espacio de $X$ y un subconjunto $A \subseteq X$ donde dispones de 14 distintos subconjuntos mediante la aplicación de estas operaciones. (Una solución: tome $\mathbb{R}$ con su habitual topología, y $A = (0, 1) \cup (1, 2) \cup \{3\} \cup ([4, 5] \cap \mathbb{Q})$.)

Pero hay muchos, muchos tipos de Moore cierre de las operaciones (por ejemplo, para cualquier teoría algebraica $T$ $T$- álgebra $X$, definir $C(A)$ a ser el más pequeño subalgebra que contengan $A$). La mayoría de ellos no cumple con los axiomas que hacer un cierre operador topológico, viz.: $C(\emptyset) = \emptyset$ $C(A \cup B) = C(A) \cup C(B)$ .

Pregunta: hay una bastante simple ejemplo de un no-topológico Moore cierre operador $C$ para que el 14 de Kuratowski operaciones son todos distintos?

(Estoy teniendo problemas para pensar realmente buena etiquetas; por favor, siéntase libre de añadir más o re-etiqueta.)

Answer 1

Gracias a la conexión (suministrados por rschwieb en un comentario)"Kuratowski del Cierre del Complemento cuerno de la Abundancia", yo era capaz de localizar lo que yo considere razonablemente satisfactoria ejemplo en

• Janusz dawes de aspect security, Elyot de la Subvención, Jeffrey Shallit, Cierres en los Lenguajes Formales y el Teorema de Kuratowski, http://arxiv.org/pdf/0901.3761.pdf.

En esencia, el artículo analiza la situación en la que consideramos una libre monoid $\Sigma^\ast$ sobre un conjunto $\Sigma$, que consta de palabras en el alfabeto $\Sigma$, y el cierre de los operadores $C_+$, $C_\ast$ en $P(\Sigma^\ast)$ que tomar un subconjunto $A \subseteq \Sigma^\ast$ (también conocido como un lenguaje formal en el alfabeto $\Sigma$) a la subsemigroup $C_+(A) \subseteq \Sigma^\ast$ generado por $A$, o a la submonoid $C_\ast(A) \subseteq \Sigma^\ast$ generado por $A$. Si $K$ denota el 14-elemento de Kuratowski monoid, a continuación, para cada uno de estos cierre de los operadores no es un inducida por monoid mapa

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

tomando $C$ $C_+$o $C_\ast$ $\neg$ a de complementación. Cada induce una $K$-acción $K \times P(\Sigma^\ast) \to P(\Sigma^\ast)$, y los autores analizan las posibles estructuras de órbitas $\text{orb}(A) = \{k \cdot A: k \in K\}$. En particular, existe un $A \in P(\Sigma^\ast)$ cuya órbita (wrt el cierre operador $C_\ast$) cuenta con 14 elementos, por lo que, de hecho, todos los 14 de Kuratowski operaciones en $P(\Sigma^\ast)$ son distinguidos.

Mientras tanto, el cierre de los operadores de $C_+, C_\ast$ son sin duda no topológico. Por ejemplo, $a^5$ pertenece a $C_\ast(\{aa\} \cup \{aaa\})$, pero claramente no $C_\ast(\{aa\}) \cup C_\ast(\{aaa\})$, lo $C_\ast$ no preservar los sindicatos. De hecho, este tipo de "$T$-subalgebra ejemplo" de cierre de la operación (como se menciona en el OP) era justo lo que estaba esperando encontrar; aquí $T$ es la teoría algebraica de monoids.

Un ejemplo de un lenguaje de $A \subseteq \{a, b\}^\ast$ cuya órbita $\{A, \neg A, C_\ast(A), \neg (C_\ast(A)), \ldots\}$ tiene 14 elementos es $\{a, ab, bb\}$. Un tedioso caso-por-caso de la verificación muestra que esto funciona, pero los autores muestran que en el fin de obtener los 14 elementos, basta observar que (1) $A$ ni $C_+$-cerrado ni $C_+$-abierto, es decir, no es un punto fijo de $\neg C_+ \neg$), (2) $C_+(A)$ no es $C_+$-abrir y $\neg C_+ \neg(A)$ no $C_+$-cerrado, (3) el cierre de la interior difiere desde el interior de la clausura: $C_+ \neg C_+ \neg (A) \neq \neg C_+ \neg C_+ (A)$.