🔢 mathematics

Rough sets by reflexive relations and their algebras

This paper investigates the algebraic structures of the completion of rough sets induced by reflexive relations, deriving specific conditions under which these structures form regular pseudocomplemented Kleene algebras, completely distributive double Stone algebras, or regular double Stone algebras equivalent to those generated by equivalence relations.

Original authors: Jouni Järvinen, Sándor Radeleczki

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jouni Järvinen, Sándor Radeleczki

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 sort a messy pile of objects. In the perfect world of mathematics, you have a perfect rulebook (an equivalence relation) that tells you exactly which items are identical twins. If you know one, you know the other. This makes sorting easy and creates a very neat, predictable structure.

But the real world is messier. Sometimes, things are similar but not identical. Sometimes, "A is like B" doesn't mean "B is like A." Maybe a portrait looks like a person, but the person doesn't look like the portrait. Maybe a son resembles his father, but the father doesn't necessarily resemble the son in the same way.

This paper explores what happens to our "sorting rules" when we move from perfect twins to these messy, one-way similarities. The authors, Jouni Järvinen and Sándor Radeleczki, are mathematicians who study Rough Sets. Think of Rough Sets as a way to handle uncertainty. Instead of saying "This item is definitely in the box," you say, "This item is probably in the box" (Upper Approximation) or "This item is definitely in the box" (Lower Approximation).

Here is the story of their discovery, broken down into simple concepts:

1. The Problem: The Messy Pile

When the similarity rule is perfect (symmetric and transitive), the collection of all possible "rough sets" forms a beautiful, orderly structure called a Lattice. It's like a perfectly organized bookshelf where every book has a specific place, and you can always find the "opposite" of any book.

However, when the similarity rule is just reflexive (everything is similar to itself) but not symmetric or transitive, the bookshelf starts to collapse. The structure might not even be a proper lattice anymore; it might be a jumbled pile where you can't find a clear "top" or "bottom" for some items.

2. The Solution: The "Dedekind–MacNeille" Safety Net

To fix the jumbled pile, the authors use a mathematical tool called the Dedekind–MacNeille completion.

The Analogy: Imagine your messy pile of rough sets is a broken bridge. You can't walk across it safely. The "completion" is like pouring concrete over the gaps to build a solid, continuous bridge. It fills in the missing pieces so the structure becomes a complete, sturdy lattice again.
They call this new, solid structure DM(RS).

3. The Discovery: New Types of Orderly Structures

The authors asked: "Under what conditions does this new, solid bridge (DM(RS)) have special, beautiful properties?" They found that for certain types of messy relationships, the bridge doesn't just become solid; it becomes a specific kind of beautiful structure known in algebra as a Regular Double Stone Algebra.

Think of these algebraic structures as different "architectural styles" for the bridge:

Kleene Algebra: A structure where you can handle "maybe" logic (like "It might be raining, or it might not").
Stone Algebra: A structure where the "maybe" zones are very well-behaved and predictable.
Double Stone Algebra: A structure that is predictable in two directions at once (forward and backward).

4. The "Clinker Equivalence": The New Hero

The most exciting part of the paper is the discovery of a new type of relationship they call a Clinker Equivalence.

The Metaphor: The name comes from "clinker-built" Viking ships. In this method, the wooden planks of the ship overlap each other like shingles on a roof. They aren't perfectly flush (like an equivalence relation), but they overlap just enough to make the ship watertight and strong.
The Math: A "Clinker Equivalence" is a relationship where the "neighborhoods" of objects (the sets of things they are similar to) overlap in a very specific, non-redundant way.
The Result: If your similarity rule is a "Clinker Equivalence," the messy bridge (DM(RS)) transforms into a Regular Double Stone Algebra. This is a structure that is almost as perfect and predictable as the old "Equivalence Relation" world, but it handles the messy, one-way similarities of the real world much better.

5. Why Does This Matter?

In the real world, data is rarely perfect.

Medical Diagnosis: A symptom might suggest a disease, but the disease doesn't always show that symptom.
Recommendation Engines: If you like Movie A, you might like Movie B, but liking Movie B doesn't mean you'll like Movie A.
Social Networks: You might trust your friend, but they might not trust you back.

