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

Technische Samenvatting: Dualiteit en Representaties voor Distributieve Quasi-Relatiealgebra's en DInFL-Algebra's

Probleemstelling
Het artikel behandelt de algebraïsche theorie van binaire relaties, met een specifieke focus op generalisaties van relatiealgebra's die de klassieke Booleaanse negatie verzwakken. Terwijl relatiealgebra's steunen op klassieke complementatie, onderzoeken de auteurs distributieve quasi-relatiealgebra's (DqRAs) en distributieve involutieve volledige Lambek-algebra's (DInFL-algebra's). Deze structuren missen individuele unaire operaties voor complementatie en inversie, en maken in plaats daarvan gebruik van lineaire negaties ($\sim$ en $-$) en een De Morgan-negatie ($\neg$). De centrale uitdagingen die worden aangepakt zijn:

1. Het vestigen van een robuuste dualiteitstheorie voor deze algebra's, in het bijzonder voor de volledige perfecte casus, analoog aan de atoomstructuren die gebruikt worden voor eindige relatiealgebra's.
2. Het uitbreiden van deze dualiteit naar alle algebra's (niet alleen de volledige perfecte) met behulp van topologische methoden.
3. Het bepalen van de representeerbaarheid van deze algebra's als rooster van binaire relaties, specifiek door te identificeren welke eindige algebra's kunnen worden ingebed in concrete algebra's van relaties.

Methodologie
De auteurs hanteren een veelzijdige aanpak waarbij algebraïsche logica, ordenleer en topologie worden gecombineerd:

• Frame-constructie: Het artikel definieert DInFL-frames en DqRA-frames. Dit zijn partiële geordende verzamelingen uitgerust met een binaire verzameling-operatie (die compositie representeert), een onderscheidende identiteitsverzameling en unaire functies die lineaire negaties representeren. Voor DqRAs wordt een aanvullende unaire operatie ($\neg$) toegevoegd. Deze frames zijn analoog aan Routley–Meyer frames in relevantie-logica, maar aangepast voor involutieve FL-algebra's.
• Dualiteit voor Volledige Perfecte Algebra's: Met behulp van de theorie van volledig join-irreducibele elementen ($J_\infty$) en volledig meet-irreducibele elementen ($M_\infty$), construeren de auteurs dualiteiten tussen volledige perfecte DInFL-algebra's/DqRAs en hun respectieve frames. Ze bewijzen dat elke volledige perfecte algebra isomorf is aan de complexe algebra van het frame van zijn join-irreducibele elementen, en vice versa.
• Morfismen: Het artikel definieert morfismen voor deze frames en stelt een dualiteit vast tussen frame-morfismen en volledige homomorfismen van de algebra's.
• Priestley-dualiteit Uitbreiding: Om algebra's te behandelen die niet noodzakelijkerwijs volledig of perfect zijn, breiden de auteurs het kader uit naar dubbel-gepunten Priestley-ruimtes. Dit zijn compacte, totaal orde-gedisconnecteerde topologische ruimtes met grenzen ($\bot, \top$). De duale ruimtes maken gebruik van de verzameling "gegeneraliseerde priemfilters" (inclusief de lege verzameling en de gehele algebra) om onbegrensde roosterstructuren te accommoderen.
• Representeerbaarheidsanalyse: De auteurs maken gebruik van een constructie die bestaat uit gedeeltelijk geordende equivalentie-relaties, orde-automorfismen ($\alpha$) en duale orde-automorfismen ($\beta$) om concrete representaties te definiitseren. Ze analyseren de representeerbaarheid van eindige algebra's door:
  • Het aantal niet-isomorfe algebra's tot grootte 8 te berekenen met Prover9/Mace4.
  • Deze tellingen te verifiëren door de bijbehorende frames te enumereren.
  • De DqRA-subreducten van bekende eindige relatiealgebra's (specifiek de 37 niet-symmetrische integrale relatiealgebra's van grootte 16) te onderzoeken.
  • Bekende stellingen over eindige representeerbaarheid toe te passen (bijv. voorwaarden waaronder een algebra niet eindig representeerbaar kan zijn).

Belangrijkste Bijdragen en Resultaten

