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

Soit $A$ un ensemble, typiquement au sens de la théorie ZFC des ensembles. Une relation binaire sur un ensemble $A$ peut être vue d'une de deux manières essentiellement équivalentes :

• En tant qu'ensemble, il s'agit d'une partie $R$ quelconque du produit cartésien $A\times A$. Par définition de ce dernier, tout élément de $z\in R$ admet $x,y\in A$ tels que $z$ puisse être exprimé comme le couple $(x,y)$.
• En tant que prédicat, il s'agit d'un prédicat binaire $ℛ$ quelconque sur $A$, dans le sens $\mathrm{\forall }x.\mathrm{\forall }y.(ℛxy\to (x\in A\mathrm{\&}y\in A))$. Toutefois, étant donné $x$ et $y$ variables de la logique du premier ordre, au lieu d'écrire $ℛxy$, nous utiliserons une notation infixée $xℛy$.

L'équivalence de ces deux notions est le résultat de ces deux propriétés :

• Soit un prédicat binaire $ℛ$ sur $A$. On peut construire de $A\times A$ la partie $R=\{z\in A\times A|\mathrm{\exists }x\in A.\mathrm{\exists }y\in A.(z=(x,y)\mathrm{\&}xℛy)\},$, qu'on peut aussi noter $R=\{(x,y)\in A\times A|xℛy\}$ plus souplement, duquel découle le théorème $⊢\mathrm{\forall }x.\mathrm{\forall }y.(xℛy\leftrightarrow (x,y)\in R)$.
• Soit une partie $R\subset A\times A$, on peut directement construire $R$ comme prédicat binaire tel que $⊢\mathrm{\forall }x.\mathrm{\forall }y.(xℛy\leftrightarrow (x,y)\in R)$.

Axiomes relationnels

Soit $\sim$ une relation sur un ensemble $A$. $(A,\sim )$ 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 $\varphi$ de la logique du premier avec la signature de la théorie ZFC, d'écrire $\mathrm{\forall }x\in A.\varphi$ et $\mathrm{\exists }x\in A.\varphi$, pour désigner $\mathrm{\forall }x.(x\in A\to \varphi )$ et $\mathrm{\exists }x.(x\in A\mathrm{\&}\varphi )$ respectivement.

• La réflexivité, $\mathrm{\forall }x\in A.x\sim x$.
• L'irréflexivité, $\mathrm{\forall }x\in A.\mathrm{\neg }x\sim x$.
• La transivité, $\mathrm{\forall }x\in A.\mathrm{\forall }y\in A.\mathrm{\forall }z\in A.((x\sim y\mathrm{\&}y\sim z)\to x\sim z)$.
• L'antisymétrie, $\mathrm{\forall }x\in A.\mathrm{\forall }y\in A.((x\sim y\mathrm{\&}y\sim x)\to x=y)$.
• L'asymétrie, $\mathrm{\forall }x\in A.\mathrm{\forall }y\in A.(x\sim y\to \mathrm{\neg }y\sim x)$.
• La Modèle:Lien, $\mathrm{\forall }x\in A.\mathrm{\forall }y\in A.((x=y\vee x\sim y\vee y\sim x))$.
• La Modèle:Lien, $\mathrm{\forall }x\in A.\mathrm{\forall }y\in A.((x\sim y\vee y\sim x))$.

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 $(A,\le )$, chacun composé d'un ensemble $A$ muni d'une relation $\le$ sur $A$. 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, 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é woset, est un toset $(A,\le )$ qui satisfait également $\mathrm{\forall }a\in P(A).(x=\varnothing \vee \mathrm{\exists }x\in a.\mathrm{\forall }y\in a.x\le y)$.

Une relation d'ordre est le nom donné aux relation d'ensembles partiellement ordonnés.

Toute relation binaire $\le$ sur $A$ réflexive admet une contrepartie stricte $⪇$ irréflexive, défini en ensemble comme $\{z\in A\times A|\mathrm{\exists }x\in A.\mathrm{\exists }y\in A.(z=(x,y)\mathrm{\&}x\le y\mathrm{\&}\mathrm{\neg }x=y)\}$., 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, $(A,{\le }_A)$ et $(B,{\le }_B)$, on peut définir des applications $f:(A,{\le }_A)\to (B,{\le }_B)$ telles que pour tous $x,y\in A$, il existe des uniques $f(x),f(y)\in B$ tels que, si $x{\le }_{A}y$, alors $f(x){\le }_{B}f(y)$. De telles applications sont dites monotones, ou isotones. Ces applications préservent alors la structure préordonnée, voire partiellement ordonnée, de ces modèles.

