Réflexivité, symétrie, antisymétrie, transitivité — relations d’équivalence et relations d’ordre
La page précédente construisait le produit cartésien E × E, c’est-à-dire l’ensemble de tous les couples que l’on peut former avec les éléments de E. Une relation binaire n’est rien d’autre qu’une partie de cet ensemble : pour chaque couple (a, b), on décide s’il est retenu ou non. Écrire a R b signifie exactement « le couple (a, b) appartient à la partie choisie ».
Tout ce que l’on fait ensuite avec les relations — comparer, classer, ordonner, identifier — vient de quatre propriétés que cette partie peut posséder ou non. Les trois premières planches les montrent et les mettent à l’épreuve ; la quatrième construit les ordres et leur diagramme ; la cinquième compte, une par une, toutes les relations possibles sur un petit ensemble.
Prenons E = {1, …, n}. Le tableau de droite a une case par couple : la case de la ligne a et de la colonne b est noircie lorsque a R b. Le dessin de droite montre la même chose autrement : une flèche de a vers b, et une boucle quand un élément est en relation avec lui-même. Choisissez une règle, ou cliquez directement dans les cases pour fabriquer votre propre relation.
Quatre phrases, quatre lectures du tableau. Réflexive : toute la diagonale est noire. Symétrique : le tableau est inchangé par le pli le long de la diagonale. Antisymétrique : aucune paire de cases symétriques n’est noire toutes les deux (la diagonale, elle, fait ce qu’elle veut). Transitive : dès que a R b, la ligne b doit être entièrement contenue dans la ligne a. Les boutons « examiner » font défiler la vérification, un cas après l’autre, et cerclent les contre-exemples en rouge.
Une relation réflexive, symétrique et transitive s’appelle une relation d’équivalence. Elle range automatiquement E en paquets : la classe de a est l’ensemble des éléments qui lui sont liés. Ces paquets ne sont jamais vides, ne se recoupent jamais et recouvrent tout E — autrement dit, ils forment une partition. Regardez les jetons se ranger, et vérifiez le compte : si les classes ont pour effectifs c₁, …, c_k, alors card R = c₁² + … + c_k².
Se donner une relation d’équivalence sur E ou se donner une partition de E, c’est la même chose : à chaque partition correspond une équivalence et une seule. Compter les équivalences revient donc à compter les partitions — ce sont les nombres de Bell. La page les énumère réellement, une par une, et les confronte au triangle de Bell.
| n | partitions énumérées | nombre de Bell Bₙ | écart | relations 2^(n²) |
|---|
Une relation réflexive, antisymétrique et transitive est une relation d’ordre. On peut alors dessiner l’ensemble par étages : on monte quand on grandit. Le diagramme de Hasse ne garde que le strict nécessaire — on efface les boucles (elles sont partout) et tous les traits que la transitivité impose déjà. Il ne reste que les couvertures immédiates, et pourtant la relation entière s’en déduit. Cliquez sur un élément pour voir ce qui est au-dessus et au-dessous de lui ; cliquez sur un second pour obtenir leurs bornes.
Sur un ensemble à n éléments il existe 2^(n²) relations. La page les passe toutes en revue, une par une, et compte celles qui ont chaque propriété. Trois de ces décomptes obéissent à une formule exacte, que le résultat mesuré doit retrouver au couple près. Un quatrième — la transitivité — n’a aucune formule connue, et c’est précisément lui qui s’effondre.
| n | relations 2^(n²) | réflexives | symétriques | antisymétriques | transitives | équivalences | ordres |
|---|
En portant en échelle logarithmique la proportion de relations transitives, la chute est nette : 100 % à n = 1, puis 81 %, 33 %, 6 %, 0,46 %… Le tirage au sort ci-dessous fabrique des relations au hasard et compte celles qui passent le test ; la proportion mesurée rejoint la valeur exacte, et devient introuvable dès n = 7.