Sauter au contenu
Logo image

Algèbre abstraite Théorie et applications

Thomas W. Judson

Section 19.1 Treillis

Sous-section 19.1.1 Ensembles partiellement ordonnés

Nous commençons l’étude des treillis et des algèbres de Boole en généralisant la notion d’inégalité. Rappelons qu’une relation sur un ensemble \(X\) est un sous-ensemble de \(X \times X\text{.}\) Une relation \(P\) sur \(X\) est appelée un ordre partiel de \(X\) si elle satisfait les axiomes suivants.
  1. La relation est réflexive : \((a, a) \in P\) pour tout \(a \in X\text{.}\)
    🔗
    🔗
  2. La relation est antisymétrique : si \((a,b) \in P\) et \((b,a) \in P\text{,}\) alors \(a = b\text{.}\)
    🔗
    🔗
  3. La relation est transitive : si \((a, b) \in P\) et \((b, c) \in P\text{,}\) alors \((a, c) \in P\text{.}\)
    🔗
    🔗
Nous écrirons généralement \(a \preceq b\) pour désigner \((a, b) \in P\text{,}\) sauf si un symbole est naturellement associé à un ordre partiel particulier, comme \(a \leq b\) pour des entiers \(a\) et \(b\text{,}\) ou \(A \subset B\) pour des ensembles \(A\) et \(B\text{.}\) Un ensemble \(X\) muni d’un ordre partiel \(\preceq\) est appelé un ensemble partiellement ordonné, ou poset.
🔗

Exemple 19.1.1.

L’ensemble des entiers (ou des rationnels ou des réels) est un poset où \(a \leq b\) a la signification usuelle pour deux entiers \(a\) et \(b\) dans \({\mathbb Z}\text{.}\)
🔗
🔗

Exemple 19.1.2.

Soit \(X\) un ensemble quelconque. Nous définirons l’ensemble des parties de \(X\) comme l’ensemble de tous les sous-ensembles de \(X\text{.}\) Nous notons l’ensemble des parties de \(X\) par \({\mathcal P}(X)\text{.}\) Par exemple, soit \(X = \{ a, b, c \}\text{.}\) Alors \({\mathcal P}(X)\) est l’ensemble de tous les sous-ensembles de l’ensemble \(\{ a, b, c \}\) :
\begin{align*} & \emptyset & & \{ a \} & & \{ b \} & & \{ c \} &\\ & \{ a, b \} & & \{ a, c\} & &\{ b, c\} & & \{ a, b, c \}. & \end{align*}
Sur tout ensemble des parties d’un ensemble \(X\text{,}\) l’inclusion d’ensembles, \(\subset\text{,}\) est un ordre partiel. Nous pouvons représenter l’ordre sur \(\{ a, b, c \}\) schématiquement par un diagramme tel que celui de Figure 19.1.3.
🔗
🔗
Un graphe avec l’ensemble constitué de a, b, c au premier niveau ; les ensembles (a, b), (a, c) et (b, c) au deuxième niveau ; les trois ensembles constitués de a, b et c au troisième niveau ; et l’ensemble vide au quatrième niveau.
Figure 19.1.3. Ordre partiel sur \(\mathcal P( \{ a, b, c \})\)
🔗

Exemple 19.1.4.

Soit \(G\) un groupe. L’ensemble des sous-groupes de \(G\) est un poset, où l’ordre partiel est l’inclusion d’ensembles.
🔗
🔗

Exemple 19.1.5.

Il peut y avoir plus d’un ordre partiel sur un ensemble donné. Nous pouvons définir un ordre partiel sur \({\mathbb N}\) par \(a \preceq b\) si \(a \mid b\text{.}\) La relation est certainement réflexive puisque \(a \mid a\) pour tout \(a \in {\mathbb N}\text{.}\) Si \(m \mid n\) et \(n \mid m\text{,}\) alors \(m = n\) ; donc la relation est également antisymétrique. La relation est transitive, car si \(m \mid n\) et \(n \mid p\text{,}\) alors \(m \mid p\text{.}\)
🔗
🔗

Exemple 19.1.6.

