La théorie des ordres est une branche des mathématiques qui étudie des notions centrées autour de la notion de relation d'ordre. Cela comprend aussi bien des relations d'ordre spécifiques, que les préordres, les ordres stricts, voire les relations binaires quelconques sur un ensemble. Cette discipline admet des ramifications en théorie des ensembles, en algèbre générale, en logique formelle et en topologie. Relations binaires et structures à relation Soit un ensemble, typiquement au sens de la théorie ZFC des ensembles. Une relation binaire sur un ensemble peut être vue d'une de deux manières essentiellement équivalentes : En tant qu'ensemble, il s'agit d'une partie quelconque du produit cartésien . Par définition de ce dernier, tout élément de admet tels que puisse être exprimé comme le couple . En tant que prédicat, il s'agit d'un prédicat binaire quelconque sur , dans le sens . Toutefois, étant donné et variables de la logique du premier ordre, au lieu d'écrire , nous utiliserons une notation infixée . L'équivalence de ces deux notions est le résultat de ces deux propriétés : Soit un prédicat binaire sur . On peut construire de la partie , qu'on peut aussi noter plus souplement, duquel découle le théorème . Soit une partie , on peut directement construire comme prédicat binaire tel que . Axiomes relationnels Soit une relation sur un ensemble . peut être modèle, à savoir satisfaire, un ou plusieurs des axiomes suivants. Pour des soucis de lisibilité, nous nous permettrons d'écrire, pour toutes formules bien formées de la logique du premier avec la signature de la théorie ZFC, d'écrire et , pour désigner et respectivement. La réflexivité, . L'irréflexivité, . La transivité, . L'antisymétrie, . L'asymétrie, . La , . La , . Divers résultats découlent de la satisfacation simultanée de plusieurs de ces axiomes. Par exemple, toute relation réflexive et connectée est fortement connectée, toute relation transitive et symétrique est réflexive, etc. Structures à relation Les structures à relation sont des familles de couples , chacun composé d'un ensemble muni d'une relation sur . Il s'agit, sous l'angle de la théorie des modèles, de diverses théories d'axiomes relationnels. Un ensemble préordonné, parfois appelé prosetJohn Baez. preorder. Version 16. 9 mars 2009. url : https://ncatlab.org/nlab/revision/preorder/16., satisfait refléxivité et transitivité. Un ensemble partiellement ordonné, aussi appelé poset, satisfait réflexivité, antisymétrie et transitivité. Il s'agit donc d'un proset particulier. Un ensemble totalement ordonné, aussi appelé toset, satisfait réflexivité, antisymétrie, transitivité, et connexion. Il s'agit donc d'un poset particulier. Un ensemble bien ordonné, aussi appelé wosetToby Bartels. well-order. Version 5. 11 avr. 2009. url : https://ncatlab.org/nlab/revision/well-order/5., est un toset qui satisfait également .
Une relation d'ordre est le nom donné aux relations d'ensembles partiellement ordonnés.
Toute relation binaire sur réflexive admet une contrepartie stricte irréflexive, défini en ensemble comme ., ou de sa contrepartie stricte. On dit d'un tel qu'il s'agit d'une relation d'ordre strict.
Morphismes de structures à relation Chaque théorie axiomatique de structures à relation établit une classe de tous ses modèles. Par exemple, il y a une classe de tous les ensembles préordonnés, une classe de tous les ensembles partiellement ordonnés, et autres. On peut également remarquer qu'entre deux de leurs modèles, et , on peut définir des applications telles que pour tous , il existe des uniques tels que, si , alors . De telles applications sont dites monotones, isotones, ou encore croissantesToby Bartels. monotone function. Version 1. 14 août 2009. url : https://ncatlab.org/nlab/revision/monotone+function/1.. Ces applications préservent alors la structure préordonnée, voire partiellement ordonnée, de ces modèles.
De tout ensemble d'axiomes relationnels , on remarque que la théorie axiomatique sur admet une structure de catégorie, dont la classe d'objets est la classe des modèles de , et dont la classe de morphismes est celle des applications monotones entre deux modèles de arbitraires. On appellera donc les applications croissantes, les morphismes d'ensembles ordonnés (respectivement préordonnés). De la sorte, les terminologies usuelles de la théorie des catégoriques s'appliquent au monde des ensembles ordonnés.
Un endomorphisme d'ensembles ordonnés est une application croissante d'un ensemble ordonné dans lui-même. Deux ensembles ordonnés et sont isomorphes si existent des applications croissantes et telles que et , qui sont alors appelées isomorphismes, et morphismes inverses l'un de l'autre. Un squelette de la catégorie des modèles de en est une sous-catégorie qui n'admet aucun isomorphisme entre deux objets distincts. Certains objets et constructions catégoriques peuvent être explicités, notamment : L'objet initial de la catégorie des ensembles préordonnés est , et ses objets finaux les singletons munis de l'égalité. Le produit d'une famille est donné par la structure , qui elle-même est un ensemble ordonné, et dont est appelé l'ordre produit. Attention toutefois, le produit de deux ensembles totalement ordonné n'est pas toujours totalement ordonné.
Exemples notables Les ordinaux sont des ensembles bien ordonnés. De même, tout ensemble bien ordonné est isomorphe à exactement un ordinal. Les ordinaux forment alors un squelette de la catégorie des ensembles bien ordonnés. On dit alors que la catégorie des ensembles bien ordonnés est équivalente à la catégorie des ordinaux. Quelques ordinaux importants sont les entiers naturels, et même l'ensemble des entiers naturels (aussi appelé ), dans leurs constructions ensemblistes à la von Neumann. , et munis d'une des relations ou sont des ensembles totalement ordonnés, mais ne sont pas bien ordonnés. muni de la relation de factorisabilité forme un ensemble partiellement ordonné. Il n'est cependant pas connecté. Un contre-exemple est donné par qui ni ne factorise, ni n'est factorisé par, ni n'est égal à . Lorsque l'on étend cette relation aux entiers relatifs, muni de la relation de factorisabilité ne forme plus qu'un préordre. En effet, un contre-exemple de l'antisymétrie est donné par l'observation que et , et ce, bien que . Étant donné un ensemble ordonnée , si une partie munie de la restriction de à forme est un ensemble totalement ordonné, on dit alors que est une chaîne de . D'un autre côté, on dit de que c'est une antichaîne si ses éléments sont incomparables deux à deux, c'est-à-dire que pour tous distincts, ni , ni . Le cardinal de la plus grande antichaîne de est appelé sa largeur. Le théorème de Dilworth décrit la largeur de tout ensemble ordonné par une partition de celui-ci en un nombre minimum de chaînes.
Infimums, supremums et extremums Si les théories axiomatiques gouvernant les diverses structures à relation admettent chacune leur propre catégorie, il est intéressant de noter que chaque ensemble préordonné admet sa propre catégorie associée. Sa classe d'objets est , et ses morphismes sont les parties de l'ensemble associé à qui n'admettent qu'un seul élément, à savoir des singletons. L'application source est donnée par le membre gauche de l'unique élément du morphisme, et l'application but par son membre droit. La composition, quant à elle, est l'application telle que, pour tous éléments de , on ait . Par réflexivité, les morphismes identités existent et sont les tels que . De la sorte, le vocabulaire usuel des catégories s'appliquent aux ensembles pré-ordonnés eux-mêmes. Puisqu'il existe au plus un morphisme entre deux éléments de , on dit de la catégorie associée à qu'elle est fineToby Bartels. thin category. Version 1. 18 août 2010. url : https://ncatlab.org/nlab/revision/thin+category/1.. Le squelette d'un proset étant un poset, certains auteurs peuvent restreindre cette appellation aux catégories associées aux ensembles partiellement ordonnées. On peut montrer que deux éléments sont isomorphes si et seulement si . Si est un ensemble partiellement ordonné, on a alors comme seuls isomorphismes les égalités, d'où squelettique. Après cela, on peut raisonnablement se demander si ou quand des ensembles ordonnés admettent diverses constructions catégoriques, telles que des objets initiaux et finaux, des produits, des sommes, et autres.
Soit un ensemble ordonné. Puisqu'il admet une structure de catégorie fine, les expressions de diverses constructions catégoriques se simplifient énormément. Qui plus est, bien que ce genre de constructions ne soient généralement uniques qu'à un isomorphisme près, puisqu'on s'est placé dans un ensemble ordonné, les seuls isomorphismes sont les identités, ce qui assure leur unicité.
L'objet final de , s'il existe, est l'élément tel que, pour tout , il existe un morphisme . Un tel morphisme doit normalement être unique, mais puisqu'on s'est placé dans une catégorie fine, l'existence assure l'unicité. L'objet initial, s'il existe, est quant à lui l'élément tel que, pour tout , il existe un morphisme .
Le produit catégorique dans , d'une famille , s'il existe, est l'élément tel que pour tout , où les morphismes associés servent alors de , et tel que pour tout , si pour tout , alors . Intuitivement, il s'agit alors du plus grand minorant de la famille. On écrit généralement , que l'on appelle alors l'infimum de , ou minimum de s'il s'agit d'un élément de . L'opération est parfois appelée rencontre.
La somme catégorique dans d'une famille , si elle existe, est la construction duale du produit, à savoir celle obtenue en "inversant les flèches" dans sa définition. En d'autres termes, il s'agirait de l'élément tel que pour tout , où les morphismes associés servent alors de co-projections canoniques, et tel que pour tout , si pour tout , alors . Intuitivement, il s'agit alors du plus petit majorant de la famille. On écrit généralement , que l'on appelle alors supremum de , ou maximum de s'il s'agit d'un élément de . L'opération est parfois appelée jointure.
On dit d'un ensemble partiellement ordonné qu'il est borné s'il admet un objet final, appelé son élément maximal ou maximum de , et un objet initial, appelé son élément minimal ou minimum de .
Treillis
On dira de qu'il est un treillis si, pour tous éléments , il existe un infimum et un suprémum de , qu'on note respectivement et . Dans un treillis, qu'il soit borné ou non, si ou (équivalents), on dira que est le minimum de et . De même, si ou (équivalents), on dira que est le maximum de et . À noter que équivaut à et .
A contrario d'autres théories d'axiomes relationnels, la catégorie des treillis est généralement définie de sorte que chaque morphisme de treillis soit non seulement croissante, mais tel que pour tous éléments , on ait et . Un morphisme de treillis est donc une application croissante qui préserve les suprémums et infimums finis.
est un treillis complet s'il admet un suprémum et un infimum sur toutes familles arbitraires d'éléments de , qui sont encore une fois uniques. Si le suprémum d'une famille est élément , on l'appellera maximum de . Si l'infimum d'une famille est élément , on l'appellera minimum de .
Les treillis peuvent être représentés avec des diagrammes de Hasse. Le produit de deux treillis, au sens des ensembles ordonnés, est lui-même un treillis. Connexions avec la topologie et la logique
Algèbres de Heyting et de Boole
Une algèbre de Heyting est un treillis borné admettant une bifonction telle que pour tous , il y ait équivalence entre et . En particulier, , ce qui fait écho à la règle du modus ponens. De fait, on appelle l'implication. Un morphisme d'algèbres de Heyting est un morphisme de treillis qui préserve l'implication. À tout algèbre de Heyting , nous définissons également la négation la fonction telle que .