💻 computer science

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

This paper establishes dualities for complete perfect distributive quasi relation algebras and DInFL-algebras using partially ordered frames, extends these results to all algebras via doubly-pointed frames with Priestley topology, and investigates their representability as lattices of binary relations, including a detailed analysis of algebras up to size six.

Original authors: Andrew Craig, Peter Jipsen, Claudette Robinson

Published 2026-01-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew Craig, Peter Jipsen, Claudette Robinson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand the rules of a complex board game. In this game, the pieces aren't just chessmen or cards; they are relationships between things. For example, "Alice is taller than Bob," or "The server is connected to the database."

For a long time, mathematicians and computer scientists have studied these relationships using a very strict set of rules called Relation Algebras. Think of these rules as a rigid, perfect crystal: they are beautiful and powerful, but they only work if the world behaves in a very specific, classical way (like having a clear "yes" or "no" answer to everything).

However, the real world (and modern computer programs) is often messier. Sometimes we don't have a clear "yes" or "no," or the rules of "flipping" a relationship (like turning "taller than" into "shorter than") don't work exactly the same way. This paper introduces a more flexible, "squishier" version of these rules called Distributive Quasi Relation Algebras (DqRAs).

Here is a breakdown of what the authors, Andrew Craig, Peter Jipsen, and Claudette Robinson, did to make sense of these flexible rules:

1. The Map and the Territory (Duality)

The core of the paper is about Duality. Imagine you have a complex 3D sculpture (the algebra). It's hard to study the sculpture directly because it's solid and opaque.

The authors invented a new way to look at it: they created a shadow map (called a "frame").

The Algebra (The Sculpture): This is the abstract math where you do operations like combining relationships.
The Frame (The Map): This is a simpler structure made of dots (points) and arrows (connections) between them.

The paper proves that for every complex algebra, there is a perfect "shadow map" that contains all the same information. If you understand the map, you automatically understand the sculpture. This is huge because maps are often easier to draw, count, and analyze than the abstract sculptures.

2. The "Double-Pointed" Priestley Spaces

To handle the messier, non-classical rules, the authors had to upgrade their maps. They used a special kind of map called a Priestley space.

Think of a standard map as a flat piece of paper. But these new maps are like holographic 3D models that have a "top" and a "bottom" (like a ceiling and a floor) and are wrapped in a special kind of fabric (topology) that keeps everything connected.

They call these "doubly-pointed" spaces because they have two special anchor points (top and bottom) that help hold the structure together, even when the rules get weird.
This allows them to study algebras that don't have a "top" or "bottom" in the traditional sense, which is common in computer science logic.

3. The "Translation" Dictionary (Morphisms)

The paper also defines how to translate between these maps. If you have a map of a small town and a map of a big city, how do you see how they relate?

The authors created a set of rules (morphisms) that act like a dictionary.
If you change the map (the frame) in a specific way, the dictionary tells you exactly how the abstract algebra changes in response. This ensures that the two worlds (the map and the sculpture) always stay in sync.

4. The "Can It Be Built?" Test (Representability)

A major question in this field is: "Can this abstract rule set actually be built using real-world relationships?"

Some algebras are like blueprints for a house that can actually be constructed.
Others are blueprints for a house that defies physics (e.g., a room that is both inside and outside at the same time).

The authors went through a massive catalog of these algebras, specifically looking at the small ones (up to size 6, and counting up to size 8).

They acted like architects checking blueprints. They asked: "Does this specific set of rules correspond to a real arrangement of binary relationships?"
They found that many small algebras can be built (they are "representable").
However, they hit a wall with some specific, tricky algebras (like the 3-element one named D3 1,1). For these, they don't know if a real-world construction exists yet. If it does exist, the paper suggests it would have to be an infinite construction, not a small, finite one.

5. The "Atom" Catalog

Finally, the paper includes a massive inventory list (Tables 1 through 5).

Imagine a periodic table of elements, but instead of atoms like Hydrogen or Oxygen, it lists every possible "shape" of these small relationship algebras.
They counted how many exist for sizes 1 through 8.
They checked which ones are "symmetric" (where the rules work the same forwards and backwards) and which are "nonsymmetric" (where direction matters).
They identified which of these shapes can be found inside the "big" relation algebras (the rigid crystal ones) and which ones are unique to this new, flexible system.

Summary

In short, this paper builds a bridge between two worlds:

The abstract, hard-to-visualize world of flexible logic rules (DqRAs).
The concrete, visual world of dots and arrows (Frames).

They created a dictionary to translate between them, proved the translation is perfect, and then used this system to check a huge list of small algebras to see which ones can be "built" in the real world and which ones remain mysterious puzzles. This helps computer scientists and logicians understand the limits of how we can model complex systems like software or networks.

Technical Summary: Duality and Representations for Distributive Quasi Relation Algebras and DInFL-Algebras

Problem Statement
The paper addresses the algebraic theory of binary relations, specifically focusing on generalizations of relation algebras that weaken classical Boolean negation. While relation algebras rely on classical complementation, the authors investigate distributive quasi relation algebras (DqRAs) and distributive involutive full Lambek algebras (DInFL-algebras). These structures lack individual unary operations for complementation and converse, instead utilizing linear negations ( $\sim$ and $-$) and a De Morgan negation ( $\neg$ ). The central challenges addressed are:

