Pré-commander - Preorder

En mathématiques , en particulier en théorie de l'ordre , un pré - ordre ou un quasi - ordre est une relation binaire qui est réflexive et transitive . Les préordres sont plus généraux que les relations d'équivalence et les ordres partiels (non stricts) , qui sont tous deux des cas particuliers d'un préordre : un préordre antisymétrique est un ordre partiel et un préordre symétrique est une relation d'équivalence.

Le nom de précommande vient de l'idée que les précommandes (qui ne sont pas des commandes partielles) sont des commandes « presque » (partielles), mais pas tout à fait ; ils ne sont ni nécessairement antisymétriques ni asymétriques . Parce qu'un préordre est une relation binaire, le symbole peut être utilisé comme dispositif de notation pour la relation. Cependant, parce qu'ils ne sont pas nécessairement antisymétriques, une partie de l'intuition ordinaire associée au symbole peut ne pas s'appliquer. D'autre part, un préordre peut être utilisé, de façon directe, pour définir un ordre partiel et une relation d'équivalence. Le faire, cependant, n'est pas toujours utile ou utile, selon le domaine de problème étudié. ${\style d'affichage \,\leq \,}$${\style d'affichage \,\leq \,}$

En mots, quand on peut dire que b recouvre a ou que a précède b , ou que b se réduit à a . Parfois, la notation ou est utilisée à la place de${\style d'affichage a\leq b,}$ ${\displaystyle \,\lesssim \,}$${\style d'affichage \,\leq .}$

A chaque préordre correspond un graphe orienté , avec des éléments de l'ensemble correspondant aux sommets, et la relation d'ordre entre paires d'éléments correspondant aux arêtes dirigées entre sommets. L'inverse n'est pas vrai : la plupart des graphes orientés ne sont ni réflexifs ni transitifs. En général, les graphiques correspondants peuvent contenir des cycles . Un préordre qui est antisymétrique n'a plus de cycles ; c'est un ordre partiel, et correspond à un graphe orienté acyclique . Un préordre qui est symétrique est une relation d'équivalence ; il peut être considéré comme ayant perdu les marqueurs de direction sur les bords du graphique. En général, le graphe orienté correspondant d'un préordre peut avoir de nombreux composants déconnectés.

Définition formelle

Considérons une relation homogène sur un ensemble donné de sorte que par définition, est un sous-ensemble de et la notation est utilisée à la place de Then est appelé un pré - ordre ou un quasi - ordre s'il est réflexif et transitif ; c'est-à-dire s'il satisfait : ${\style d'affichage \,\leq \,}$ ${\style d'affichage P,}$${\style d'affichage \,\leq \,}$${\style d'affichage P\fois P}$${\style d'affichage a\leq b}$${\style d'affichage (a,b)\in \,\leq .}$${\style d'affichage \,\leq \,}$

1. Réflexivité : et${\displaystyle a\leq a{\text{ for all }}a\in P,}$
2. Transitivité :${\displaystyle {\text{ if }}a\leq b{\text{ et }}b\leq c{\text{ then }}a\leq c{\text{ pour tous }}a,b,c\ dans P.}$

Un ensemble équipé d'un pré-ordre est appelé un ensemble pré - ordonné (ou proset ). Pour accentuer ou contraster les précommandes strictes , une précommande peut également être appelée précommande non stricte .

Si la réflexivité est remplacée par l' irréflexivité (tout en gardant la transitivité) alors le résultat est appelé un pré-ordre strict ; explicitement, un préordre strict sur est une relation binaire homogène sur qui satisfait les conditions suivantes : ${\style d'affichage P}$${\style d'affichage \,<\,}$${\style d'affichage P}$

1. Irréflexivité ou anti-réflexivité : c'est-à-dire, et${\displaystyle {\textit {pas}}\;a<a\;{\text{ pour tous }}a\in P;}$${\displaystyle \,a<a\;{\text{ est }}{\textit {false}}{\text{ pour tout }}a\in P,}$
2. Transitivité :${\displaystyle {\text{ if }}a<b{\text{ et }}b<c{\text{ then }}a<c{\text{ pour tous }}a,b,c\in P. }$

