Théorie des ordres
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
modifierSoit 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
modifierSoit 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 connexion (en), .
- La connexion forte (en), .
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
modifierLes 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é proset[1], satisfait refléxivité et transitivité.
- Un ensemble partiellement ordonné, aussi appelé poset[1], satisfait réflexivité, antisymétrie et transitivité. Il s'agit donc d'un proset particulier.
- Un ensemble totalement ordonné, aussi appelé toset[1], satisfait réflexivité, antisymétrie, transitivité, et connexion. Il s'agit donc d'un poset particulier.
- Un ensemble bien ordonné, aussi appelé woset[2], est un toset qui satisfait également .
Une relation d'ordre est le nom donné aux relation 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
modifierChaque 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 croissantes[3]. 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.
-
Diagramme commutatif décrivant un produit catégorique.
-
Diagramme commutatif décrivant un isomorphisme entre deux objets.
- 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
modifier- 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'un 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
modifierSi 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 fine[4]. 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 projections canoniques (en), 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
modifierOn 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
modifierAlgèbres de Heyting et de Boole
modifierUne 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 .
Une algèbre de Boole n'est autre qu'une algèbre de Heyting pour laquelle la négation est involutive, c'est-à-dire que pour tous .
- L'algèbre de Boole à deux éléments forme une sémantique correcte et complète de la logique classique. En réalité, l'algèbre de Lindenbaum de la logique propositionnelle classique est, elle-même, une algèbre de Boole. Cela établit une forme d'équivalence entre évaluation booléenne à deux valeurs et démonstrations en logique classique.
Les algèbres de Heyting ont également leur importance en logique, notamment de par leur utilisation en sémantique de logique intuitionniste. En effet, l'algèbre de Lindenbaum d'une logique propositionnelle intuitionniste est une algèbre de Heyting.
Il existe également une construction duale, ou opposée, aux algèbres de Heyting, dites algèbres de co-Heyting, qui admet une opération de co-implication plutôt que d'implication, à savoir une bifonction telle que pour tous , il y ait équivalence entre et , ce qui ressemble davantage au syllogisme disjonctif. Elle permet notamment de généraliser l'opération de différence ensembliste. Les algèbres de co-Heyting servent notamment en sémantique de logique dual-intuitionniste, une forme notable de logique paracohérente.
Une algèbre de bi-Heyting est une algèbre à la fois de Heyting et de co-Heyting, donc dotée à la fois d'une opération d'implication et d'une opération de différence. Elle sert notamment en sémantique des logiques bi-intuitionnistes.
Cadres et locales
modifierLes treillis sont les objets centraux de la topologie sans points. En effet, toute topologie sur est un ensemble , duquel la structure forme un treillis, plus spécifiquement un cadre. La catégorie duale à celle des cadres est celle des locales.
Par ailleurs, le théorème de représentation de Stone pour les algèbres de Boole pose l'équivalence de la catégorie des algèbres de Boole avec celle des espaces de Stone, qui sont des espaces topologiques compacts dans lesquels seuls l'ensemble vide et les singletons sont connexes.
Références
modifier- John Baez. preorder. Version 16. 9 mars 2009. url : https://ncatlab.org/nlab/revision/preorder/16.
- ↑ Toby Bartels. well-order. Version 5. 11 avr. 2009. url : https://ncatlab.org/nlab/revision/well-order/5.
- ↑ Toby Bartels. monotone function. Version 1. 14 août 2009. url : https://ncatlab.org/nlab/revision/monotone+function/1.
- ↑ Toby Bartels. thin category. Version 1. 18 août 2010. url : https://ncatlab.org/nlab/revision/thin+category/1.