L’ordre vu à travers les diagrammes de la théorie des catégories

• Une structure d’ordre est définie lorsqu’une relation binaire sur un ensemble d’éléments satisfait des lois comme la réflexivité, la transitivité et l’antisymétrie
• Un ordre linéaire est une structure dans laquelle toute paire d’éléments est comparable ; si l’on retire la totalité, on obtient un ordre partiel
• Dans un ordre partiel, on peut décrire la structure à l’aide de chaînes, d’élément maximal et minimal, de join·meet et de diagrammes de Hasse
• Le mélange des couleurs, la divisibilité des nombres et l’inclusion entre ensembles sont des exemples d’ordres partiels ; lorsqu’ils possèdent tous deux un join et un meet, ils forment un lattice
• Un preorder est une structure ne possédant que la réflexivité et la transitivité, et tout preorder peut être interprété comme une catégorie où il existe au plus un morphisme entre deux objets

---

Ordre

• Un ordre est composé d’un ensemble d’éléments et d’une relation binaire définie sur cet ensemble ; une structure mathématique apparaît lorsque certaines lois sont satisfaites
  • L’essentiel n’est pas tant le critère d’ordre lui-même que les propriétés de la relation entre les éléments
  • Une relation binaire est une relation entre deux éléments d’un ensemble, et peut aussi être représentée par des flèches
• En théorie des ensembles, un ordre peut être représenté comme un sous-ensemble du produit cartésien d’un ensemble avec lui-même ; en programmation, comme une fonction comparant deux objets
  • Mais toute fonction de comparaison ou tout ensemble de paires d’éléments ne définit pas un ordre ; pour obtenir un résultat cohérent indépendamment de la disposition initiale, certaines règles sont nécessaires

Ordre linéaire

• L’ordre linéaire** est un ordre dans lequel tous les éléments ont une position les uns par rapport aux autres, une structure où il n’y a** aucune ambiguïté sur le fait qu’un élément précède un autre

  • L’ordre des couleurs selon la longueur d’onde de la lumière ou leur disposition dans un arc-en-ciel est donné comme exemple
  • Un ordre linéaire est défini comme une relation binaire satisfaisant la réflexivité, la transitivité, l’antisymétrie et la totalité
  • Ces quatre lois constituent les conditions d’une relation d’ordre

• Réflexivité

  • Tout élément doit être plus grand ou égal à lui-même, et pour tout $a$, on a $a \le a$
  • C’est la règle qui traite le cas de base ; si, au contraire, on définit la relation de sorte qu’un élément ne soit pas relié à lui-même, on obtient un autre type de structure proche d’un strict order

• Transitivité

  • Si $a \le b$ et $b \le c$, alors on doit avoir $a \le c$
  • C’est une loi qui détermine une grande part de l’essence de l’ordre

• Antisymétrie

  • C’est la règle qui interdit les résultats de comparaison contradictoires : le cas $x \le y$ et $y \le x$ n’est autorisé que si $x = y$
  • Le texte la résume aussi en disant qu’une égalité ex aequo n’est pas autorisée

• Totalité

  • Toute paire d’éléments doit être comparable, et pour n’importe quels deux éléments, on a $a \le b \lor b \le a$
  • Pour toute paire, l’un des deux doit être plus grand ou égal à l’autre
  • Comme la totalité inclut le cas où $a$ et $b$ sont égaux, elle contient la réflexivité comme cas particulier
  • Si l’on retire la totalité, on obtient un ordre partiel, et l’ordre linéaire est aussi noté total order

• L’ordre des nombres naturels

  • Les nombres naturels forment un ordre linéaire sous la relation supérieur ou égal
  • Tout ordre linéaire fini est isomorphe à un sous-ensemble des nombres naturels, en faisant correspondre le premier élément à 1, le deuxième à 2, etc.
  • Ainsi, tous les ordres linéaires finis de même taille sont isomorphes entre eux
  • Du point de vue de la théorie des catégories, il est également mentionné que les diagrammes de tous les ordres linéaires finis et de la plupart des ordres linéaires infinis ont la même allure

