The lattice of closure systems, closure operators and implicational systems on a finite set : a survey (revised version)

Nathalie Caspard*, LACL
Bernard Monjardet, CERMSEM

Résumé. Nous présentons une synthèse des propriétés du treillis des familles de Moore (familles de parties d'un ensemble S contenant S et fermées par intersection et appellées aussi "systèmes de fermeture") sur un ensemble S fini, avec les preuves des résultats les plus significatifs. En particulier, nous prouvons que ce treillis est atomistique et borné inférieurement, et qu'il existe une base canonique permettant de représenter toute famille de Moore par des familles de Moore "implicationnelles". La notion de famille de Moore admet un certain nombre de versions cryptomorphiques, notamment les notions (d'opérateur) de fermeture et de système complet d'implications, notions présentes dans de nombreux domaines des mathématiques pures ou appliquées ainsi qu'en informatique.
Mots clés : Base canonique, famille de Moore, (opérateur de) fermeture, relation de dépendance, système d'implications, théorie de la donnée, treillis borné inférieurement.

Abstract. We present a survey of properties of the lattice of closure systems (families of subsets of a set S containing S and closed by set intersection) on a finite set S with proofs of the more significant results. In particular, we prove that this lattice is atomistic and lower bounded and that there exists a canonical basis allowing to represent any closure system by "implicational" closure systems. The notion of closure system has many cryptomorphic versions, especially the notions of closure operator and of (full) implicational system, occuring in many fields of pure or applied mathematics and of computer science.
Keywords : Canonical basis, closure operator, dependence relation, implicational system, lower bounded lattice, Moore family, theory of data.

*LACL, Université Paris 12 Val-de-Marne, 61 Avenue du Général de Gaulle, 94010 Créteil Cedex