Treillis de Galois

Cet article est une ébauche concernant les mathématiques.

Un treillis de Galois est un treillis dont la construction est basée sur une correspondance de Galois mais peut aussi être définie en termes de rectangles maximaux d'une relation.

Définition à partir d'une correspondance de Galois

Soient $m_{1} : P \to Q$ et $m_{2} : Q \to P$ deux fonctions définies sur les treillis $(P, \leq_{P})$ et $(Q, \leq_{Q})$ telles que $(m_{1}, m_{2})$ soit une correspondance de Galois.
Soit $G$ l'ensemble des couples $(p, q) \in P \times Q$ tels que $p = m_{2} (q)$ et $q = m_{1} (p)$
Soit $\leq$ la relation définie par $(p_{1}, q_{1}) \leq (p_{2}, q_{2})$ si et seulement si $q_{1} \leq_{Q} q_{2}$ .

La structure $(G, \leq)$ est alors un treillis appelé treillis de Galois.

Définition à partir d'une relation binaire

Soit $R \subset X \times Y$ une relation binaire.
On définit un rectangle maximal de $R$ comme un couple $(A, B)$ correspondant à un sous-produit cartésien de $R$ maximal pour l'inclusion, c'est-à-dire tel que :

$A \times B \subset R$ et $\forall A^{'} \supset A, \forall B^{'} \supset B, (A^{'} \times B^{'} \subset R \Rightarrow A^{'} = A, B^{'} = B)$ ^[1].

Ces rectangles maximaux $(A, B)$ , ordonnés par inclusion sur leurs premiers membres $A$ - ou dualement sur leurs deuxièmes membres $B$ - forment un treillis appelé treillis de Galois.

Cette dualité d'inclusion caractérise les treillis de Galois.

Théorème fondamental des treillis de Galois

Tout treillis peut être le treillis de Galois d'une relation binaire^[2]. Réciproquement, deux relations binaires peuvent avoir le même treillis de Galois (ou plus rigoureusement, deux treillis de Galois isomorphes).

Treillis de concepts

Au XVII^e siècle, les jansénistes de Port-Royal ont dans leurs travaux explicité les notions d'intension et d'extension d'un concept, déjà abordées par les philosophes grecs de l'antiquité. On retrouve ces notions philosophiques dans les modes de définitions d'un ensemble mathématique : l'extension d'un ensemble est l'inventaire de ses éléments, tandis que l'intension regroupe les propriétés caractéristiques de cet ensemble.

En 1982, le mathématicien allemand Rudolf Wille (en)^[3] a réinvesti ces notions philosophiques dans un cadre algébrique et algorithmique :

Soit X un ensemble d'objets formels et soit Y un ensemble de propriétés formelles que peuvent avoir ces objets ;
Soit $R \subseteq (X \times Y)$ une relation binaire précisant les propriétés que possèdent ces objets ;
Alors chaque élément $(A, B)$ du treillis de Galois correspondant peut être vu comme un concept formel, c'est-à-dire un ensemble d'objets partageant les mêmes propriétés. Le treillis de Galois prend alors le nom de treillis de concepts.

Notes et références

↑ Cette condition de maximalité peut se traduire par : $\forall y \notin B \exists a \in A t . q . (a, y) \notin R,$ et $\forall x \notin A \exists b \in B t . q . (x, b) \notin R$ .
↑ Ordre et classification, algèbre et combinatoire. Marc Barbut et Bernard Monjardet, Hachette, 1970.
↑ Analyse de concepts formels

Voir aussi

Sur les autres projets Wikimedia :

Treillis de Galois, sur Wikimedia Commons

Articles connexes

Lien externe

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Bibliographie

Marghoubi, R., Zeitouni, K., & Boulmakoul, A. (2006). Utilisation des treillis de Galois pour l'extraction et la visualisation des règles d'association spatiales. In INFORSID (pp. 703-718).

Portail des mathématiques

[1] Cette condition de maximalité peut se traduire par : $\forall y \notin B \exists a \in A t . q . (a, y) \notin R,$ et $\forall x \notin A \exists b \in B t . q . (x, b) \notin R$ .

[2] Ordre et classification, algèbre et combinatoire. Marc Barbut et Bernard Monjardet, Hachette, 1970.

[3] Analyse de concepts formels

[1]

[2]

[3]