Establishing a robust duality theory for these algebras, particularly for the complete perfect case, analogous to the atom structures used for finite relation algebras.
Extending this duality to all algebras (not just complete perfect ones) using topological methods.
Determining the representability of these algebras as lattices of binary relations, specifically identifying which finite algebras can be embedded into concrete algebras of relations.

Methodology
The authors employ a multi-faceted approach combining algebraic logic, order theory, and topology:

Frame Construction: The paper defines DInFL-frames and DqRA-frames. These are partially ordered sets equipped with a binary set-operation (representing composition), a distinguished identity set, and unary functions representing linear negations. For DqRAs, an additional unary operation ( $\neg$ ) is included. These frames are analogous to Routley–Meyer frames in relevance logic but adapted for involutive FL-algebras.
Duality for Complete Perfect Algebras: Using the theory of completely join-irreducible elements ( $J_\infty$ ) and completely meet-irreducible elements ( $M_\infty$ ), the authors construct dualities between complete perfect DInFL-algebras/DqRAs and their corresponding frames. They prove that every complete perfect algebra is isomorphic to the complex algebra of its frame of join-irreducibles, and vice versa.
Morphisms: The paper defines morphisms for these frames and establishes a duality between frame morphisms and complete homomorphisms of the algebras.
Priestley Duality Extension: To handle algebras that are not necessarily complete or perfect, the authors extend the framework to doubly-pointed Priestley spaces. These are compact, totally order-disconnected topological spaces with bounds ( $\bot, \top$ ). The dual spaces utilize the set of "generalised prime filters" (including the empty set and the whole algebra) to accommodate unbounded lattices.
Representability Analysis: The authors utilize a construction involving partially ordered equivalence relations, order automorphisms ( $\alpha$ $α$ ), and dual order automorphisms ( $\beta$ $β$ ) to define concrete representations. They analyze the representability of finite algebras by:
- Calculating the number of non-isomorphic algebras up to size 8 using Prover9/Mace4.
- Verifying these counts by enumerating corresponding frames.
- Investigating DqRA-subreducts of known finite relation algebras (specifically the 37 nonsymmetric integral relation algebras of size 16).
- Applying known theorems regarding finite representability (e.g., conditions under which an algebra cannot be finitely representable).

Key Contributions and Results

Dualities:
- The paper provides a complete duality for complete perfect distributive quasi relation algebras and complete perfect distributive involutive FL-algebras via their respective frames.
- It extends this duality to all DInFL-algebras and DqRAs using doubly-pointed Priestley spaces, effectively generalizing the duality to unbounded structures.
- The authors define morphisms for these frames and prove they are dual to complete homomorphisms of the algebras.
Structural Properties:
- The paper clarifies the relationship between qRAs and commutative InFL-algebras, showing that commutative InFL-algebras are quasi relation algebras.
- It proves that the identity $\neg \sim a = - \neg a$ (previously an explicit axiom in some definitions) is implied by the standard definition of qRAs.
- It establishes that symmetric relation algebras yield subreducts that are themselves relation algebras, implying that non-relation-algebra DqRAs must arise from nonsymmetric relation algebras.
Enumeration and Classification:
- The authors provide a detailed catalog of DInFL-algebras and DqRAs up to cardinality 6 (with counts up to 8).
- They identify the dual frames for these algebras, linking them to specific poset structures (e.g., $1+1+2$ , $2 \times 2$ , $2 \times 3$ ).
- Table 1 presents all frames for nontrivial algebras up to size four.
Representability Findings:
- The paper catalogs the representability status of finite algebras up to size 6.
- It identifies that many small algebras (e.g., $D^3_{1,1}$ , $D^4_{1,1}$ , $D^4_{1,2}$ ) have no known representation. For some, it is proven that if a representation exists, it must be infinite.
- The authors analyze the DqRA-subreducts of the 37 nonsymmetric relation algebras of size 16. They determine that 20 of these subreducts are representable (arising from representable relation algebras), while the status of others (such as the subreduct of McKenzie's non-representable algebra 1437) remains open or is shown to be non-representable as a weakening relation algebra.
- The paper notes that the smallest non-cyclic DInFL-algebra (7 elements) has a dual frame with poset structure $\triangleright \triangleleft$ , and no representation is currently known for it.

Significance and Claims
The paper claims to provide a foundational framework for studying distributive quasi relation algebras and DInFL-algebras through duality. By establishing the connection between these algebras and partially ordered frames (and their topological extensions), the authors offer tools for:

Decision Procedures: The frame-based approach facilitates decision procedures (e.g., via tableaux methods) for the equational theories of these algebras.
Representability Testing: The duality allows for the investigation of representability via "game-based approaches" and the analysis of dual frames, similar to methods used in relation algebra.
Classification: The extensive cataloging of small algebras and their representability status fills a gap in the literature, providing a concrete reference for future research.

The authors modestly frame the work as an expanded version of a previous publication [4], with the primary additions being the inclusion of Priestley duality for unbounded algebras and an extensive discussion of representability for finite algebras. They highlight the three-element MV-algebra ( $D^3_{1,1}$ ) and the DqRA-subreduct of McKenzie's algebra 1437 as significant open problems where representation is currently unknown. The paper concludes that the search for representations of these algebras remains an active and appealing area of research.