This paper gives mathematicians and computer scientists a new toolkit. It tells them: "If your data has this specific 'overlap' pattern (Clinker Equivalence), you can use powerful, predictable mathematical laws to analyze it, even though the data isn't perfectly symmetrical."

Summary

The authors took a messy, one-way similarity rule, built a safety net over it to make it a complete structure, and discovered that if the overlaps are just right (like the planks on a Viking ship), the result is a mathematically beautiful and highly predictable system. They named this special pattern Clinker Equivalence, offering a new way to model the imperfect, directional similarities of our real world.

1. Problem Statement

Rough set theory, originally introduced by Z. Pawlak, relies on equivalence relations to approximate subsets of a universe $U$ . However, many real-world scenarios involve non-equivalence relations (e.g., tolerance relations, quasiorders, or arbitrary binary relations). When the underlying relation $R$ is not an equivalence, the set of rough sets $RS$ (pairs of lower and upper approximations) does not necessarily form a lattice, or if it does, it may lack desirable algebraic properties.

To address this, the authors utilize the Dedekind–MacNeille completion of the ordered set of rough sets, denoted as $DM(RS)$. This completion ensures a complete lattice structure even when $RS$ itself is not a lattice. The central problem of this paper is to characterize the specific types of reflexive relations $R$ under which the completed lattice $DM(RS)$ forms specific, well-behaved algebraic structures:

Regular Pseudocomplemented Kleene Algebras.
Double Stone Algebras.
Regular Double Stone Algebras.

The authors aim to generalize the known results for equivalence relations to a broader class of reflexive relations, specifically investigating when these algebras satisfy the Stone condition ( $x^* \vee x^{**} = 1$ ) and regularity (congruence-regularity).

2. Methodology

The paper employs a combination of order theory, lattice theory, and rough set theory. The methodology proceeds as follows:

Foundational Setup: The authors define rough approximations ( $X^\blacktriangleleft, X^\blacktriangleright$ ) based on an arbitrary reflexive relation $R$ on a universe $U$ . They define the set of rough sets $RS$ and its Dedekind–MacNeille completion $DM(RS)$.
Algebraic Characterization: They analyze the algebraic properties of $DM(RS)$ by examining the structure of the lattices of approximations $\wp(U)^\blacktriangleright$ (upper approximations) and $\wp(U)^\blacktriangleleft$ (lower approximations).
Pseudocomplementation: The authors derive explicit formulas for the pseudocomplement ( $^*$ ) and dual pseudocomplement ( $^+$ ) in $DM(RS)$ based on the properties of $\wp(U)^\blacktriangleright$ . They utilize the concept of the core of a relation ( $core_R(x)$ ) to construct these complements.
Structural Analysis of Join-Irreducibles: A critical part of the methodology involves analyzing the completely join-irreducible elements ( $J$ ) of the lattice $DM(RS)$. The authors categorize these elements and study the "levels" of the poset $J$ .
Condition Derivation: They establish necessary and sufficient conditions on the relation $R$ (specifically regarding the atoms of $\wp(U)^\blacktriangleright$ and the non-emptiness of cores) that force $DM(RS)$ to satisfy the axioms of Stone and Double Stone algebras.
Counter-Examples and Generalizations: The paper uses specific examples (e.g., non-symmetric, non-transitive relations) to demonstrate that these algebraic structures can exist outside the realm of equivalence relations.

3. Key Contributions

A. Characterization of Regular Pseudocomplemented Kleene Algebras

The authors prove that if $DM(RS)$ is a spatial and completely distributive lattice, it forms a regular pseudocomplemented Kleene algebra if and only if the lattice of upper approximations $\wp(U)^\blacktriangleright$ is an atomistic Boolean lattice.

This generalizes previous results where such structures were only known to exist for equivalence relations or specific tolerance relations induced by irredundant coverings.

B. Characterization of Stone and Double Stone Algebras

The paper introduces specific conditions, labeled (St1) and (St2), which relate to the intersection properties of upper approximations.

