partition d'un ensemble

Imaginez six jetons numérotés de 1 à 6. On les range dans trois boîtes : les impairs {1, 3, 5}, les nombres pairs inférieurs à 6 {2, 4}, et le jeton seul {6}. Chaque jeton va dans une boîte, aucun n'apparaît dans deux boîtes et aucune boîte n'est vide.

Ce rangement forme une partition de l'ensemble des six jetons. Les boîtes sont les blocs de la partition : elles découpent l'ensemble sans oubli ni chevauchement.

Soit un ensemble appelé E. Une partition de E est une collection de sous-ensembles, appelés blocs, qui satisfait simultanément trois conditions. Chaque bloc est non vide. Deux blocs distincts ont une intersection vide. Enfin, la réunion de tous les blocs est E.

En notant P la collection de blocs, ces conditions s'écrivent :

Ces trois propriétés ont chacune un rôle : interdire un bloc vide, empêcher les chevauchements et ne laisser aucun élément de E de côté. Une relation d'équivalence sur E regroupe les éléments en classes d'équivalence ; ces classes forment une partition. Réciproquement, une partition définit une relation d'équivalence en déclarant deux éléments équivalents lorsqu'ils appartiennent au même bloc.

Une partition met en jeu quatre éléments liés. L'ensemble support E fournit tous les éléments à répartir. La collection P rassemble les blocs. Chaque bloc est un sous-ensemble non vide de E. L'appartenance à un même bloc détermine enfin quels éléments sont regroupés.

Les blocs dépendent du support, car ils ne peuvent contenir que ses éléments. Leur réunion reconstitue le support, tandis que leur disjonction garantit qu'un élément n'appartient qu'à un seul bloc. L'ordre dans lequel on dessine ou énumère les blocs ne change pas la partition. Pour les six jetons, trois contours séparés rendent visibles le bloc {1, 3, 5}, le bloc {2, 4} et le bloc {6}.

On considère l'ensemble E = {1, 2, 3, 4, 5, 6} et la collection P = {{1, 3, 5}, {2, 4}, {6}}. Les données sont donc les six éléments de E et les trois blocs proposés.

1. Chaque bloc contient au moins un élément : ils ont respectivement 3, 2 et 1 éléments.
2. Comparons les blocs deux à deux. Aucun nombre n'est répété, donc leurs trois intersections sont vides.
3. Réunissons les blocs : {1, 3, 5} ∪ {2, 4} ∪ {6} = {1, 2, 3, 4, 5, 6} = E.
4. Les trois conditions sont satisfaites : P est une partition de E.

Le contrôle peut être refait élément par élément : chacun des six nombres apparaît exactement une fois dans la collection. Si 6 était ajouté au deuxième bloc, il y aurait chevauchement ; s'il était retiré du troisième sans être replacé, la réunion ne couvrirait plus E.

Pour classer des objets sans ambiguïté, une partition convient lorsque chaque objet doit recevoir une catégorie unique. Si plusieurs catégories peuvent s'appliquer au même objet, il faut plutôt employer une famille de sous-ensembles qui se chevauchent.

Dans une démonstration, on peut traiter séparément plusieurs cas qui forment une partition. Le bon contrôle consiste à s'assurer que tout cas possible est couvert une fois et une seule ; sinon, l'étude risque un oubli ou un double comptage.

Une relation d'équivalence fournit automatiquement un classement : on place ensemble les éléments équivalents. On préfère cette voie quand le critère de regroupement est donné comme une relation ; les blocs obtenus sont alors ses classes d'équivalence.

Une partition n'est pas un simple recouvrement. Un recouvrement exige que la réunion couvre E, mais il peut autoriser des chevauchements. Ainsi, {{1, 2}, {2, 3}} recouvre {1, 2, 3} sans en être une partition, car 2 appartient aux deux sous-ensembles.

Un bloc n'est pas la partition entière. Pour E = {1, 2, 3}, {1, 2} peut être un bloc, tandis que {{1, 2}, {3}} est la partition. Le critère qui tranche est le niveau considéré : un sous-ensemble contre une collection couvrant E.

Une classe d'équivalence est un bloc produit par une relation d'équivalence donnée. Une partition peut être présentée directement, sans relation préalable ; elle permet toutefois de reconstruire une relation en regroupant les éléments d'un même bloc.

Pour un ensemble non vide E, la collection réduite à {E} est une partition à un seul bloc. À l'autre extrême, la collection de tous les singletons de E est aussi une partition. Le nombre de blocs peut donc varier sans que l'ensemble support change.

Le sous-ensemble vide ne peut pas être ajouté comme bloc. Il ne crée certes aucun chevauchement et ne change pas la réunion, mais il viole explicitement la condition de non-vacuité des blocs.

Pour l'ensemble vide, la collection vide est généralement admise comme son unique partition : sa réunion est vide et les conditions portant sur ses blocs sont satisfaites sans bloc à vérifier. Cette convention doit être annoncée si le contexte exclut les partitions sans bloc.

Vérifier seulement que chaque élément apparaît au moins une fois ne suffit pas. Dans {{1, 2}, {2, 3}}, tous les éléments de {1, 2, 3} apparaissent, mais 2 apparaît deux fois. Le contrôle fiable exige une appartenance à exactement un bloc.

La relation d'équivalence formalise le critère qui place deux éléments dans un même bloc.

La classe d'équivalence montre comment ce critère devient concrètement l'un des blocs de la partition.

Le nombre de Bell compte les partitions possibles d'un ensemble fini en fonction de son nombre d'éléments.