1. Dualiteiten:

   • Het artikel biedt een volledige dualiteit voor volledige perfecte distributieve quasi-relatiealgebra's en volledige perfecte distributieve involutieve FL-algebra's via hun respectieve frames.
   • Het breidt deze dualiteit uit naar alle DInFL-algebra's en DqRAs met behulp van dubbel-gepunten Priestley-ruimtes, wat effectief de dualiteit generaliseert naar onbegrensde structuren.
   • De auteurs definiëren morfismen voor deze frames en bewijzen dat deze duaal zijn aan volledige homomorfismen van de algebra's.

2. Structurele Eigenschappen:

   • Het artikel verheldert de relatie tussen qRA's en commutatieve InFL-algebra's, waarbij wordt aangetoond dat commutatieve InFL-algebra's quasi-relatiealgebra's zijn.
   • Het bewijst dat de identiteit $\neg \sim a = - \neg a$ (voorheen een expliciet axioma in sommige definities) wordt geïmpliceerd door de standaarddefinitie van qRA's.
   • Het stelt vast dat symmetrische relatiealgebra's subreducten opleveren die zelf relatiealgebra's zijn, wat impliceert dat niet-relatiealgebra DqRA's voort moeten komen uit niet-symmetrische relatiealgebra's.

3. Enumeratie en Classificatie:

   • De auteurs bieden een gedetailleerde catalogus van DInFL-algebra's en DqRAs tot cardinaliteit 6 (met tellingen tot 8).
   • Ze identificeren de duale frames voor deze algebra's, waarbij ze de link leggen met specifieke poset-structuren (bijv. $1+1+2$, $2 \times 2$, $2 \times 3$).
   • Tabel 1 presenteert alle frames voor niet-triviale algebra's tot grootte vier.

4. Bevindingen over Representeerbaarheid:

   • Het artikel catalogiseert de representeerbaarheidsstatus van eindige algebra's tot grootte 6.
   • Het identificeert dat veel kleine algebra's (bijv. $D^3_{1,1}$, $D^4_{1,1}$, $D^4_{1,2}$) geen bekende representatie hebben. Voor sommige is bewezen dat indien een representatie bestaat, deze oneindig moet zijn.
   • De auteurs analyseren de DqRA-subreducten van de 37 niet-symmetrische relatiealgebra's van grootte 16. Ze bepalen dat 20 van deze subreducten representeerbaar zijn (voortkomend uit representeerbare relatiealgebra's), terwijl de status van anderen (zoals de subreduct van McKenzie's niet-representeerbare algebra 1437) open blijft of wordt aangetoond als niet-representeerbaar als een verzwakte relatiealgebra.
   • Het artikel merkt op dat de kleinste niet-cyclische DInFL-algebra (7 elementen) een dual frame heeft met de poset-structuur $\triangleright \triangleleft$, en dat er momenteel geen representatie bekend is voor deze algebra.

Betekenis en Claims
Het artikel claimt een fundamenteel kader te bieden voor het bestuderen van distributieve quasi-relatiealgebra's en DInFL-algebra's via dualiteit. Door de verbinding tussen deze algebra's en gedeeltelijk geordende frames (en hun topologische uitbreidingen) te vestigen, bieden de auteurs instrumenten voor:

• Beslissingsprocedures: De frame-gebaseerde aanpak vergemakkelijkt beslissingsprocedures (bijv. via tableaux-methoden) voor de equatoriale theorieën van deze algebra's.
• Representeerbaarheids-testen: De dualiteit maakt het mogelijk om representeerbaarheid te onderzoeken via "game-gebaseerde benaderingen" en de analyse van duale frames, vergelijkbaar met methoden gebruikt in relatiealgebra.
• Classificatie: De uitgebreide catalogisering van kleine algebra's en hun representeerbaarheidsstatus vult een gat in de literatuur en dient als een concreet referentiekader voor toekomstig onderzoek.

De auteurs presenteren hun werk bescheiden als een uitgebreide versie van een eerdere publicatie [4], waarbij de primaire toevoegingen de inclusie van Priestley-dualiteit voor onbegrensde algebra's en een uitgebreide discussie over de representeerbaarheid van eindige algebra's zijn. Zij benadrukken de drie-elementen MV-algebra ($D^3_{1,1}$) en de DqRA-subreduct van McKenzie's algebra 1437 als significante openstaande problemen waar de representatie momenteel onbekend is. Het artikel concludeert dat de zoektocht naar representaties van deze algebra's een actief en aantrekkelijk onderzoeksgebied blijft.