Ordre partiel

• Un ordre partiel est la structure obtenue à partir d’un ordre linéaire en retirant la totalité, tout en conservant la réflexivité, la transitivité et l’antisymétrie
  • On utilise aussi le nom partially-ordered set, ou poset
• Tout ordre linéaire est un ordre partiel, mais tout ordre partiel n’est pas un ordre linéaire
• L’ordre partiel est également lié à la relation d’équivalence : c’est une structure où l’antisymétrie remplace la symétrie
• Dans l’exemple de comparaison du niveau au football, si seules certaines personnes peuvent être comparées directement ou indirectement, un ordre linéaire reste possible ; mais dès qu’on inclut des personnes qui ne se sont jamais affrontées, on obtient une structure non linéaire, donc un ordre partiel
  • Un ordre partiel ne peut pas toujours donner de réponse tranchée à la question de savoir qui est meilleur

• Chaînes

  • Un ordre partiel peut être composé de plusieurs sous-ensembles linéaires, appelés chain
  • L’exemple donne deux chaînes : $m \to g \to f$ et $d \to o$
  • Ces chaînes n’ont pas besoin d’être complètement séparées ; tant que toutes les connexions ne se combinent pas en une seule chaîne continue bijective, la structure reste un ordre partiel
  • Dans l’exemple, on peut savoir que $d \le g$ et $f \le g$, mais la relation entre $d$ et $f$ reste indéterminée

• Élément maximal et élément minimal

  • Si un élément $a$ satisfait $x \le a$ pour tout autre élément $x$, alors cet élément est un greatest element
  • Certains ordres partiels possèdent un tel élément ; dans le diagramme d’exemple, c’est $m$
  • Même si plusieurs éléments sont tous plus grands que les autres, s’ils ne sont pas identiques entre eux, il n’existe pas de greatest element
  • De la même manière, on définit aussi un least element

• Join

  • La least upper bound de deux éléments reliés s’appelle leur join
  • Sa définition comporte deux conditions
    • il faut avoir $A \le G$ et $B \le G$
    • pour tout autre élément $P$ plus grand que $A$ et $B$, il faut avoir $G \le P$
  • Si un élément est plus grand que l’autre, le join est simplement l’élément le plus grand
  • Dans un ordre linéaire, le join de deux éléments quelconques est donc l’élément le plus grand
  • S’il existe plusieurs bornes supérieures de même niveau, le join n’existe pas ; le join doit être unique

• Meet

  • Parmi les éléments qui sont tous plus petits ou égaux aux deux éléments, le plus grand s’appelle le meet
  • Les mêmes règles que pour le join s’appliquent en sens inverse

• Diagramme de Hasse

  • Les schémas utilisés dans cette section sont des diagrammes de Hasse
  • Ils suivent une règle supplémentaire : les éléments plus grands sont toujours placés plus haut
  • S’il y a des flèches, le point vers lequel pointe la flèche est toujours situé plus haut
  • Grâce à cette disposition, on peut comparer deux points simplement en regardant leur position verticale, et identifier un join en cherchant l’élément commun relié le plus bas

• Ordre partiel du mélange des couleurs

  • Présentation d’un color-mixing partial order, défini de sorte que chaque couleur pointe vers les couleurs qui la contiennent
  • Le join de deux couleurs quelconques est la couleur obtenue en les mélangeant

• Ordre partiel des nombres par divisibilité

  • Si l’on ordonne les nombres non par grandeur, mais selon la divisibilité, on obtient un ordre partiel
  • On définit que si $a$ divise $b$, alors $a$ précède $b$
  • Par exemple, puisque $2 \times 5 = 10$, 2 et 5 précèdent 10, mais 3 ne précède pas 10
  • Dans cet ordre, le join est le plus petit commun multiple et le meet est le plus grand commun diviseur

