Affiliations: Institut für Informatik, Christian-Albrechts-Universität zu Kiel, 24098 Kiel, Germany. rub@informatik.uni-kiel.de | Department of Computer Science, Brock University, St. Catharines, Ontario, Canada, L2S 3A1, mwinter@brocku.ca
Note: [] The second author gratefully acknowledges support from the Natural Sciences and Engineering Research Council of Canada. Address for correspondence: Department of Computer Science, Brock University, St. Catharines, Ontario, Canada, L2S 3A1
Abstract: We introduce the decomposition of an arbitrary relation into a sequential composition of three relations, viz. of a mapping with a partial order and then the transpose of a mapping. After presenting some basic properties, we investigate the specific classes of junkfree, irreducible and minimal decompositions and show that for all relations a minimal decomposition exists. We also study decompositions with regard to DedekindMacNeille completions and concept lattices. These constructions are closely related to decompositions of relations. In our setting the fundamental theorem of concept lattices states that concept lattices are minimal-complete decompositions and all such decompositions are isomorphic. As a further main result we prove that the cutDedekindMacNeille completion of the order that belongs to the minimal decomposition of a relation is isomorphic to the concept lattice of that relation. Instead of considering binary relations on sets, we will work point-free within the general framework of allegories. This complement-free approach implies that the results of the paper can be applied to all models of these algebraic structures, including, for instance, lattice-valued fuzzy relations.