Soit \(X = \{ 1, 2, 3, 4, 6, 8, 12, 24 \}\) l’ensemble des diviseurs de \(24\) avec l’ordre partiel défini dans Exemple 19.1.5. La Figure 19.1.7 montre l’ordre partiel sur \(X\text{.}\)
🔗
🔗
Un graphe avec 24 au premier niveau, 8 et 12 au deuxième niveau, 4 (relié à 8 et 12) et 6 (relié à 12) au troisième niveau, 2 (relié à 4 et 6) et 3 (relié à 6) au quatrième niveau, et 1 au niveau inférieur.
Figure 19.1.7. Un ordre partiel sur les diviseurs de \(24\)
🔗
Soit \(Y\) un sous-ensemble d’un poset \(X\text{.}\) Un élément \(u\) de \(X\) est un majorant de \(Y\) si \(a \preceq u\) pour tout élément \(a \in Y\text{.}\) Si \(u\) est un majorant de \(Y\) tel que \(u \preceq v\) pour tout autre majorant \(v\) de \(Y\text{,}\) alors \(u\) est appelé la borne supérieure ou supremum de \(Y\text{.}\) Un élément \(l\) de \(X\) est dit minorant de \(Y\) si \(l \preceq a\) pour tout \(a \in Y\text{.}\) Si \(l\) est un minorant de \(Y\) tel que \(k \preceq l\) pour tout autre minorant \(k\) de \(Y\text{,}\) alors \(l\) est appelé la borne inférieure ou infimum de \(Y\text{.}\)
🔗

Exemple 19.1.8.

Soit \(Y = \{ 2, 3, 4, 6 \}\) contenu dans l’ensemble \(X\) de Exemple 19.1.6. Alors \(Y\) a pour majorants \(12\) et \(24\text{,}\) avec \(12\) comme borne supérieure. Le seul minorant est \(1\) ; il doit donc être la borne inférieure.
🔗
🔗
Il s’avère que les bornes supérieures et les bornes inférieures sont uniques lorsqu’elles existent.
🔗

Démonstration.

Soient \(u_1\) et \(u_2\) des bornes supérieures de \(Y\text{.}\) Par définition de la borne supérieure, \(u_1 \preceq u\) pour tout majorant \(u\) de \(Y\text{.}\) En particulier, \(u_1 \preceq u_2\text{.}\) De même, \(u_2 \preceq u_1\text{.}\) Donc \(u_1 = u_2\) par antisymétrie. Un argument similaire montre que la borne inférieure est unique.
🔗
🔗
Sur de nombreux posets, il est possible de définir des opérations binaires en utilisant la borne inférieure et la borne supérieure de deux éléments. Un treillis est un poset \(L\) tel que toute paire d’éléments de \(L\) a une borne supérieure et une borne inférieure. La borne supérieure de \(a, b \in L\) est appelée la réunion de \(a\) et \(b\) et est notée \(a \vee b\text{.}\) La borne inférieure de \(a, b \in L\) est appelée l’intersection de \(a\) et \(b\) et est notée \(a \wedge b\text{.}\)
🔗

Exemple 19.1.10.

Soit \(X\) un ensemble. Alors l’ensemble des parties de \(X\text{,}\) \({\mathcal P}(X)\text{,}\) est un treillis. Pour deux ensembles \(A\) et \(B\) dans \({\mathcal P}(X)\text{,}\) la borne supérieure de \(A\) et \(B\) est \(A \cup B\text{.}\) Certes \(A \cup B\) est un majorant de \(A\) et \(B\text{,}\) puisque \(A \subset A \cup B\) et \(B \subset A \cup B\text{.}\) Si \(C\) est un autre ensemble contenant à la fois \(A\) et \(B\text{,}\) alors \(C\) doit contenir \(A \cup B\) ; donc \(A \cup B\) est la borne supérieure de \(A\) et \(B\text{.}\) De même, la borne inférieure de \(A\) et \(B\) est \(A \cap B\text{.}\)
🔗
🔗

Exemple 19.1.11.

