Les ensembles quotients
Quotienter un ensemble, c'est décider que certaines différences ne comptent plus. On range alors ses éléments en paquets, les classes d'équivalence, puis on travaille avec les paquets eux-mêmes. L'ensemble de ces paquets est l'ensemble quotient E/~. Ce geste est partout : les heures d'une horloge, les fractions, les directions, les colliers qu'on peut faire tourner, les surfaces qu'on obtient en recollant les bords d'un carré. Cette page montre comment une relation découpe un ensemble, quand une fonction « passe au quotient », comment on compte les classes, et ce que devient un quotient quand on le dessine.
Vue d'ensemble
Une relation ~ sur E est une relation d'équivalence si elle est réflexive (x ~ x), symétrique (x ~ y ⇒ y ~ x) et transitive (x ~ y et y ~ z ⇒ x ~ z). La classe de x est [x] = {y ∈ E : y ~ x}. Deux classes sont soit égales, soit disjointes, et elles recouvrent E : elles forment une partition. L'ensemble quotient est E/~ = {[x] : x ∈ E}, et la projection canonique π : E → E/~, x ↦ [x], est surjective. Une classe est un élément de E/~ ; un élément de la classe en est un représentant.
| Ensemble E | On décide que… | Quotient E/~ |
|---|---|---|
| ℤ | x ~ y si x − y est multiple de 12 | les 12 heures du cadran, ℤ/12ℤ |
| ℤ × ℤ* | (p, q) ~ (r, s) si ps = qr | les fractions, ℚ |
| ℝ | x ~ y si x − y ∈ ℤ | le cercle ℝ/ℤ |
| couples de points du plan | (A, B) ~ (C, D) si ABDC est un parallélogramme | les vecteurs |
| droites du plan | d ~ d′ si d ∥ d′ | les directions |
| colliers de perles | deux colliers sont égaux à une rotation près | les colliers « vrais », orbites |
Relation d'équivalence et partition : deux visages d'une même chose
Une relation d'équivalence découpe E ; un découpage définit une relation d'équivalence.
Partons d'une relation sur E = {1, …, 24}. Si elle est réflexive, symétrique et transitive, ses classes sont disjointes et recouvrent E : c'est une partition. Inversement, une partition définit une relation, « être dans le même morceau », qui est une relation d'équivalence. Ces deux passages sont réciproques l'un de l'autre. La transitivité est la propriété décisive. La relation « être à distance au plus 2 » est réflexive et symétrique, mais 1 ~ 3 et 3 ~ 5 sans que 1 ~ 5. Ses « classes » se chevauchent, et il n'y a plus de quotient.
Passer au quotient : quand une fonction ne voit que les classes
f passe au quotient si elle prend la même valeur sur toute une classe.
Soit f : E → F. On voudrait définir f̄ sur E/~ par f̄([x]) = f(x). Ce n'est une vraie définition que si le résultat ne dépend pas du représentant choisi : il faut que x ~ y ⇒ f(x) = f(y). On dit alors que f est compatible avec ~, et f̄ est l'unique application telle que f = f̄ ∘ π. C'est la propriété universelle du quotient. Prenons ℕ avec la congruence modulo n : son quotient s'identifie à ℤ/nℤ. La fonction x ↦ x² mod n passe au quotient, et x ↦ (−1)x aussi quand n est pair. En revanche, x ↦ ⌊x/n⌋ ne passe pas au quotient, et x ↦ 2x mod n en général non plus. Si l'on calcule avec un mauvais représentant, on obtient une autre réponse.
Recoller les bords d'un carré : des surfaces comme quotients
En identifiant les bords d'un carré deux à deux, on fabrique des surfaces.
Sur le carré [0 ; 1]², décidons que certains points du bord sont « le même point ». Si (0, y) ~ (1, y), le carré se referme en cylindre ; avec (0, y) ~ (1, 1 − y), en ruban de Möbius. Si l'on recolle aussi le haut et le bas, on obtient le tore, la bouteille de Klein ou le plan projectif, selon le sens des flèches. Si l'on replie le carré sur lui-même, on obtient la sphère. Le quotient n'est plus un ensemble de paquets abstraits : il a une forme. Une fourmi qui marche tout droit dans le carré ressort par le bord opposé, à l'endroit et dans le sens que dicte la relation. On peut même calculer une caractéristique du quotient, le nombre d'Euler χ = S − A + F, en comptant les classes de sommets et d'arêtes.
Les orbites : compter les colliers
Quand un groupe agit sur E, ses orbites sont les classes d'un quotient.
Un collier de n perles en k couleurs s'écrit comme un mot de n lettres. Mais deux mots qui se déduisent l'un de l'autre par une rotation représentent le même collier. Si l'on autorise aussi à retourner le collier, on parle de bracelet. La relation « se déduire par une rotation » est une relation d'équivalence, car les rotations forment un groupe. Les colliers sont donc les classes du quotient, que l'on appelle des orbites. Pour les compter sans les énumérer, on utilise le lemme de Burnside : le nombre d'orbites est la moyenne, sur toutes les rotations g, du nombre de mots que g laisse fixes. La page énumère tous les mots, les range en classes et compare au lemme.
Signature : l'automate minimal et les anagrammes
Deux quotients qui simplifient : l'un en informatique, l'autre en combinatoire.
Un automate lit un mot lettre par lettre en passant d'un état à l'autre, et il accepte le mot s'il finit dans un état final. Celui-ci lit un nombre écrit en binaire et accepte les multiples de 3, mais il est mal construit : il a 9 états, dont beaucoup font le même travail. Deux états sont équivalents si, quelle que soit la suite du mot, ils mènent tous deux à l'acceptation ou tous deux au refus. C'est une relation d'équivalence, et l'automate quotient, qui a un état par classe, reconnaît exactement le même langage. On trouve les classes par raffinements successifs (algorithme de Moore). On part de la partition « finaux / non finaux », puis on sépare deux états dès qu'une même lettre les envoie dans des classes différentes. Le résultat est l'automate minimal (Myhill et Nerode, 1958).
Deux mots sont anagrammes l'un de l'autre s'ils utilisent les mêmes lettres le même nombre de fois. C'est encore une relation d'équivalence : une classe est un « sac de lettres », c'est-à-dire une liste d'effectifs (n₁, …, nk) de somme n. Le quotient a C(n + k − 1, k − 1) éléments, qu'on compte par la méthode des étoiles et des barres. La classe de (n₁, …, nk) contient n!/(n₁!…nk!) mots, le coefficient multinomial. En additionnant les tailles de toutes les classes, on retrouve tous les mots : kn. C'est la formule du multinôme, lue comme une partition de l'ensemble des mots.
Une brève histoire
En résumé
Relation = partition
Les relations d'équivalence sur E et les partitions de E se correspondent exactement ; E/~ est l'ensemble des morceaux.
Passer au quotient
Une fonction définie sur E se transporte sur E/~ si et seulement si elle est constante sur chaque classe ; alors f = f̄ ∘ π.
Compter, recoller, simplifier
Le quotient compte les objets « à symétrie près » (Burnside), fabrique des surfaces et réduit un automate à sa forme minimale.
Pour aller plus loin
La relation noyau. Toute application f : E → F définit une relation d'équivalence, x ~ y si f(x) = f(y), et E/~ est en bijection avec l'image de f. Toute relation d'équivalence est de cette forme : c'est le noyau de la projection π.
Un quotient n'a pas besoin de représentants. Une classe est un ensemble, et la définition de E/~ n'utilise aucun choix. Choisir un représentant dans chaque classe d'une famille infinie peut, en revanche, demander l'axiome du choix (ensemble de Vitali).
Liens. Les relations binaires, la construction des nombres (ℤ et ℚ comme quotients), les quotients en algèbre (groupes, anneaux, espaces vectoriels et théorème du rang), la topologie, l'axiome du choix.