Duality theory and representations for distributive quasi relation algebras and DInFL-algebras

Sintesi Tecnica: Dualità e Rappresentazioni per le Algebre di Relazione Quasi Distributive e le Algebre DInFL

Enunciato del Problema
Il saggio affronta la teoria algebrica delle relazioni binarie, concentrandosi specificamente sulle generalizzazioni delle algebre di relazione che indeboliscono la classica negazione booleana. Mentre le algebre di relazione si basano sulla complementazione classica, gli autori investigano le algebre di relazione quasi distributive (DqRA) e le algebre di Lambek piene involutive distributive (DInFL-algebre). Queste strutture mancano di operazioni unarie individuali per la complementazione e la conversione, utilizzando invece negazioni lineari ($\sim$ e $-$) e una negazione di De Morgan ($\neg$). Le sfide centrali affrontate sono:

1. Stabilire una robusta teoria della dualità per queste algebre, in particolare per il caso completo perfetto, analogamente alle strutture atomiche utilizzate per le algebre di relazione finite.
2. Estendere questa dualità a tutte le algebre (non solo quelle complete perfette) utilizzando metodi topologici.
3. Determinare la rappresentabilità di queste algebre come reticoli di relazioni binarie, identificando specificamente quali algebre finite possono essere incorporate in algebre concrete di relazioni.

Metodologia
Gli autori impiegano un approccio multifacettato che combina logica algebrica, teoria dell'ordine e topologia:

• Costruzione dei Frame: Il saggio definisce i frame DInFL e i frame DqRA. Questi sono insiemi parzialmente ordinati dotati di un'operazione di insieme binaria (che rappresenta la composizione), un insieme identità distinto e funzioni unarie che rappresentano le negazioni lineari. Per le DqRA, viene inclusa un'operazione unaria aggiuntiva ($\neg$). Questi frame sono analoghi ai frame di Routley–Meyer nella logica della rilevanza, ma adattati per le algebre FL involutive.
• Dualità per le Algebre Complete Perfette: Utilizzando la teoria degli elementi completamente giunzioni-irriducibili ($J_\infty$) e degli elementi completamente incontri-irriducibili ($M_\infty$), gli autori costruiscono dualità tra le DInFL-algebre/DqRAs complete perfette e i loro rispettivi frame. Dimostrano che ogni algebra completa perfetta è isomorfa l'algebra complessa del suo frame di giunzioni-irriducibili, e viceversa.
• Morfismi: Il saggio definisce i morfismi per questi frame e stabilisce una dualità tra i morfismi di frame e gli omomorfismi completi delle algebre.
• Estensione della Dualità di Priestley: Per gestire le algebre che non sono necessariamente complete o perfette, gli autori estendono il framework a spazi di Priestley doppiamente puntati. Questi sono spazi topologici compatti e totalmente disconnessi nell'ordine, con limiti ($\bot, \top$). Gli spazi duali utilizzano l'insieme dei "filtri primi generalizzati" (inclusi l'insieme vuoto e l'intera algebra) per accomodare reticoli non limitati.
• Analisi della Rappresentabilità: Gli autori utilizzano una costruzione che coinvolge relazioni di equivalenza parzialmente ordinate, automorfismi d'ordine ($\alpha$) e automorfismi d'ordine duali ($\beta$) per definire rappresentazioni concrete. Analizzano la rappresentabilità delle algebre finite tramite:
  • Il calcolo del numero di algebre non isomorfe fino alla dimensione 8 con Prover9/Mace4.
  • La verifica di tali conteggi enumerando i corrispondenti frame.
  • L'indagine sui sotto-reduct DqRA di note algebre di relazione (specificamente le 37 algebre di relazione non simmetriche integrali di dimensione 16).
  • L'applicazione di teoremi noti sulla rappresentabilità finita (ad esempio, condizioni secondo cui un'algebra non può essere finitamente rappresentabile).

Contributi Chiave e Risultati

