On the structure and theory of McCarthy algebras

Resumo Técnico: Sobre a Estrutura e a Teoria das Álgebras de McCarthy

Enunciado do Problema
As álgebras de McCarthy constituem o contraparte algébrica da lógica de McCarthy, uma lógica trivalente baseada na conjunção não comutativa usada para modelar a avaliação preguiçosa (lazy evaluation) de predicados parciais em ciência da computação (por exemplo, em Haskell, OCaml, Java e Python). Embora a utilidade da lógica de McCarthy em álgebras de processos para modelar tratamento de erros e guardas condicionais esteja estabelecida, sua estrutura algébrica permaneceu pouco explorada. Especificamente, embora Guzmán e Squier [13] tenham fornecido uma base finita para o reduto livre de constantes (Álgebras Condicionais ou C-álgebras), e Konikowska [18] tenha proposto uma lista de identidades para a álgebra de três elementos $M_3$, faltava uma análise estrutural abrangente e uma base equacional reduzida para a variedade completa das álgebras de McCarthy (incluindo constantes). Além disso, a relação entre as álgebras de McCarthy e outras lógicas não clássicas (como as lógicas de Kleene e as álgebras de Boolean) dentro de um arcabouço algébrico unificado carecia de esclarecimento.

Metodologia
Os autores introduzem um arcabouço algébrico geral chamado i-ubands (bandas unitais com involução). Um i-uband é definido como um monoide idempotente $\langle M, \cdot, e \rangle$ equipado com uma operação unária involutiva $'$ satisfazendo $x'' \approx x$. Esta estrutura serve como um terreno comum para várias lógicas não clássicas, incluindo álgebras de Boolean, ortolattices, álgebras de De Morgan e álgebras de Kleene.

A metodologia procede da seguinte forma:

1. Definição e Classificação: Os autores analisam a variedade de i-ubands, focando especificamente nos i-ubands subclássicos (aqueles que contêm a álgebra de Boolean de dois elementos como uma subálgebra). Eles classificam todos os i-ubands de 3 elementos não isomorfos, identificando quatro modelos subclássicos: a álgebra de Kleene fraca ($WK$), a álgebra de Kleene forte ($SK$), a álgebra de McCarthy ($M_3$) e seu espelho $M_3^{op}$.
2. Análise de Identidades: O artigo investiga as identidades satisfeitas por $M_3$ no contexto de i-ubands. Isso envolve a derivação de leis distributivas fracas (distributividade à esquerda, ortodistributividade) e leis de absorção fracas e leis comutativas fracas (comutatividade de unidade local).
3. Axiomatização: Ao analisar a interação dessas identidades, os autores derivam bases equacionais reduzidas e equivalentes para a variedade de álgebras de McCarthy.
4. Decomposição Estrutural: Os autores utilizam a ordem parcial induzida pela operação de adição ($+$) para decompor as álgebras de McCarthy. Eles definem um "esqueleto de semilattice" e "fibras" para estabelecer um teorema de decomposição de semilattice.
5. Representação: A estrutura algébrica é caracterizada via posets decorados com sℓ (conjuntos parcialmente ordenados decorados com um esqueleto de semilattice), demonstrando que as operações são unicamente determinadas pela ordem e pela membresia no esqueleto.

Principais Contribuições e Resultados

