🔢 mathematics

Rewriting Systems on Arbitrary Monoids

Este artículo introduce los sistemas de reescritura monoidales (MRS) como una abstracción de la reescritura de cadenas sobre monoides ambientales arbitrarios para abordar las limitaciones lógicas de los monoides libres, y establece una biadjunción canónica entre la 2-categoría de los MRS noéticos y confluentes y la categoría de los monoides, al tiempo que clasifica todos los sistemas de este tipo que presentan un monoide fijo mediante Transformaciones de Tietze Elementales Generalizadas.

Autores originales: Eduardo Magalhães

Publicado 2026-02-02

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Eduardo Magalhães

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando resolver un rompecabezas donde tienes un conjunto de reglas para cambiar una cosa en otra. En el mundo de la informática y las matemáticas, esto se hace habitualmente con cadenas de letras (como palabras en un diccionario). Si tienes la palabra "cat" y una regla que dice que "cat" se convierte en "dog", puedes intercambiarlas. Esta es la forma tradicional de hacer las cosas, llamada Reescritura de Cadenas (String Rewriting).

Sin embargo, el autor de este artículo, Eduardo Magalhães, plantea una pregunta simple pero profunda: ¿Qué pasaría si no estuviéramos jugando solo con palabras? ¿Qué pasaría si estuviéramos jugando con números, formas o incluso ideas abstractas que no se parecen en nada a las palabras?

Aquí tienes un desglose de las ideas principales del artículo utilizando analogías de la vida cotidiana:

1. El Problema: Ser demasiado exigente con las "palabras"

Tradicionalmente, los sistemas de reescritura solo funcionan sobre Monoides Libres. Piensa en un Monoide Libre como un almacén gigante y vacío donde solo puedes apilar cajas (letras) en línea. Solo puedes combinarlas pegándolas una tras otra.

El Problema: El artículo argumenta que esto es demasiado limitante. Es como decir que solo puedes reorganizar los muebles si estás en un almacén sin paredes. En el mundo real (y en la lógica), a menudo lidiamos con estructuras que tienen sus propias reglas internas (como un reloj donde 12 + 1 = 1, o un grupo de amigos donde "Alice + Bob" es simplemente "El Grupo").
La Brecha Lógica: El autor señala que "ser un almacén libre" es una regla muy específica y difícil de definir en el lenguaje de la lógica. Si quieres estudiar estos sistemas utilizando herramientas lógicas estándar, te quedas estancado porque no puedes definir fácilmente lo "libre" dentro del propio sistema.

2. La Solución: Sistemas de Reescritura Monoidales (MRS)

El autor introduce los Sistemas de Reescritura Monoidales (MRS).

La Analogía: En lugar de solo reorganizar letras en una línea, imagina que tienes una caja de herramientas (un Monoide). Esta caja de herramientas tiene una forma específica de combinar herramientas (multiplicación).
- En un sistema de cadenas, solo puedes pegar "A" y "B" para formar "AB".
- En un MRS, puedes combinar cualquier par de elementos en tu caja de herramientas, siempre que sigan las reglas de la caja. Tal vez tu caja de herramientas es un conjunto de números donde se suman, o un conjunto de formas donde se superponen.
El Cambio: El artículo dice: "Dejemos de pretender que todo es una palabra. Dejemos que las reglas actúen directamente sobre los objetos mismos". Esto hace que el sistema sea más flexible e "interno" a la estructura que describe.

3. El Estado "Perfecto": Noetherian y Confluente

En cualquier juego de reescritura, quieres que sucedan dos cosas:

Noetherian (Terminación): El juego debe terminar eventualmente. No puedes seguir cambiando las cosas para siempre en un bucle. (Ejemplo: No puedes tener una regla que transforme "A" en "B" y "B" de vuelta en "A" perpetuamente).
Confluente (Consistencia): No importa en qué orden apliques las reglas, deberías llegar al mismo resultado final. (Ejemplo: Si tienes una habitación desordenada, no debería importar si recoges primero los calcetines o los libros; la habitación debería quedar limpia de la misma manera).

Cuando un sistema tiene ambas propiedades, puedes tomar cualquier entrada desordenada y reducirla a una "Forma Normal" única (la versión más limpia y simple de ese objeto).

4. La Gran Conexión: El "Traductor" (Biadjunción)

El artículo construye un puente entre dos mundos:

Mundo A: El mundo desordenado y lleno de reglas de los Sistemas de Reescritura (MRS).
Mundo B: El mundo limpio y simple de los Monoides (las estructuras finales).

El autor crea un Traductor (una herramienta matemática llamada biadjunción) que funciona en ambas direcciones:

De las Reglas a la Estructura: Si tienes un conjunto de reglas, el traductor encuentra la estructura "limpia" escondida dentro de ellas (el Monoide de los irreducibles).
De la Estructura a las Reglas: Si tienes una estructura limpia (como el número 5), el traductor puede construir un conjunto "canónico" de reglas que la genera.

La Metáfora: Imagina que tienes una escultura (el Monoide).

Una forma de describirla es decir: "Está hecha de arcilla". (La Estructura).
Otra forma es dar una lista de instrucciones: "Toma un trozo, aplátalo, corta un círculo, suaviza los bordes". (El Sistema de Reescritura).
El artículo demuestra que estas dos descripciones están perfectamente vinculadas. Puedes ir de las instrucciones a la escultura, y de la escultura de vuelta al mejor conjunto posible de instrucciones, sin perder ninguna información.

5. Las Transformaciones "Tietze": Las Varitas Mágicas

Finalmente, el artículo responde a una pregunta difícil: "Si tengo dos conjuntos diferentes de reglas que construyen la misma escultura, ¿cómo se relacionan?"

En el viejo mundo de la reescritura de cadenas, existía un famoso conjunto de movimientos llamados Transformaciones de Tietze que podían convertir un conjunto de reglas en otro. El autor inventa las Transformaciones de Tietze Elementales Generalizadas (GETTs) para este mundo nuevo y más amplio.

La Analogía: Imagina que tienes dos recetas diferentes para hacer un pastel.
- La Receta A dice: "Mezclar harina, azúcar, huevos".
- La Receta B dice: "Mezclar ingredientes secos, luego ingredientes húmedos, luego hornear".
- Aunque los pasos parezcan diferentes, ambos hacen el mismo pastel.
El Resultado: El artículo demuestra que puedes transformar cualquier receta válida (MRS Noetherian Confluente) en cualquier otra receta válida para el mismo pastel usando una secuencia de estos "movimientos GETT".
- Movimiento 1: Añadir una regla que ya es verdadera (redundante).
- Movimiento 2: Eliminar una regla que ya está cubierta por otras.
- Movimiento 3: Introducir un nuevo ingrediente (símbolo) para ayudar a explicar un paso.
- Movimiento 4: Un movimiento complejo que simplifica todo el sistema centrándose en una parte específica de las reglas.

Resumen

Este artículo toma el concepto de "reescritura" (cambiar cosas basadas en reglas) y lo libera de la restricción de las "palabras". Demuestra que:

Se puede hacer en cualquier estructura matemática, no solo en cadenas.
Existe un puente lógico perfecto entre las reglas y el resultado.
Cualquier par de conjuntos de reglas que producen el mismo resultado pueden transformarse entre sí utilizando un conjunto específico y universal de movimientos.

Es un poco como darse cuenta de que, si bien puedes describir una casa enumerando sus ladrillos (cadenas), también puedes describirla mediante su plano arquitectónico (monoide), y puedes demostrar matemáticamente que cada plano tiene un conjunto único y perfecto de instrucciones para construirlo, y que cada conjunto de instrucciones conduce a un plano único.

Resumen Técnico: Sistemas de Reescriptura sobre Monoides Arbitrarios

Planteamiento del Problema
El estudio de los sistemas de reescritura ha estado históricamente dominado por los Sistemas de Reescriptura de Cadenas (SRC), donde las reducciones se definen sobre monoides libres generados por un alfabeto. Si bien los SRC proporcionan un marco robusto para resolver el problema de la palabra y analizar estructuras algebraicas, poseen una limitación estructural: están intrínsecamente ligados a los monoides libres. Desde una perspectiva lógica, esto crea un desajuste fundacional. La clase de los monoides libres no es primeramente axiomatizable; consecuentemente, al aplicar métodos de primer orden o de la teoría de modelos a las presentaciones de reescritura, la propiedad de "frialdad" (freeness) no puede tratarse internamente, sino que debe imponerse como una condición semántica externa. Además, la reescritura clásica depende fuertemente de la representación sintáctica de las palabras, lo cual puede no ser estrictamente necesario para las propiedades algebraicas subyacentes de la reducción, tales como la confluencia y la terminación.

Metodología
Para abordar estas limitaciones, el artículo introduce los Sistemas de Reescriptura Monoidales (SRM), una abstracción donde las reducciones se definen directamente sobre un monoide ambiente arbitrario $(M, \cdot)$ en lugar de un monoide libre de palabras. Un SRM se define como una terna $(M, \cdot, R)$ , donde $R \subseteq M \times M$ es una relación binaria. La relación de reducción $a \to_R b$ se define por la existencia de $x, y, s, t \in M$ tales que $a = xsy$, $b = xty $, y$ (s, t) \in R$.

La metodología procede a través de tres etapas principales:

Generalización Algebraica: El artículo establece que las propiedades fundamentales de los SRC (como la propiedad de Church-Rosser, la noetericidad y la existencia de formas normales únicas) se generalizan directamente a los SRM. Demuestra que, para un SRM confluente y noetérico, el conjunto de elementos irreducibles forma un monoide isomorfo al monoide cociente $M / \leftrightarrow^*_R$ .
Formulación Categórica: Los sistemas se organizan dentro de un marco 2-categorial estricto. El autor define $\mathbf{NCRS}_2$ como la 2-categoría de SRM noetéricos confluentes, donde los 0-celdas son los sistemas, las 1-celdas son homomorfismos que preservan la estructura de reducción, y las 2-celdas representan equivalencias entre homomorfismos. Esta estructura se compara con la 2-categoría de los monoides, $\mathbf{Mon}$ .
Teoría de Transformaciones: Para clasificar la familia de SRM que presentan un monoide fijo, el artículo introduce las Transformaciones de Tietze Elementales Generalizadas (GETTs). Estas son cuatro tipos de operaciones (añadir/eliminar reglas, añadir nuevos generadores y colapsar subconjuntos coherentes de reglas) adaptadas al entorno del monoide arbitrario.

Contribuciones Clave y Resultados

Definición de SRM y Propiedades Fundamentales: El artículo formaliza los SRM y demuestra que las restricciones sintácticas de los monoides libres no son necesarias para los lemas centrales de la teoría de reescritura. Prueba que el cociente de un SRM por su relación de congruencia es isomorfo al monoide de sus elementos irreducibles.
Biadjunción entre $\mathbf{NCRS}_2$ y $\mathbf{Mon}$ : Un resultado central es la existencia de una biadjunción canónica entre la 2-categoría de los SRM noetéricos confluentes ( $\mathbf{NCRS}_2$ $NCRS_{2}$ ) y la 2-categoría de los monoides ( $\mathbf{Mon}$ $Mon$ ).
- El adjunto derecho $I: \mathbf{NCRS}_2 \to \mathbf{Mon}$ mapea un sistema a su monoide de irreducibles.
- El adjunto izquierdo $G: \mathbf{Mon} \to \mathbf{NCRS}_2$ construye un SRM noetérico confluente "canónico" para cualquier monoide dado $M$ , utilizando el monoide libre generado por $M \setminus \{1\}$ y codificando la multiplicación del monoide como reglas de reducción.
- Esta biadjunción establece una propiedad universal: los mapas desde una presentación canónica $G(M)$ hacia cualquier sistema $A$ corresponden unívocamente (hasta isomorfismo de 2-celda) a los homomorfismos de monoide de $M$ hacia el monoide de los irreducibles de $A$ .
Teorema de Tietze Generalizado: El artículo generaliza el Teorema de Tietze al entorno de los monoides arbitrarios. Define cuatro tipos de GETTs y demuestra que cualquier par de SRM noetéricos confluentes que presentan el mismo monoide están conectados por una secuencia (posiblemente infinita) de estas transformaciones. Específicamente, si dos sistemas presentan el mismo monoide $M$ , uno puede transformarse en el otro utilizando como máximo $|B|$ GETTs, donde $|B|$ es la cardinalidad del conjunto subyacente del sistema objetivo.

Significado
El artículo afirma que este trabajo proporciona una caracterización completa de los sistemas generadores para un monoide hasta la equivalencia de GETT, eliminando la dependencia de los monoides libres. Al cambiar el entorno de los monoides libres a monoides arbitrarios, el marco permite que los sistemas de reescritura sean tratados internamente dentro de la lógica de primer orden y la teoría de modelos, ya que la restricción de "frialdad" ya no es un prerrequisito para la definición del sistema.

Además, la organización 2-categorial de estos sistemas ofrece una perspectiva de mayor dimensión a la reescritura. Trata los sistemas generadores no meramente como presentaciones estáticas, sino como estructuras dinámicas donde las equivalencias entre sistemas pueden estudiarse utilizando herramientas categoriales. El resultado de la biadjunción clarifica específicamente la relación entre los mapas "semánticos" de monoides y los mapas "sintácticos" de sistemas de reescritura, mostrando que los segundos están determinados unívocamente por los primeros hasta la estructura inherente de 2-dimensiones de $\mathbf{NCRS}_2$ .

El trabajo también proporciona diversos ejemplos que ilustran la versatilidad de los SRM, incluyendo aplicaciones a espacios topológicos (operadores de clausura), toposes elementales (topologías de Lawvere-Tierney) y teorías de Horn en lógica, demostrando que la estructura monoidal es el componente esencial para la reescritura, más que la sintaxis específica de las palabras.