Lattice-based relation algebras and their representability.

*(English)*Zbl 1175.03041
de Swart, Harrie (ed.) et al., Theory and applications of relational structures as knowledge instruments. COST Action 274, TARSKI. Revised papers. Berlin: Springer (ISBN 3-540-20780-5/pbk). Lect. Notes Comput. Sci. 2929, 231-255 (2003).

Introduction: The motivation for this paper comes from the following sources. First, one can observe that the two major concepts underlying the methods of reasoning with incomplete information are the concept of degree of truth of a piece of information and the concept of approximation of a set of information items. We shall refer to the theories employing the concept of degree of truth as to theories of fuzziness and to the theories employing the concept of approximation as to theories of roughness. The algebraic structures relevant to these theories are residuated lattices and Boolean algebras with operators, respectively. Residuated lattices provide an arithmetic of degrees of truth and Boolean algebras equipped with the appropriate operators provide a method of reasoning with approximately determined information. Both classes of algebras have a lattice structure as a basis. Second, both theories of fuzziness and theories of roughness develop generalizations of relation algebras to algebras of fuzzy relations and algebras of rough relations, respectively. In both classes a lattice structure is a basis. Third, not necessarily distributive lattices with modal operators, which can be viewed as most elementary approximation operators, were recently developed by Orłowska and Vakarelov (2003) (distributive lattices with operators were considered by Gehrke and Jónsson (1994) and by Sofronie-Stokkermans (2000)). With this background, our aim is to begin a systematic study of the classes of algebras that have the structure of a (not necessarily distributive) lattice and, moreover, in each class there are some operators added to the lattice which are relevant for binary relations. Our main interest is in developing relational representation theorems for the classes of lattices with operators under consideration. More precisely, we wish to guarantee that each algebra of our classes is isomorphic to an algebra of binary relations on a set. We prove the theorems of that form by suitably extending the Urquhart representation theorem for lattices (1978) and the representation theorems presented in [G. Allwein and J. M. Dunn, “Kripke models for linear logic”, J. Symb. Log. 58, No. 2, 514–545 (1993; Zbl 0795.03013)]. The classes defined in the paper are the parts which put together lead to what might be called lattice-based relation algebras. Our view is that these algebras would be the weakest structures relevant for binary relations. All the other algebras of binary relations considered in the literature would then be their signature and/or axiomatic extensions.

For the entire collection see [Zbl 1029.00017].

For the entire collection see [Zbl 1029.00017].