De tout ensemble d'axiomes relationnels $\alpha$, on remarque que la théorie axiomatique sur $\alpha$ admet une structure de catégorie, dont la classe d'objets est la classe des modèles de $\alpha$, et dont la classe de morphismes est celle des applications monotones entre deux modèles de $\alpha$ arbitraires. On appellera donc les applications isotones, 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 produit catégorique.
• Diagramme commutatif décrivant un isomorphisme entre deux objets.
  Diagramme commutatif décrivant un isomorphisme entre deux objets.

• Un endomorphisme d'ensembles ordonnés est une application isotone d'un ensemble ordonné dans lui-même.
• Deux ensembles ordonnés $(A,{\le }_A)$ et $(B,{\le }_B)$ sont isomorphes si existent des applications isotones $f:(A,{\le }_A)\to (B,{\le }_B)$ et $g:(B,{\le }_B)\to (A,{\le }_A)$ telles que $g\circ f={\text{id}}_{(A,{\le }_A)}$ et $f\circ g={\text{id}}_{(B,{\le }_B)}$, qui sont alors appelées isomorphismes, et morphismes inverses l'un de l'autre.
• Un squelette de la catégorie des modèles de $\alpha$ 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 $(\varnothing ,\varnothing )$, et ses objets finaux $(\{*\},=)$ les singletons munis de l'égalité.
  • Le produit d'une famille ${((A_i,{\le }_{A_i}))}_{i\in I}$ est donné par la structure $(\prod _{i\in I}{A}_i,\prod _{i\in I}{\le }_{A_i})$, qui elle-même est un ensemble ordonné, et dont $\prod _{i\in I}{\le }_{A_i}$ 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 $\mathbb{N}$ (aussi appelé $\omega$), dans leurs constructions ensemblistes à la von Neumann.
• $\mathbb{Z}$, $\mathbb{Q}$ et $ℝ$ munis d'un des relations $\le$ ou $\ge$ sont des ensembles totalement ordonnés, mais ne sont pas bien ordonnés.
• $\mathbb{N}$ muni de la relation de factorisabilité forme un ensemble partiellement ordonné. Il n'est cependant pas connecté. Un contre-exemple est donné par $2$ qui ni ne factorise, ni n'est factorisé par, ni n'est égal à $3$.
• Lorsque l'on étend cette relation aux entiers relatifs, $\mathbb{Z}$ 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 $-1|1$ et $1|-1$, et ce, bien que $-1\ne 1$.
• Étant donné un ensemble ordonnée $(A,\le )$, si une partie $B\subset A$ munie de la restriction $\le {|}_B$ de $\le$ à $B$ forme $(B,\le {|}_B)$ est un ensemble totalement ordonné, on dit alors que $(B,\le {|}_B)$ est une chaîne de $(A,\le )$. D'un autre côté, on dit de $(B,\le {|}_B)$ que c'est une antichaîne si ses éléments sont incomparables deux à deux, c'est-à-dire que pour tous $a,b\in B$ distincts, ni $a\le b$, ni $b\le a$. Le cardinal de la plus grande antichaîne de $(A,\le )$ 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é $(A,\le )$ admet sa propre catégorie associée. Sa classe d'objets est $A$, et ses morphismes sont les parties de l'ensemble associé à $\le$ 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 $\circ$ telle que, pour tous éléments $a\le b\le c$ de $A$, on ait $\{(b,c)\}\circ \{(a,b)\}=\{(a,c)\}$. Par réflexivité, les morphismes identités existent et sont les $\{(a,a)\}\subset \le$ tels que $a\in A$. 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 $A$, on dit de la catégorie associée à $(A,\le )$ qu'elle est fine. 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 $a,a^{\prime }\in A$ sont isomorphes si et seulement si $a\le a^{\prime }\mathrm{\&}{a}^{\prime }\le a$. Si $(A,\le )$ est un ensemble partiellement ordonné, on a alors comme seuls isomorphismes les égalités, d'où $(A,\le )$ 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 $(A,\le )$ 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 $(A,\le )$, s'il existe, est l'élément $\mathrm{\top }\in A$ tel que, pour tout $a\in A$, il existe un morphisme $a\to \mathrm{\top }$. 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 $\mathrm{\perp }\in A$ tel que, pour tout $a\in A$, il existe un morphisme $\mathrm{\perp }\to a$.