1. Dualità:

   • Il saggio fornisce una dualità completa per le algebre di relazione quasi distributive complete perfette e le algebre DInFL distributive involutive complete tramite i rispettivi frame.
   • Estende questa dualità a tutte le DInFL-algebre e DqRAs utilizzando spazi di Priestley doppiamente puntati, generalizzando efficacemente la dualità a strutture non limitate.
   • Gli autori definiscono i morfismi per questi frame e dimostrano che sono duali agli omomorfismi completi delle algebre.

2. Proprietà Strutturali:

   • Il saggio chiarisce la relazione tra le qRAs e le algebre InFL commutative, mostrando che le algebre InFL commutative sono algebre di relazione quasi.
   • Dimostra che l'identità $\neg \sim a = - \neg a$ (precedentemente un assioma esplicito in alcune definizioni) è implicata dalla definizione standard delle qRAs.
   • Stabilisce che le algebre di relazione simmetriche producono sotto-reduct che sono essi stessi algebre di relazione, implicando che le DqRAs che non sono algebre di relazione devono derivare da algebre di relazione non simmetriche.

3. Enumerazione e Classificazione:

   • Gli autori forniscono un catalogo dettagliato di DInFL-algebre e DqRAs fino alla cardinalità 6 (con conteggi fino a 8).
   • Identificano i loro frame duali, collegandoli a specifiche strutture di poset (ad esempio, $1+1+2$, $2 \times 2$, $2 \times 3$).
   • La Tabella 1 presenta tutti i frame per le algebre non triviali fino alla dimensione quattro.

4. Risultati sulla Rappresentabilità:

   • Il saggio cataloga lo stato di rappresentabilità delle algebre finite fino alla dimensione 6.
   • Identifica che molte piccole algebre (ad esempio, $D^3_{1,1}$, $D^4_{1,1}$, $D^4_{1,2}$) non hanno una rappresentazione nota. Per alcune, è dimostrato che se una rappresentazione esiste, deve essere infinita.
   • Gli autori analizzano i sotto-reduct DqRA delle 37 algebre di relazione non simmetriche di dimensione 16. Determinano che 20 di questi sotto-reduct sono rappresentabili (derivanti da algebre di relazione rappresentabili), mentre lo stato degli altri (come il sotto-reduct dell'algebra 1437 di McKenzie) rimane aperto o è mostrato come non rappresentabile come algebra di relazione indebolita.
   • Il saggio nota che la più piccola DInFL-algebra non ciclica (7 elementi) ha un frame duale con struttura di poset $\triangleright \triangleleft$, e non è attualmente nota alcuna rappresentazione per essa.

Significato e Rivendicazioni
Il saggio sostiene di fornire un quadro fondamentale per lo studio delle algebre di relazione quasi distributive e delle DInFL-algebre attraverso la dualità. Stabilendo la connessione tra queste algebre e i frame parzialmente ordinati (e le loro estensioni topologiche), gli autori offrono strumenti per:

• Procedure Decisionali: L'approccio basato sui frame facilita le procedure decisionali (ad esempio, tramite metodi a tableaux) per le teorie equazionali di queste algebre.
• Test di Rappresentabilità: La dualità permette l'indagine della rappresentabilità tramite "approcci basati su giochi" e l'analisi dei frame duali, in modo simile ai metodi usati nella teoria delle algebre di relazione.
• Classificazione: L'esteso catalogazione delle piccole algebre e del loro stato di rappresentabilità colma una lacuna nella letteratura, fornendo un riferimento concreto per la ricerca futura.

Gli autori presentano il lavoro modestamente come una versione espansa di una pubblicazione precedente [4], con le aggiunte primarie che riguardano l'inclusione della dualità di Priestley per le algebre non limitate e una discussione estesa della rappresentabilità per le algebre finite. Evidenziano l'algebra MV a tre elementi ($D^3_{1,1}$) e il sotto-reduct DqRA dell'algebra 1437 di McKenzie come problemi aperti significativi dove la rappresentazione è attualmente sconosciuta. Il saggio conclude che la ricerca di rappresentazioni per queste algebre rimane un'area di ricerca attiva e stimolante.