• Ordre partiel par inclusion

  • Lorsqu’on dispose de plusieurs ensembles contenant certains éléments communs, on peut définir un inclusion order
  • Si un ensemble $a$ contient $b$, ou autrement dit si $b$ est un sous-ensemble de $a$, alors $a$ précède $b$
  • Dans ce cas, le join est l’union et le meet l’intersection
  • Si l’on mélange les couleurs contenues dans chaque ensemble, on obtient la même structure que l’ordre partiel du mélange des couleurs vu plus haut
  • L’ordre par divisibilité des nombres est isomorphe à l’ordre d’inclusion des ensembles de nombres premiers ou des prime powers avec répétition autorisée
  • Cela découle du théorème fondamental de l’arithmétique, selon lequel tout nombre s’écrit d’une manière unique comme produit de nombres premiers

Théorème de représentation de Birkhoff

• Les ordres partiels du mélange des couleurs et de la divisibilité des nombres peuvent tous deux être représentés comme des ordres d’inclusion sur les combinaisons possibles de certains éléments de base
  • Dans le premier cas, les éléments de base sont les couleurs primaires ; dans le second, les nombres premiers ou les puissances de nombres premiers
• Le fait qu’un ordre partiel fini puisse être représenté de cette manière est déterminé par le théorème de représentation de Birkhoff
  • Il y a deux conditions
    • il existe un join et un meet pour chaque paire d’éléments
    • le join et le meet doivent être distributifs l’un par rapport à l’autre. En notation $∨$, $∧$, on a $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
• Tout ordre partiel dont tous les éléments possèdent un join et un meet est un lattice
• Lorsque ces opérations sont distributives entre elles, on obtient un distributive lattice
• Les éléments « premiers » qui composent l’ordre d’inclusion sont ceux qui ne peuvent pas être exprimés comme le join d’autres éléments ; on les appelle join-irreducible elements
• Le théorème se formule aussi ainsi : tout distributive lattice est isomorphe à l’inclusion order de ses join-irreducible elements
• Un ordre partiel qui n’est pas un distributive lattice peut malgré tout être isomorphe à un inclusion order, mais dans ce cas il correspond à un ordre d’inclusion qui ne contient pas toutes les combinaisons possibles

Treillis

• Un lattice est un ordre partiel dans lequel toute paire d’éléments possède un join et un meet
  • Tout lattice est un ordre partiel, mais tout ordre partiel n’est pas un lattice
• De nombreux ordres partiels générés par certaines règles sont des distributive lattices, et les exemples de la section précédente le deviennent aussi lorsqu’on les dessine complètement
• Dans l’exemple du mélange des couleurs, on ajoute une boule noire en haut et une boule blanche en bas
  • Sinon, les trois éléments du haut n’ont pas de join et les trois éléments du bas n’ont pas de meet

• Treillis borné

  • Un lattice qui possède à la fois un greatest element et un least element est appelé bounded lattice
  • Dans le lattice du mélange des couleurs, la boule noire est le greatest element et la boule blanche le least element
  • Il est aussi mentionné que tout lattice fini est borné

Isomorphisme d’ordre

• Un isomorphisme d’ordre est une fonction réversible entre les ensembles sous-jacents de deux ordres, qui préserve aussi les flèches de l’ordre
• En prenant l’exemple de l’ordre par divisibilité des nombres et de l’ordre d’inclusion des nombres premiers, on obtient deux fonctions
  • la fonction allant de l’ordre d’inclusion des nombres premiers à l’ordre des nombres est la multiplication des éléments de l’ensemble
  • la fonction allant de l’ordre des nombres à l’ordre d’inclusion des nombres premiers est la prime factorization, c’est-à-dire la décomposition en facteurs premiers
• La condition essentielle d’un isomorphisme d’ordre est que pour deux éléments $a$, $b$, $a \le b$ si et seulement si $F(a) \le F(b)$
• Une telle fonction est dite order-preserving

Préordre