Une relation binaire est un pré-ordre strict si et seulement si c'est un ordre partiel strict . Par définition, un ordre partiel strict est un préordre strict asymétrique , où est dit asymétrique si pour tout Inversement, tout préordre strict est un ordre partiel strict car toute relation irréflexive transitive est nécessairement asymétrique . Bien qu'ils soient équivalents, le terme « ordre partiel strict » est généralement préféré à « pré-ordre strict » et les lecteurs sont renvoyés à l' article sur les ordres partiels stricts pour plus de détails sur ces relations. Contrairement aux précommandes strictes, il existe de nombreuses précommandes (non strictes) qui ne sont pas des commandes partielles (non strictes) . ${\style d'affichage \,<\,}$${\displaystyle a<b{\text{ implique }}{\textit {pas}}\ b<a}$${\style d'affichage a,b.}$

Définitions associées

Si un pré - commande est aussi antisymétrique , qui est, et implique alors il est un ordre partiel . ${\style d'affichage a\leq b}$${\displaystyle b\leq a}$${\style d'affichage a=b,}$

D'autre part, si elle est symétrique , c'est-à-dire si elle implique alors c'est une relation d'équivalence . ${\style d'affichage a\leq b}$${\displaystyle b\leq a,}$

Une précommande est totale si ou pour tout${\style d'affichage a\leq b}$${\displaystyle b\leq a}$${\displaystyle a,b\in P.}$

La notion d'ensemble pré-ordonné peut être formulée dans un cadre catégorique comme une catégorie mince ; c'est-à-dire comme une catégorie avec au plus un morphisme d'un objet à un autre. Ici les objets correspondent aux éléments de et il y a un morphisme pour les objets qui sont liés, zéro sinon. Alternativement, un ensemble pré-ordonné peut être compris comme une catégorie enrichie, enrichie sur la catégorie${\style d'affichage P}$${\style d'affichage P,}$${\displaystyle 2=(0\à 1).}$

Une classe précommandée est une classe équipée d'une précommande. Chaque ensemble est une classe et donc chaque ensemble pré-ordonné est une classe pré-ordonnée.

Exemples

La relation d' accessibilité dans tout graphe orienté (contenant éventuellement des cycles) donne lieu à un préordre, où dans le préordre si et seulement s'il existe un chemin de x à y dans le graphe orienté. Inversement, chaque préordre est la relation d'accessibilité d'un graphe orienté (par exemple, le graphe qui a une arête de x à y pour chaque paire ( x , y ) avec Cependant, de nombreux graphes différents peuvent avoir le même préordre d'accessibilité les uns que les autres. De la même manière, l'accessibilité des graphes acycliques orientés , graphes orientés sans cycles, donne naissance à des ensembles partiellement ordonnés (préordres satisfaisant une propriété d'antisymétrie supplémentaire). ${\style d'affichage x\leq y}$${\displaystyle x\leq y.}$

Tout espace topologique fini donne lieu à un préordre sur ses points en définissant si et seulement si x appartient à tout voisinage de y . Chaque préordre fini peut être formé comme le préordre de spécialisation d'un espace topologique de cette manière. C'est-à-dire qu'il existe une correspondance un à un entre les topologies finies et les préordres finis. Cependant, la relation entre les espaces topologiques infinis et leurs préordres de spécialisation n'est pas univoque. ${\style d'affichage x\leq y}$

Un réseau est un préordre dirigé , c'est-à-dire que chaque paire d'éléments a une borne supérieure . La définition de la convergence via des réseaux est importante en topologie , où les pré- ordres ne peuvent pas être remplacés par des ensembles partiellement ordonnés sans perdre des fonctionnalités importantes.

Autres exemples :

• La relation définie par si où f est une fonction dans un pré-ordre.${\style d'affichage x\leq y}$${\style d'affichage f(x)\leq f(y),}$
• La relation définie par s'il existe une injection de x à y . L'injection peut être remplacée par la surjection , ou tout type de fonction de préservation de la structure, telle que l' homomorphisme d'anneau ou la permutation .${\style d'affichage x\leq y}$
• La relation d' intégration pour les commandes totales dénombrables .
• La relation graphe-mineure en théorie des graphes .
• Une catégorie avec au plus un morphisme de tout objet x à tout autre objet y est un préordre. De telles catégories sont appelées minces . En ce sens, les catégories « généralisent » les préordres en autorisant plus d'une relation entre les objets : chaque morphisme est une relation de préordre distincte (nommée).

En informatique, on peut trouver des exemples des précommandes suivantes.

• Les réductions Many-one et Turing sont des précommandes sur les classes de complexité.
• Les relations de sous-typage sont généralement des pré-ordres.
• Les précommandes de simulation sont des précommandes (d'où le nom).
• Relations de réduction dans les systèmes de réécriture abstraits .
• Le préordre d' englobement sur l' ensemble de termes , défini par si un sous - terme de t est une instance de substitution de s .${\style d'affichage s\leq t}$

Exemple de précommande totale :

• Préférence , selon des modèles courants.

Les usages

Les précommandes jouent un rôle central dans plusieurs situations :

• Chaque préordre peut se voir attribuer une topologie, la topologie d'Alexandrov ; et en effet, chaque préordre sur un ensemble est en correspondance un à un avec une topologie d'Alexandrov sur cet ensemble.
• Les pré-ordres peuvent être utilisés pour définir des algèbres intérieures .
• Les précommandes fournissent la sémantique de Kripke pour certains types de logique modale .
• Les pré-ordres sont utilisés pour forcer dans la théorie des ensembles pour prouver les résultats de cohérence et d' indépendance .

Bâtiments

Chaque relation binaire sur un ensemble peut être étendue à une pré - commande sur en prenant la fermeture transitive et fermeture réflexive , la fermeture transitive indique une connexion chemin si et seulement s'il y a un - chemin de la${\style d'affichage R}$${\style d'affichage S}$${\style d'affichage S}$${\displaystyle R^{+=}.}$${\displaystyle R:xR^{+}y}$${\style d'affichage R}$${\style d'affichage x}$${\style d'affichage y.}$

Préordre résiduel gauche induit par une relation binaire

Étant donné une relation binaire, la composition complémentée forme un pré-ordre appelé résidu gauche , où désigne la relation inverse de et désigne la relation complémentaire de tandis que désigne la relation composition . ${\style d'affichage R,}$${\displaystyle R\backslash R={\overline {R^{\textsf {T}}\circ {\overline {R}}}}}$${\displaystyle R^{\textsf {T}}}$${\style d'affichage R,}$${\displaystyle {\overline {R}}}$${\style d'affichage R,}$${\style d'affichage \circ }$

Précommandes et commandes partielles sur partitions

Étant donné un préordre sur on peut définir une relation d'équivalence sur telle que ${\displaystyle \,\lesssim \,}$${\style d'affichage S}$ ${\style d'affichage \,\sim \,}$${\style d'affichage S}$

La relation résultante est réflexive puisqu'un préordre est réflexif, transitif en appliquant deux fois la transitivité du préordre, et symétrique par définition. ${\style d'affichage \,\sim \,}$

En utilisant cette relation, il est possible de construire un ordre partiel sur l'ensemble quotient de l'équivalence, l'ensemble de toutes les classes d'équivalence de Si la précommande est est l'ensemble des - cycle de classes d'équivalence: si et seulement si ou est dans un -cycle avec En tout cas, sur il est possible de définir Par la construction de cette définition est indépendante des représentants choisis et la relation correspondante est en effet bien définie. On vérifie aisément que cela donne un ensemble partiellement ordonné. ${\displaystyle S/\sim ,}$${\style d'affichage \,\sim .}$${\style d'affichage R^{+=},}$ ${\displaystyle S/\sim }$${\style d'affichage R}$${\style d'affichage x\dans [y]}$${\style d'affichage x=y}$${\style d'affichage x}$${\style d'affichage R}$${\style d'affichage y}$${\displaystyle S/\sim ,}$${\displaystyle [x]\leq [y]{\text{ si et seulement si }}x\lesssim y.}$${\style d'affichage \,\sim ,}$

A l'inverse, à partir d'un ordre partiel sur une partition d'un ensemble on peut construire un préordre sur Il existe une correspondance bijective entre les préordres et les paires (partition, ordre partiel). ${\style d'affichage S}$${\style d'affichage S.}$

Exemple : Soit une théorie formelle , qui est un ensemble de phrases avec certaines propriétés (dont les détails peuvent être trouvés dans l'article sur le sujet ). Par exemple, cela pourrait être une théorie du premier ordre (comme la théorie des ensembles de Zermelo-Fraenkel ) ou une théorie d'ordre zéro plus simple . L'une des nombreuses propriétés de est qu'il est fermé sous des conséquences logiques de sorte que, par exemple, si une phrase implique logiquement une phrase qui sera écrite au fur et à mesure alors nécessairement La relation est un préordre sur parce que toujours et quand et les deux sont vrais alors il en va de même De plus, pour tout si et seulement si ; c'est-à-dire que deux phrases sont équivalentes par rapport à si et seulement si elles sont logiquement équivalentes . Cette relation d'équivalence particulière est communément désignée par son propre propre symbole spécial et donc ce symbole peut être utilisé à la place de la classe d'équivalence d'une phrase notée se compose de toutes les phrases qui sont logiquement équivalent à (qui est, tout ce que ). L'ordre partiel sur induit par qui sera également désigné par le même symbole est caractérisé par si et seulement si où la condition de droite est indépendante du choix des représentants et des classes d'équivalence. Tout ce qui a été dit jusqu'ici peut aussi être dit de sa relation inverse L'ensemble pré-ordonné est un ensemble dirigé car if et if désigne la phrase formée par conjonction logique then et où L'ensemble partiellement ordonné est par conséquent aussi un ensemble dirigé. Voir l' algèbre de Lindenbaum-Tarski pour un exemple connexe. ${\style d'affichage S}$${\style d'affichage S}$${\style d'affichage S}$${\style d'affichage A\dans S}$${\style d'affichage B,}$${\style d'affichage A\Flèche droite B}$${\style d'affichage B\Flèche gauche A,}$${\displaystyle B\in S.}$${\style d'affichage \,\flèche gauche \,}$${\style d'affichage S}$${\style d'affichage A\Flèche gauche A}$${\style d'affichage A\flèche gauche B}$${\style d'affichage B\Flèche gauche C}$${\style d'affichage A\Flèche gauche C.}$${\style d'affichage A,B\dans S,}$ ${\style d'affichage A\sim B}$${\displaystyle A\Leftarrow B{\text{ et }}B\Leftarrow A}$${\style d'affichage \,\flèche gauche \,}$${\style d'affichage A\sim B}$${\style d'affichage A\iff B,}$${\style d'affichage \,\iff \,}$${\style d'affichage \,\sim .}$${\style d'affichage A,}$${\style d'affichage [A],}$${\style d'affichage B\dans S}$${\style d'affichage A}$${\style d'affichage B\dans S}$${\style d'affichage A\iff B}$${\displaystyle S/\sim }$${\style d'affichage \,\flèche gauche ,\,}$${\style d'affichage \,\flèche gauche ,\,}$${\style d'affichage [A]\flèche gauche [B]}$${\style d'affichage A\Flèche gauche B,}$${\style d'affichage A\dans [A]}$${\style d'affichage B\dans [B]}$${\style d'affichage \,\flèche gauche \,}$ ${\style d'affichage \,\Flèche droite .\,}$${\style d'affichage (S,\flèche gauche )}$${\style d'affichage A,B\dans S}$${\displaystyle C:=A\coin B}$ ${\style d'affichage \,\coin ,\,}$${\style d'affichage A\Flèche gauche C}$${\style d'affichage B\Flèche gauche C}$${\displaystyle C\in S.}$${\displaystyle \left(S/\sim ,\Leftarrow \right)}$

Précommandes et précommandes strictes

Précommande stricte induite par une précommande

Étant donné un préordre, une nouvelle relation peut être définie en déclarant que si et seulement si ou de manière équivalente, en utilisant la relation d'équivalence introduite ci-dessus, de sorte que la relation satisfait ${\displaystyle \,\lesssim ,}$${\style d'affichage \,<\,}$${\style d'affichage a<b}$${\displaystyle (a\lesssim b{\text{ et non }}b\lesssim a),}$${\displaystyle (a\lesssim b{\text{ et non }}a\sim b)}$

La relation est un ordre partiel strict et tout ordre partiel strict peut être le résultat d'une telle construction. Si le préordre est antisymétrique, et donc un ordre partiel, alors l'équivalence est l'égalité (c'est-à-dire ) et donc la relation de cette définition peut être reformulée comme : ${\style d'affichage \,<\,}$${\displaystyle \,\lesssim \,}$${\displaystyle a\sim b{\text{ si et seulement si }}a=b}$${\style d'affichage \,<\,}$

$${\displaystyle a<b\quad {\text{ si et seulement si }}\quad (a\leq b{\text{ et }}a\neq b)\quad \quad ({\text{if }}\ lesssim {\text{ est antisymétrique}}).}$$

Mais surtout, ce n'est pas la définition générale de la relation (c'est-à-dire qu'elle n'est pas définie comme : si et seulement si ) car si le préordre n'est pas antisymétrique, alors la relation résultante ne serait pas transitive (pensez à la façon dont les éléments non égaux équivalents relater). C'est la raison de l'utilisation du symbole " " au lieu du symbole " inférieur ou égal à " " ", ce qui pourrait prêter à confusion pour une précommande qui n'est pas antisymétrique car cela peut suggérer à tort que cela implique${\style d'affichage \,<\,}$${\style d'affichage \,<\,}$${\style d'affichage a<b}$${\displaystyle (a\lesssim b{\text{ et }}a\neq b)}$${\displaystyle \,\lesssim \,}$${\style d'affichage \,<\,}$${\style d'affichage \lesssim }$${\style d'affichage \leq }$${\style d'affichage a\leq b}$${\displaystyle a<b{\text{ ou }}a=b.}$

Précommandes induites par une précommande stricte

Avec cette construction, plusieurs préordres " " peuvent aboutir à la même relation de préordre strict donc sans plus d'informations, comme la relation d'équivalence " " ne peut pas être reconstruite à partir de " ". Les précommandes possibles sont les suivantes : ${\displaystyle \,\lesssim \,}$${\style d'affichage \,<,\,}$${\displaystyle \,\lesssim \,}$${\style d'affichage <}$

• Définir comme (c'est-à-dire prendre la clôture réflexive de la relation). Ceci donne l'ordre partiel associé à l'ordre partiel strict " " par clôture réflexive ; dans ce cas, l'équivalence est l'égalité, nous n'avons donc pas besoin des notations et${\style d'affichage a\leq b}$${\displaystyle a<b{\text{ ou }}a=b}$${\style d'affichage <}$${\displaystyle \,\lesssim \,}$${\style d'affichage \,\sim .}$
• Définir comme " " (c'est-à-dire prendre le complément inverse de la relation), ce qui correspond à définir comme " ni l'un ni l'autre " ; ces relations et ne sont en général pas transitives ; cependant, s'ils le sont, il s'agit d'une équivalence ; dans ce cas " " est un

ordre faible strict . Le pré-ordre résultant est connexe (anciennement appelé total), c'est-à-dire un pré-ordre total .${\displaystyle a\lesssim b}$${\displaystyle {\text{ not }}b<a}$${\style d'affichage a\sim b}$${\displaystyle a<b{\text{ ni }}b<a}$${\displaystyle \,\lesssim \,}$${\style d'affichage \,\sim \,}$${\style d'affichage \,\sim \,}$${\style d'affichage <}$

Nombre de précommandes

Nombre de relations binaires à n éléments de différents types

Éléments	Tout	Transitif	Réfléchi	Pré-commander	Commande partielle	Précommande totale	Commande totale	Relation d'équivalence
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65 536	3 994	4 096	355	219	75	24	15
m	2 n 2		2 n 2 − n			${\textstyle \sum _{k=0}^{n}k!}$S ( n , k )	n !	${\textstyle \sum _{k=0}^{n}}$S ( n , k )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Comme expliqué ci-dessus, il existe une correspondance 1 à 1 entre les préordres et les paires (partition, ordre partiel). Ainsi, le nombre de pré-ordres est la somme du nombre d'ordres partiels sur chaque partition. Par exemple:

• pour ${\style d'affichage n=3 :}$
  • 1 partition de 3, donnant 1 précommande
  • 3 partitions de 2 + 1 , donnant des précommandes${\style d'affichage 3\fois 3=9}$
  • 1 partition de 1 + 1 + 1 , donnant 19 précommandes
  Soit, ensemble, 29 précommandes.
• pour ${\style d'affichage n=4 :}$
  • 1 partition de 4, donnant 1 précommande
  • 7 partitions avec deux classes (4 de 3 + 1 et 3 de 2 + 2 ), donnant des précommandes${\style d'affichage 7\fois 3=21}$
  • 6 partitions de 2 + 1 + 1 , donnant des précommandes${\displaystyle 6\times 19=114}$
  • 1 partition de 1 + 1 + 1 + 1 , donnant 219 précommandes
  Soit, ensemble, 355 précommandes.

Intervalle

Car l'

intervalle est l'ensemble des points x satisfaisant et également écrit Il contient au moins les points a et b . On peut choisir d'étendre la définition à toutes les paires. Les intervalles supplémentaires sont tous vides. ${\displaystyle a\lesssim b,}$ ${\style d'affichage [a,b]}$${\displaystyle a\lesssim x}$${\style d'affichage x\lesssim b,}$${\displaystyle a\lesssim x\lesssim b.}$${\style d'affichage (a,b)}$

En utilisant la relation stricte correspondante " ", on peut également définir l'intervalle comme l'ensemble des points

x satisfaisant et également écrit Un intervalle ouvert peut être vide même si${\style d'affichage <}$${\style d'affichage (a,b)}$${\style d'affichage a<x}$${\style d'affichage x<b,}$${\style d'affichage a<x<b.}$${\style d'affichage a<b.}$

Aussi et peut être défini de la même manière. ${\style d'affichage [a,b)}$${\style d'affichage (a,b]}$

Voir également

• Ordre partiel - pré-ordre qui est antisymétrique
• Relation d'équivalence - préordre qui est symétrique
• Précommande totale – précommande totale
• Ordre total - pré-ordre qui est antisymétrique et total
• Ensemble réalisé
• Catégorie de sets pré-commandés
• Pré-commande
• Bien-quasi-ordre

Remarques

1. ^ Pour "proset", voir par exemple Eklund, Patrik; Gähler, Werner (1990), "Espaces de Cauchy généralisés", Mathematische Nachrichten , 147 : 219-233, doi : 10.1002/mana.19901470123 , MR  1127325.
2. ^ Pierce, Benjamin C. (2002). Types et langages de programmation . Cambridge, Massachusetts/Londres, Angleterre : The MIT Press. p. 182 et suiv. ISBN 0-262-16209-1.
3. ^ Kunen, Kenneth (1980), Set Theory, An Introduction to Independence Proofs , Études de logique et fondement des mathématiques, 102 , Amsterdam, Pays-Bas : Elsevier.
4. ^ Dans ce contexte, "" ne signifie pas "définir la différence".${\style d'affichage \ barre oblique inverse }$

Les références

• Schmidt, Gunther, "Mathématiques relationnelles", Encyclopédie des mathématiques et de ses applications, vol. 132, Cambridge University Press, 2011, ISBN  978-0-521-76268-7
• Schröder, Bernd SW (2002), Ordered Sets: An Introduction , Boston: Birkhäuser, ISBN 0-8176-4128-9