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

modifier

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

modifier

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 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

modifier

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é 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

modifier

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 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.

  • 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

modifier

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 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.

 
Diagramme commutatif décrivant une somme catégorique.

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

modifier
 
Diagramme de Hasse du 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

modifier

Algèbres de Heyting et de Boole

modifier
 
Diagramme de Hasse du treillis de Rieger-Nishimura, à savoir l'algèbre de Heyting libre engendré par un élément

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  .

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

modifier

Les 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
  1. a b et c John Baez. preorder. Version 16. 9 mars 2009. url : https://ncatlab.org/nlab/revision/preorder/16.
  2. Toby Bartels. well-order. Version 5. 11 avr. 2009. url : https://ncatlab.org/nlab/revision/well-order/5.
  3. Toby Bartels. monotone function. Version 1. 14 août 2009. url : https://ncatlab.org/nlab/revision/monotone+function/1.
  4. Toby Bartels. thin category. Version 1. 18 août 2010. url : https://ncatlab.org/nlab/revision/thin+category/1.