• Un preorder est la structure obtenue à partir d’un ordre linéaire en retirant l’antisymétrie, tout en conservant la réflexivité et la transitivité
• Du point de vue de la comparabilité
  • dans un ordre linéaire, on a $a \le b$ ou $b \le a$
  • dans un ordre partiel, l’un des deux peut être vrai, ou aucun des deux
  • dans un préordre, l’un des deux, aucun des deux, ou les deux à la fois peuvent être vrais
• Un préordre diffère du sens ordinaire du mot ordre, car une flèche peut aller de n’importe quel point vers un autre
  • Le texte donne l’exemple du football, modélisé par « qui a battu qui », en incluant aussi les victoires indirectes
• À cause de la transitivité, les victoires indirectes s’ajoutent comme des relations directes, ce qui fait que lorsqu’il existe une relation cyclique, plusieurs objets deviennent tous reliés entre eux

• Préordre et relation d’équivalence

  • Le préordre est une structure intermédiaire entre un ordre partiel et une relation d’équivalence
  • Cela vient du fait qu’il ne lui manque que la (anti)symétrie, qui est précisément le point de divergence entre les deux
  • Dans un préordre, les éléments reliés dans les deux sens satisfont la symétrie et forment donc une relation d’équivalence
  • En regroupant ces éléments, on obtient les equivalence classes du préordre
  • Si l’on ne conserve que les relations entre ces classes d’équivalence, elles satisfont alors l’antisymétrie, ce qui forme un ordre partiel
  • Ainsi, pour tout préordre, on peut définir l’ordre partiel sur les classes d’équivalence de ce préordre

Préordre et catégorie

• La transitivité d’un préordre est la règle selon laquelle si $a \le b$ et $b \le c$, alors on obtient $a \le c$ ; on peut l’interpréter comme une composition de relations
• La définition d’une catégorie inclut les deux conditions suivantes
  • l’existence d’un morphisme identité pour chaque objet
  • la possibilité de composer deux morphismes appropriés, cette composition devant être associative
• Dans un préordre, la transitivité joue le rôle de la composition, et la réflexivité celui du morphisme identité
• Par conséquent, tout préordre est une catégorie
• Dans une catégorie générale, il peut y avoir plusieurs morphismes entre deux objets, mais dans un préordre il n’en existe au plus un entre deux objets donnés
  • soit $a \le b$ existe, soit il n’existe pas
• De la même manière qu’un monoïde est une catégorie à un seul objet, un ordre peut être vu comme une catégorie ne possédant qu’au plus un morphisme entre deux objets
• En raison de cette propriété, dans un préordre tous les diagrammes commutent

• Propriétés catégoriques des ordres partiels et des préordres

  • Les ordres partiels et les préordres sont tous deux des cas particuliers de préordres, donc aussi des catégories
  • En théorie des catégories, les préordres sont évoqués comme des skeletal categories, des catégories où des objets isomorphes ne coexistent pas comme objets distincts

• Produit et coproduit

  • La définition du coproduct d’une catégorie est formée de deux morphismes $A \to A + B$, $B \to A + B$ et d’une propriété universelle
  • Elle a exactement la même forme que la définition du join dans un ordre
  • Dans un ordre, tous les morphismes sont uniques, donc « être plus grand » correspond à « il existe un morphisme unique »
  • Ainsi, dans la catégorie d’un préordre, le coproduct catégorique correspond au join
  • Par dualité, le product correspond au meet

• Définition formelle

  • En théorie des catégories, on appelle thin categories les catégories qui, comme les ordres, ne possèdent qu’au plus un morphisme entre deux objets
  • Tout préordre peut être vu comme une telle thin category, et réciproquement une telle catégorie peut être interprétée comme un préordre
  • Les thin categories servent à explorer le concept de catégorie dans un cadre plus simple qu’une catégorie générale
  • Comprendre le meet et le join aide aussi à comprendre les concepts plus généraux de product et de coproduct
  • C’est également un cadre utile lorsqu’on ne s’intéresse pas aux différences entre plusieurs morphismes entre objets et qu’une structure simple suffit