Algebraic Theory of Independence in Information Systems

Abstract

The semilattice of all subsets of a finite nonempty set provided with the operation of union and a congruence of this semilattice enable to define independent elements of the semilattice. Reducts, subreducts, and superreducts of an arbitrary element in the semilattice are introduced and investigated. A particular type of congruence, the so called rough top equality, is studied. These algebraic notions and methods are applied to black boxes, to information systems, and to contexts in Wille’s sense. The algebraic results are used to solve the problem whether two sets of inputs give the same output in a black box, whether two sets of attributes define the same classification of objects in an information system, and, finally, whether two sets of features generate the same concept in a context. Partial dependence between two sets of attributes of an information system is introduced and a distance between these sets is defined.