Stone Condition: $DM(RS)$ is a Stone algebra if and only if for any $x, y, p$ where $\{x\}^\blacktriangleright, \{y\}^\blacktriangleright \subseteq \{p\}^\blacktriangleright$ , the meet $\{x\}^\blacktriangleright \wedge \{y\}^\blacktriangleright$ is non-empty.
Double Stone Condition: $DM(RS)$ is a Double Stone algebra if it is a Stone algebra and its dual is also a Stone algebra.

C. Introduction of "Clinker Equivalence"

The most significant contribution is the identification of a new class of relations called clinker equivalence.

Definition: A reflexive relation $R$ is a clinker equivalence if the family of sets $\{\{x\}^\blacktriangleright \mid x \in U\}$ forms an irredundant covering of $U$ .
Significance: The authors prove that $DM(RS)$ forms a regular double Stone algebra if and only if $R$ is a clinker equivalence.
Generalization: This class is strictly broader than the class of equivalence relations. For instance, the relation $R$ on $U=\{1,2,3\}$ where $R(1)=U, R(2)=\{2\}, R(3)=\{1,3\}$ is not an equivalence relation (it is not symmetric or transitive), yet it generates a regular double Stone algebra isomorphic to $2 \times 3$ .

D. Explicit Construction of Complements

The paper provides constructive formulas for the pseudocomplements in $DM(RS)$ using the core of the inverse relation:
$(A, B)^* = (B^* \triangledown \blacktriangleleft, B^*)$
where $B^*$ is the pseudocomplement in $\wp(U)^\blacktriangleright$ , and $B^*$ is computed via the core sets: $B^* = K(B)^{\blacktriangleright c \blacktriangleleft \blacktriangleright}$ .

4. Key Results

Lattice Structure: If $R$ is reflexive and $\wp(U)^\blacktriangleright$ is completely distributive, $DM(RS)$ is a completely distributive pseudocomplemented Kleene algebra.
Regularity Condition: $DM(RS)$ is a regular Kleene algebra if and only if the set of completely join-irreducible elements of $DM(RS)$ has at most two levels (i.e., no chains of length 3 exist in the irreducible elements). This occurs precisely when $\wp(U)^\blacktriangleright$ is an atomistic Boolean lattice.
Stone Condition: $DM(RS)$ is a Stone algebra if and only if condition (St1) holds: for any $p$ , the set $\{p\}^\blacktriangleright$ contains exactly one atom of $\wp(U)^\blacktriangleright$ (in the atomic case).
Main Theorem (Theorem 7.2 & 7.6): $DM(RS)$ is a regular double Stone algebra if and only if $R$ $R$ is a clinker equivalence.
- This implies that the algebraic structure of rough sets for these specific non-equivalence relations is as rich and well-behaved as that of classical equivalence relations.

5. Significance

Theoretical Expansion: The paper significantly expands the scope of rough set theory beyond equivalence relations. It demonstrates that the desirable algebraic properties of rough sets (specifically Stone and Double Stone algebras) do not strictly require symmetry or transitivity, but rather specific structural properties of the induced covering (irredundancy).
New Algebraic Class: The introduction of clinker equivalence provides a new mathematical object for researchers to study. It bridges the gap between rough sets and covering-based rough sets, offering a precise algebraic characterization.
Practical Implications: In applications involving directional similarity (e.g., "A resembles B" does not imply "B resembles A") or variable precision rough sets, relations are often reflexive but not symmetric. This work assures that even in these complex, non-symmetric scenarios, the resulting algebraic structures can be regular and well-defined, facilitating logical reasoning and data analysis.
Methodological Rigor: By utilizing the Dedekind–MacNeille completion, the authors bypass the limitation that $RS$ itself might not be a lattice, allowing for a unified algebraic treatment of rough sets under arbitrary reflexive relations.

In conclusion, the paper establishes that the "regularity" and "Stone" properties of rough set algebras are determined by the combinatorial structure of the upper approximations (specifically, whether they form an atomistic Boolean lattice and an irredundant covering), rather than the traditional requirement of an equivalence relation. This leads to the discovery of clinker equivalences as a novel generalization of equivalence relations in rough set theory.