On the structure and theory of McCarthy algebras

Resumen Técnico: Sobre la Estructura y la Teoría de las Álgebras de McCarthy

Planteamiento del Problema
Las álgebras de McCarthy constituyen el contraparte algebraica de la lógica de McCarthy, una lógica de tres valores basada en la conjunción no conmutativa utilizada para modelar la evaluación perezosa (lazy evaluation) de predicados parciales en la informática (por ejemplo, en Haskell, OCaml, Java y Python). Si bien la utilidad de la lógica de McCarthy en los álgebras de procesos para modelar el manejo de errores y las guardas condicionales está establecida, su estructura algebraica ha permanecido poco explorada. Específicamente, aunque Guzmán y Squier [13] proporcionaron una base finita para el reducto libre de constantes (Álgebras Condicionales o álgebras C), y Konikowska [18] propuso una lista de identidades para el álgebra de tres elementos $M_3$, faltaba un análisis estructural exhaustivo y una base ecuacional reducida para la variedad completa de las álgebras de McCarthy (incluyendo constantes). Además, se requería clarificar la relación entre las álgebras de McCarthy y otras lógicas no clásicas (como las lógicas de Kleene y las álgebras booleanas) dentro de un marco algebraico unificado.

Metodología
Los autores introducen un marco algebraico general llamado i-ubands (bandas con involución unitarias). Un i-uband se define como un monoide idempotente $\langle M, \cdot, e \rangle$ equipado con una operación unaria involutiva $'$ que satisface $x'' \approx x$. Esta estructura sirve como terreno común para diversas lógicas no clásicas, incluyendo álgebras booleanas, ortolátiaces, álgebras de De Morgan y álgebras de Kleene.

La metodología procede de la siguiente manera:

1. Definición y Clasificación: Los autores analizan la variedad de los i-ubands, centrándose específicamente en los i-ubands subclásicos (aquellos que contienen el álgebra booleana de dos elementos como subálgebra). Clasifican todos los i-ubands de tres elementos no isomorfos, identificando cuatro modelos subclásicos: el álgebra de Kleene débil ($WK$), el álgebra de Kleene fuerte ($SK$), el álgebra de McCarthy ($M_3$) y su espejo $M_3^{op}$.
2. Análisis de Identidades: El artículo investiga las identidades satisfechas por $M_3$ dentro del contexto de los i-ubands. Esto implica derivar leyes de distributividad débil (distributividad izquierda, ortodistributividad), leyes de absorción débil y leyes de conmutatividad débil (conmutatividad de la unidad local).
3. Axiomatización: Mediante el análisis de la interacción de estas identidades, los autores derivan bases ecuacionales reducidas y equivalentes para la variedad de las álgebras de McCarthy.
4. Descomposición Estructural: Los autores utilizan el orden parcial inducido por la operación de adición ($+$) para descomponer las álgebras de McCarthy. Definen un "esqueleto de semilattice" y "fibras" para establecer un teorema de descomposición de semilattice.
5. Representación: La estructura algebraica se caracteriza mediante posets decorados con sℓ (conjuntos parcialmente ordenados decorados con un esqueleto de semilattice), demostrando que las operaciones están determinadas únicamente por el orden y la pertenencia al esqueleto.

Contribuciones Clave y Resultados