Soit \(G\) un groupe et supposons que \(X\) est l’ensemble des sous-groupes de \(G\text{.}\) Alors \(X\) est un poset ordonné par l’inclusion ensembliste, \(\subset\text{.}\) L’ensemble des sous-groupes de \(G\) est également un treillis. Si \(H\) et \(K\) sont des sous-groupes de \(G\text{,}\) la borne inférieure de \(H\) et \(K\) est \(H \cap K\text{.}\) L’ensemble \(H \cup K\) peut ne pas être un sous-groupe de \(G\text{.}\) Nous laissons au lecteur le soin de montrer que la borne supérieure de \(H\) et \(K\) est le sous-groupe engendré par \(H \cup K\text{.}\)
🔗
🔗
En théorie des ensembles, nous avons certaines conditions de dualité. Par exemple, par les lois de De Morgan, tout énoncé sur les ensembles vrai pour \((A \cup B)'\) doit également être vrai pour \(A' \cap B'\text{.}\) Nous avons également un principe de dualité pour les treillis.
🔗
Le théorème suivant nous dit qu’un treillis est une structure algébrique avec deux opérations binaires satisfaisant certains axiomes.
🔗

Démonstration.

Par le principe de dualité, nous n’avons besoin de prouver que le premier énoncé de chaque partie.
🔗
(1) Par définition \(a \vee b\) est la borne supérieure de \(\{ a, b\}\text{,}\) et \(b \vee a\) est la borne supérieure de \(\{ b, a \}\) ; or \(\{ a, b\} = \{ b, a \}\text{.}\)
🔗
(2) Nous allons montrer que \(a \vee ( b \vee c)\) et \((a \vee b) \vee c\) sont tous deux des bornes supérieures de \(\{ a, b, c \}\text{.}\) Soit \(d = a \vee b\text{.}\) Alors \(c \preceq d \vee c = (a \vee b) \vee c\text{.}\) Nous savons également que
\begin{equation*} a \preceq a \vee b =d \preceq d \vee c = (a \vee b) \vee c\text{.} \end{equation*}
Un argument similaire montre que \(b \preceq (a \vee b) \vee c\text{.}\) Donc \((a \vee b) \vee c\) est un majorant de \(\{ a, b, c \}\text{.}\) Nous devons maintenant montrer que \((a \vee b) \vee c\) est la borne supérieure de \(\{ a, b, c\}\text{.}\) Soit \(u\) un autre majorant de \(\{ a, b, c \}\text{.}\) Alors \(a \preceq u\) et \(b \preceq u\) ; donc \(d = a \vee b \preceq u\text{.}\) Puisque \(c \preceq u\text{,}\) il s’ensuit que \((a \vee b) \vee c = d \vee c \preceq u\text{.}\) Donc \((a \vee b) \vee c\) doit être la borne supérieure de \(\{ a, b, c\}\text{.}\) La démonstration que \(a \vee ( b \vee c)\) est la borne supérieure de \(\{ a, b, c \}\) est identique. Par conséquent, \(a \vee ( b \vee c) = (a \vee b) \vee c\text{.}\)
🔗
(3) La réunion de \(a\) et \(a\) est la borne supérieure de \(\{ a \}\) ; donc \(a \vee a = a\text{.}\)
🔗
(4) Soit \(d = a \wedge b\text{.}\) Alors \(a \preceq a \vee d\text{.}\) D’autre part, \(d = a \wedge b \preceq a\text{,}\) et donc \(a \vee d \preceq a\text{.}\) Par conséquent, \(a \vee ( a \wedge b) = a\text{.}\)
🔗
🔗
Étant donné un ensemble arbitraire \(L\) avec des opérations \(\vee\) et \(\wedge\) satisfaisant les conditions du théorème précédent, il est naturel de se demander si cet ensemble provient ou non d’un treillis. Le théorème suivant affirme que c’est toujours le cas.
🔗

Démonstration.

Nous montrons d’abord que \(L\) est un poset sous \(\preceq\text{.}\) Puisque \(a \vee a = a\text{,}\) \(a \preceq a\) et \(\preceq\) est réflexif. Pour montrer que \(\preceq\) est antisymétrique, supposons \(a \preceq b\) et \(b \preceq a\text{.}\) Alors \(a \vee b = b\) et \(b \vee a = a\text{.}\) Par la loi commutative, \(b = a \vee b = b \vee a = a\text{.}\) Enfin, nous devons montrer que \(\preceq\) est transitif. Supposons \(a \preceq b\) et \(b \preceq c\text{.}\) Alors \(a \vee b = b\) et \(b \vee c = c\text{.}\) Ainsi,
\begin{equation*} a \vee c = a \vee (b \vee c ) = ( a \vee b) \vee c = b \vee c = c\text{,} \end{equation*}
soit \(a \preceq c\text{.}\)
🔗
Pour montrer que \(L\) est un treillis, nous devons prouver que \(a \vee b\) et \(a \wedge b\) sont, respectivement, la borne supérieure et la borne inférieure de \(a\) et \(b\text{.}\) Puisque \(a=(a \vee b) \wedge a = a \wedge (a \vee b)\text{,}\) il s’ensuit que \(a \preceq a \vee b\text{.}\) De même, \(b \preceq a \vee b\text{.}\) Donc \(a \vee b\) est un majorant de \(a\) et \(b\text{.}\) Soit \(u\) un autre majorant quelconque de \(a\) et \(b\text{.}\) Alors \(a \preceq u\) et \(b \preceq u\text{.}\) Mais \(a \vee b \preceq u\) puisque
\begin{equation*} (a \vee b) \vee u = a \vee (b \vee u) = a \vee u = u\text{.} \end{equation*}
La preuve que \(a \wedge b\) est la borne inférieure de \(a\) et \(b\) est laissée en exercice.
🔗
🔗
🔗
🔗
PrécédentTopSuivant