Treillis de Galois

Treillis de Galois

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.

Sommaire

Définition à partir d'une correspondance de Galois

  • Soient m_1 : P \rightarrow Q et m_2 : Q \rightarrow P deux fonctions définies sur les treillis (P, \leq_P) et (Q, \leq_Q) telles que (m1,m2) soit une correspondance de Galois.
  • Soit G l'ensemble des couples (p,q) \in P \times Q tels que p = m2(q) et q = m1(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) 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 XVIIe siècle, les jansénistes de Port-Royal ont dans leurs travaux explicité les notions d'intention et d'extension d'un concept. 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'intention 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.

Références

  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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Treillis de Galois de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Treillis de galois — Soient et deux fonctions définies sur les treillis et telles que (m1,m2) soit une correspondance de Galois. Soit G l ensemble des couples …   Wikipédia en Français

  • Treillis (ensemble ordonne) — Treillis (ensemble ordonné) Pour les articles homonymes, voir Treillis. Le terme treillis provient de la forme du diag …   Wikipédia en Français

  • Treillis (informatique) — Treillis (ensemble ordonné) Pour les articles homonymes, voir Treillis. Le terme treillis provient de la forme du diag …   Wikipédia en Français

  • Treillis (mathématiques) — Treillis (ensemble ordonné) Pour les articles homonymes, voir Treillis. Le terme treillis provient de la forme du diag …   Wikipédia en Français

  • Treillis complet — Treillis (ensemble ordonné) Pour les articles homonymes, voir Treillis. Le terme treillis provient de la forme du diag …   Wikipédia en Français

  • Treillis (ensemble ordonné) — Pour les articles homonymes, voir Treillis. Le terme treillis provient de la forme du diagramme de Hasse associé à la relation d ordre. Un …   Wikipédia en Français

  • Correspondance de Galois — En mathématiques, une correspondance de Galois antitone est une généralisation, pour deux ordres partiels quelconques, de la correspondance entre sous corps d une extension galoisienne et sous groupes de son groupe de Galois. Une correspondance… …   Wikipédia en Français

  • Correspondance De Galois — Soient et des fonctions définies sur deux ensembles ordonnés et . (m1,m2) est une correspondance de Galois si pour tout et pour tout …   Wikipédia en Français

  • Correspondance de galois — Soient et des fonctions définies sur deux ensembles ordonnés et . (m1,m2) est une correspondance de Galois si pour tout et pour tout …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”