• Marco Unificado (i-ubands): El artículo establece a los i-ubands como un entorno general para estudiar versiones no conmutativas de lógicas clásicas y no clásicas. Clarifica la distincción entre los i-ubands y los semigrupos de bandas con involución, señalando que los i-ubands solo requieren $x'' \approx x$ en lugar de la condición más fuerte $(xy)' \approx y'x'$.
• Axiomatización Reducida: Los autores proporcionan una base ecuacional finita para la variedad $\mathcal{M}$ de las álgebras de McCarthy. Demuestran que $\mathcal{M}$ coincide con la variedad de álgebras MK (álgebras de McCarthy-Konikowska). La base se presenta en términos de tres componentes:
  1. Distributividad Débil: Al menos una de la distributividad izquierda con descomposición izquierda, divisibilidad izquierda con ortodistributividad derecha, o paradistributividad derecha.
  2. Absorción Débil: Al menos una de la acotación izquierda o la absorción izquierda.
  3. Conmutatividad Débil: Al menos una de la conmutatividad de la unidad local, la conmutatividad local o la conmutatividad wk.
     Este resultado confirma que los postulados de Konikowska forman una base ecuacional y proporciona formulaciones alternativas y reducidas.
• Miembros Subdirectamente Irreducibles: El artículo demuestra que los únicos álgebras de McCarthy subdirectamente irreducibles son el álgebra booleana de dos elementos ($2$) y el álgebra de McCarthy de tres elementos ($M_3$). En consecuencia, la variedad $\mathcal{M}$ es generada por $M_3$.
• Descomposición de Semilattice: Un resultado central es el Teorema de Descomposición de Semilattice (Teorema 6.1). Cada álgebra de McCarthy $A$ se descompone en un sistema directo de semilattice de álgebras booleanas $\langle I_A, \mathcal{B}_A, \mathcal{P}_A \rangle$, donde:
  • $I_A$ es el esqueleto de semilattice de $A$ (isomorfo al conjunto de unidades locales $\{x \cdot 0 \mid x \in A\}$).
  • $\mathcal{B}_A$ es el conjunto de fibras (intervalos $[0_i, 1_i]$), cada una de las cuales es un álgebra booleana.
  • $\mathcal{P}_A$ consiste en homomorfismos entre fibras inducidos por el orden.
    A diferencia de las sumas de semilattice estándar (por ejemplo, semigrupos de Clifford), esta descomposición no es generalmente un cociente del álgebra, lo que la distingue de los teoremas clásicos de descomposición de semilattice.
• Representación como Posets Decorados: Los autores muestran que las álgebras de McCarthy están plenamente determinadas por sus posets decorados con sℓ. Las operaciones (multiplicación, involución) pueden expresarse utilizando el orden, los ínfimos/supremos existentes y un predicado unario que identifica el esqueleto de semilattice. Esto conduce a una caracterización de isomorfismo: dos álgebras de McCarthy son isomorfas si y solo si sus posets decorados con sℓ son isomorfos.
• Lattice de Subvariedades: El artículo esboza los niveles inferiores del lattice de subvariedades de los i-ubands. Identifica que las álgebras de McCarthy forman una variedad subclásica (donde la unidad no es un punto fijo de la involución) y que $\mathcal{M}$ cubre la variedad de los álgebras booleanas ($BA$) en este lattice. También identifica problemas abiertos respecto a la axiomatización finita de las variedades generadas por el reducto del monoide de Sugihara ($C_3^s$) y sus variantes izquierda/derecha ($L_3^s, R_3^s$).

Significancia
El artículo proporciona el primer análisis estructural exhaustivo de las álgebras de McCarthy, yendo más allá de la identificación de su base ecuacional hacia una comprensión profunda de su arquitectura interna. Al introducir los i-ubands, los autores unifican el estudio de la lógica de McCarthy con otras lógicas no clásicas, revelando la lógica de McCarthy como la compañera no conmutativa de las lógicas de Kleene y booleanas. El teorema de descomposición y la representación mediante posets decorados ofrecen nuevas herramientas para analizar estas álgebras, facilitando potencialmente futuras investigaciones en su teoría de modelos y aplicaciones en la informática, particularmente en la verificación formal de procesos que involucran el manejo de errores y la evaluación perezosa. El trabajo también clarifica la posición precisa de las álgebras de McCarthy dentro del panorama más amplio de la lógica algebraica, específicamente su relación con las álgebras booleanas y el lattice de subvariedades de los i-ubands.