Le produit catégorique dans $(A,\le )$, d'une famille $ℱ=\{a_i{\}}_{i\in I}\subset A$, si il existe, est l'élément $a\in A$ tel que $a\le a_i$ pour tout $i\in I$, où les morphismes associés $\{(a,a_i)\}$ servent alors de Modèle:Lien, et tel que pour tout $a^{\prime }\in A$, si $a^{\prime }\le a_i$ pour tout $i\in I$, alors $a^{\prime }\le a$. Intuitivement, il s'agit alors du plus grand minorant de la famille. On écrit généralement $a=\bigwedge ℱ$, que l'on appelle alors l'infimum de $ℱ$, ou minimum de $ℱ$ s'il s'agit d'un élément de $ℱ$. L'opération $\bigwedge$ est parfois appelée rencontre.

Fichier:Coproduct-01.svg

Diagramme commutatif décrivant une somme catégorique.

La somme catégorique dans $(A,\le )$ d'une famille $ℱ=\{a_i{\}}_{i\in I}\subset A$, 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 $a\in A$ tel que $a_i\le a$ pour tout $i\in I$, où les morphismes associés $\{(a_i,a)\}$ servent alors de co-projections canoniques, et tel que pour tout $a^{\prime }\in A$, si $a_i\le a^{\prime }$ pour tout $i\in I$, alors $a\le a^{\prime }$. Intuitivement, il s'agit alors du plus petit majorant de la famille. On écrit généralement $a=\bigvee ℱ$, que l'on appelle alors supremum de $ℱ$, ou maximum de $ℱ$ s'il s'agit d'un élément de $ℱ$. L'opération $\bigvee$ est parfois appelée jointure.

On dit d'un ensemble partiellement ordonné $(A,\le )$ qu'il est borné s'il admet un objet final, appelé son élément maximal ou maximum de $A$, et un objet initial, appelé son élément minimal ou minimum de $A$.

Treillis

Fichier:Hasse diagram of powerset of 3.svg

Diagramme de Hasse du treillis $(P(\{x,y,z\}),\subseteq )$.

On dira de $(A,\le )$ qu'il est un treillis si, pour tous éléments $a,b\in A$, il existe un infimum et un suprémum de $\{a,b\}$, qu'on note respectivement $a\wedge b$ et $a\vee b$. Dans un treillis, qu'il soit borné ou non, si $a\wedge b=a$ ou $a\vee b=b$ (équivalents), on dira que $a$ est le minimum de $a$ et $b$. De même, si $a\wedge b=b$ ou $a\vee b=a$ (équivalents), on dira que $a$ est le maximum de $a$ et $b$. À noter que $a\le b$ équivaut à $a\wedge b=a$ et $a\vee b=b$.

A contrario d'autres théories d'axiomes relationnels, la catégorie des treillis est généralement défini de sorte à ce que chaque morphisme de treillis $f:(A,{\le }_A)\to (B,{\le }_B)$ soit non seulement isotone, mais tel que pour tous éléments $a,b\in A$, on ait $f(a\wedge b)=f(a)\wedge f(b)$ et $f(a\vee b)=f(a)\vee f(b)$. Un morphisme de treillis est donc une application isotone qui préserve les suprémums et infimums finis.

$(A,\le )$ est un treillis complet s'il admet un suprémum et un infimum sur toutes familles arbitraires d'éléments de $A$, qui sont encore une fois uniques. Si le suprémum d'une famille $ℱ\subset A$ est élément $ℱ$, on l'appellera maximum de $ℱ$. Si l'infimum d'une famille $ℱ\subset A$ 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

Fichier:Rieger-Nishimura.svg

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é $(A,\le )$ admettant une bifonction $\Rightarrow :A\times A\to A$ telle que pour tous $a,b,c\in A$, il y ait équivalence entre $c\wedge a\le b$ et $c\le a\Rightarrow b$. En particulier, $a\wedge (a\Rightarrow b)\le b$, ce qui fait écho à la règle du modus ponens. De fait, on appelle $\Rightarrow$ l'implication.

• Un morphisme d'algèbres de Heyting est un morphisme de treillis qui préserve l'implication.
• À tout algèbre de Heyting $(A,\le )$, nous définissons également la négation $\mathrm{\neg }:A\to A$ la fonction telle que $\mathrm{\neg }:a\mapsto a\Rightarrow \mathrm{\perp }$.

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 $\mathrm{\neg }\mathrm{\neg }a=a$ pour tous $a\in A$.

• L'algèbre de Boole à deux éléments, à isomorphisme près, forme une sémantique complète et saine 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 $\setminus :A\times A\to A$ telle que pour tous $a,b,c\in A$, il y ait équivalence entre $b\le a\vee c$ et $b\setminus a\le c$, 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

Les treillis sont les objets centraux de la topologie sans points. En effet, toute topologie sur $X$ est un ensemble ${\mathrm{\Omega }}_X$, duquel la structure $({\mathrm{\Omega }}_X,\subset )$ 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.