The structure of rough sets defined by reflexive relations

Jouni Järvinen, Sándor Radeleczki · 2024

Read The structure of rough sets defined by reflexive relations by Jouni Järvinen, Sándor Radeleczki (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10863.txt.

Introduction

Rough set theory sorts objects by what can be told apart, and the resulting family of rough sets does not always form a neat lattice. The authors study the completion of that family, the Dedekind-MacNeille completion, for relations that are reflexive: every object relates at least to itself. Building on earlier work about joins, meets, and special algebras on this completion, they dig into its order structure. They identify the completely join-irreducible elements, the atoms from which everything else is assembled.

They also pin down when the completion becomes a fully distributive spatial lattice. A surprise follows: even without transitivity, the completion can form a Nelson algebra, a structure usually tied to stronger relations. To prove it, they introduce the core of a relational neighborhood, a new notion that yields an exact condition. The paper extends a long program of mapping rough set structures through their completions.

Catalog record

CREATORJouni Järvinen, Sándor Radeleczki
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-10863

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The structure of rough sets defined by reflexive relations Jouni Järvinen, Sándor Radeleczki Abstract . For several types of information relations, the induced rough sets system RS does not form a lattice but only a partially ordered set. However, by studying its Dedekind–MacNeille completion DM(RS), one may reveal new important properties of rough set structures. Building upon D. Umadevi’s work on describing joins and meets in DM(RS), we previously investigated pseudo-Kleene algebras defined on DM(RS) for reflexive relations. This paper delves deeper into the order-theoretic properties of DM(RS) in the context of reflexive relations. We describe the completely join-irreducible elements of DM(RS) and characterize when DM(RS) is a spatial completely distributive lattice. We show that even in the case of a non-transitive reflexive relation, DM(RS) can form a Nelson algebra, a property generally associated with quasiorders. We introduce a novel concept, the core of a relational neighborhood, and use it to provide a necessary and sufficient condition for DM(RS) to determine a Nelson algebra. 1991 Mathematics Subject Classification Primary 68T37, 06B23; Secondary 06D30, 03E20 Dedicated to the memory of Magnus Steinby 1. Introduction Rough set theory, initially introduced in [ 29 ] , is grounded in the concept of indistinguishability relations. These relations are equivalence relations defined such that two objects are considered equivalent when they appear identical based on their observable properties. Let E be an equivalence relation on U . Every subset X of U can be approximated by two sets. The upper approximation X^{\blacktriangle} consists of elements that are related to at least one element in X by the equivalence relation E . This set represents the elements that might belong to X given the information provided by E . The lower approximation X^{\blacktriangledown} consists of elements such that all elements related to them by E are also in X . This set represents the elements that definitely belong to X based on the information provided by E . The rough set of X is the pair (X^{\blacktriangledown},X^{\blacktriangle}) . This pair captures the uncertainty related to the subset X due to the limited information provided by the equivalence relation E . The collection of all rough sets, denoted by \mathrm{RS} , can be ordered coordinate-wise using the set-inclusion relation. The lattice-theoretic properties of RS have been extensively studied. For example, J. Pomykała and J. A. Pomykała [ 30 ] proved that RS forms a Stone algebra. This result was further refined by S. D. Comer [ 6 ] , who established that \mathrm{RS} forms a regular double Stone algebra. Piero Pagliani [ 28 ] introduced a Nelson algebra structure on \mathrm{RS} and showed that these Nelson algebras induced by equivalence relations are semisimple. Rough approximations and rough sets can be extended beyond equivalence relations by using other types of binary relations. A quasiorder, a reflexive and transitive relation, is one such example. Rough sets defined by quasiorders have been investigated by several researchers (see [ 9 , 23 , 24 , 25 , 27 , 31 ] , for instance). The rough set lattice \mathrm{RS} determined by a quasiorder is known to be completely distributive and spatial. Moreover, a Nelson algebra can be defined on \mathrm{RS} (see [ 14 , 15 , 16 , 21 , 22 ] ). A tolerance, a reflexive and symmetric relation, is another type of binary relation that can be used to define rough sets. While the rough set system \mathrm{RS} defined by a tolerance may not always form a lattice [ 12 ] , it does form a completely distributive and spatial lattice when the tolerance is induced by an irredundant covering. Furthermore, a pseudocomplemented regular Kleene algebra can be defined on \mathrm{RS} in this case (see [ 17 , 18 , 19 ] ). For arbitrary binary relations D. Umadevi presented the Dedekind–MacNeille completion \mathrm{DM(RS)} of \mathrm{RS} in [ 34 ] . She also described the meets and joins in \mathrm{DM(RS)} . In [ 20 ] , we investigated pseudo-Kleene algebras defined on \mathrm{DM(RS)} for reflexive relations. We proved that these algebras are always paraorthomodular. Also in a recent work [ 35 ] , Umadevi studies \mathrm{DM(RS)} in case of a reflexive relation. The motivation for this research is to further explore the order-theoretic and algebraic properties of relation-based rough set structures. Since some older studies have a special role, we start by recalling them. J. Varlet [ 37 ] proved that a double pseudocomplemented distributive lattice is regular if and only if every chain of its prime filters has at most two elements. Varlet [ 36 ] also showed that a distributive double pseudocomplemented lattice is a regular double Stone algebra if and only if its prime filters form disjoint chains of one or two elements. In [ 5 ] , R. Cignoli proved that a quasi-Nelson algebra (see page 5 of this work for the definition) is a Nelson algebra if and only if its prime filters have the so-called interpolation property. In our previous works, we proved that in a complete, completely distributive, and spatial lattice, analogous results can be presented using completely join-irreducible elements. The advantage of this is that dealing with join-irreducible elements is simpler than dealing with prime filters. We proved in [ 19 ] that a completely distributive and spatial pseudocomplemented Kleene algebra is regular if and only if its set of completely join-irreducible elements has at most two levels. Because the complete lattices of rough sets defined by tolerances induced by irredundant coverings are completely distributive and spatial, we applied this result to prove that \mathrm{RS} forms a regular pseudocomplemented Kleene algebra. Using relationships between the completely join-irreducible elements, we also provided a representation theorem stating that each pseudocomplemented Kleene algebra defined on a completely distributive and spatial lattice is isomorphic to some \mathrm{RS} defined by a tolerance induced by an irredundant covering. In [ 15 ] , we showed that a completely distributive and spatial Kleene algebra forms a Nelson algebra if and only if its set of completely join-irreducible elements has the interpolation property. Using this result, we proved that rough sets determined by a quasiorder form a Nelson algebra. Additionally, we proved that every completely distributive and spatial Nelson algebra is isomorphic to some rough set defined by a quasiorder. Note also that M. Gehrke and E. Walker proved in [ 10 ] that for an equivalence E , \mathrm{RS} is isomorphic to \mathbf{2}^{I}\times\mathbf{3}^{K} , where \mathbf{2} and \mathbf{3} are the chains of 2 and 3 elements, I is the set of the E -classes having one element, and K is the set of E -classes having more than one element. This means that the completely join-irreducible elements of \mathrm{RS} form disjoint chains of one or two elements. The above discussion highlights the special interest in the notions of completely join-irreducible elements, spatiality, and complete distributivity. In this work, we characterize the set of the completely join-irreducible elements of \mathrm{DM(RS)} . Furthermore, we characterize the cases when \mathrm{DM(RS)} is spatial and completely distributive. Our paper is structured as follows. In Section 2 , we introduce the basic notation. We also prove \mathrm{DM(RS)} is a subdirect product of \wp(U)^{\blacktriangledown}\times\wp(U)^{\blacktriangle} , where \wp(U)^{\blacktriangledown} and \wp(U)^{\blacktriangle} denote the complete lattices of all

Read the complete text