Closure systems, implicational systems, overhanging relations and the case of hierarchical classification

Florent Domenach, CERMSEM
Bruno Leclerc, EHESS

Résumé. Le thème principal de cet article est l'étude des familles de Moore et des opérateurs de fermeture, particulièrement ceux apparaissant en classification hiérarchique. Ils sont considérés du point de vue de leurs systèmes implicatifs associés, et nous introduisons aussi un nouveau type de relations binaires sur P(S)associées aux familles de Moore sur S. En 1986, Adams a proposé une relation d'emboitement de ce type afin de formaliser les arbres de classification et d'expliquer les propriétés de sa célèbre méthode de consensus en termes d'emboitements. Ici, nous généralisons, en la caractérisant par trois axiomes, cette relation d'emboitement. Nous montrons qu'il y a une bijection entre ces relations d'emboitement généralisées et les familles de Moore (et donc, avec les fermetures). Une correspondance directe entre emboitements généralisés et systèmes implicatifs complets est aussi établie. Nous regardons quelles propriétés des systèmes implicatifs et des relations d'emboitement sont générales, et quelles sont celles propres aux structres classificatoires. Nous caractérisons aussi la base canonique d'implication des hiérarchies et obtenons un résultat similaire pour les emboitements.
Mots clés : Fermeture, hiérarchie, implication, emboitement.

Abstract. The main topic of this paper is the study of Moore families and closure operators, especially those appearing in hierarchical classification. They are considered from the point of view of their related implicational systems, and we also introduce a new type of binary relations on P(S)associated with Moore families on S. In 1986, Adams proposed a nesting relation of this type to formalize classification trees and explained the properties of his classical consensus method in terms of nestings. Here we generalize Adams' nestings with overhanging relations, characterized by three properties. We show that there is a one-to-one correspondence between overhanging relations and Moore families (and, so, closure mappings). A direct correspondence between overhangings and complete implicational systems is also established. We study which properties of implicational systems and overhanging relations are general and which are specific to classification structures. We characterize canonical implication bases of hierarchies and obtain a similar result for overhangings.
Keywords : Closure mapping, hierarchy, implication, nesting.

AMS Classification : C0, D83.