• Arcabouço Unificado (i-ubands): O artigo estabelece os i-ubands como um cenário geral para o estudo de versões não comutativas de lógicas clássicas e não clássicas. Ele esclarece a distinção entre i-ubands e semigrupos de banda com involução, observando que i-ubands apenas requerem $x'' \approx x$ em vez da mais forte condição $(xy)' \approx y'x'$.
• Axiomatização Reduzida: Os autores fornecem uma base equacional finita para a variedade $\mathcal{M}$ das álgebras de McCarthy. Eles provam que $\mathcal{M}$ coincide com a variedade de álgebras MK (álgebras de McCarthy-Konikowska). A base é apresentada em termos de três componentes:
  1. Distributividade Fraca: Pelo menos uma de: distributividade à esquerda com decomposição à esquerda, divisibilidade à esquerda com ortodistributividade à direita, ou paradistributividade à direita.
  2. Absorção Fraca: Pelo menos uma de: limitação à esquerda ou absorção à esquerda.
  3. Comutatividade Fraca: Pelo menos uma de: comutatividade de unidade local, comutatividade local ou comutatividade wk.
     Este resultado confirma que os postulados de Konikowska formam uma base equacional e fornece formulações alternativas e reduzidas.
• Membros Subdiretamente Irredutíveis: O artigo prova que as únicas álgebras de McCarthy subdiretamente irredutíveis são a álgebra de Boolean de dois elementos ($2$) e a álgebra de McCarthy de três elementos ($M_3$). Consequentemente, a variedade $\mathcal{M}$ é gerada por $M_3$.
• Decomposição de Semilattice: Um resultado central é o Teorema de Decomposição de Semilattice (Teorema 6.1). Toda álgebra de McCarthy $A$ se decompõe em um sistema direto de semilattice de álgebras de Boolean $\langle I_A, \mathcal{B}_A, \mathcal{P}_A \rangle$, onde:
  • $I_A$ é o esqueleto de semilattice de $A$ (isomorfo ao conjunto de unidades locais $\{x \cdot 0 \mid x \in A\}$).
  • $\mathcal{B}_A$ é o conjunto de fibras (intervalos $[0_i, 1_i]$), cada uma das quais é uma álgebra de Boolean.
  • $\mathcal{P}_A$ consiste de homomorfismos entre as fibras induzidos pela ordem.
    Ao contrário das somas de semilattice padrão (ex: semigrupos de Clifford), esta decomposição não é geralmente um quociente da álgebra, distinguindo-se dos teoremas clássicos de decomposição de semilattice.
• Representação como Posets Decorados: Os autores mostram que as álgebras de McCarthy são totalmente determinadas por seus posets decorados com sℓ. As operações (multiplicação, involução) podem ser expressas usando a ordem, supremos/ínfimos existentes e um predicado unário identificando o esqueleto de semilattice. Isso leva a uma caracterização de isomorfismo: dois McCarthy algebras são isomorfos se, e somente se, seus posets decorados com sℓ forem isomorfos.
• Lattice de Subvariedades: O artigo esboça os níveis inferiores do lattice de subvariedades de i-ubands. Ele identifica que as álgebras de McCarthy formam uma variedade subclássica (onde a unidade não é um ponto fixo de involução) e que $\mathcal{M}$ cobre a variedade das álgebras de Boolean ($BA$) neste lattice. Também identifica problemas abertos relativos à axiomatização finita das variedades geradas pelo reduto do monoide de Sugihara ($C_3^s$) e suas variantes à esquerda/direita ($L_3^s, R_3^s$).

Significância
O artigo fornece a primeira análise estrutural abrangente das álgebras de McCarthy, indo além da identificação de sua base equacional para um entendimento profundo de sua arquitetura interna. Ao introduzir os i-ubands, os autores unificam o estudo da lógica de McCarthy com outras lógicas não clássicas, revelando a lógica de McCarthy como a companheira não comutativa das lógicas de Kleene e de Boolean. O teorema de decomposição e a representação via posets decorados oferecem novas ferramentas para analisar essas álgebras, potencialmente facilitando novas pesquisas em sua teoria de modelos e aplicações em ciência da computação, particularmente na verificação formal de processos envolvendo tratamento de erros e avaliação preguiçosa. O trabalho também esclarece a posição precisa das álgebras de McCarthy dentro do panorama mais amplo da lógica algébrica, especificamente sua relação com as álgebras de Boolean e o lattice de subvariedades de i-ubands.