Intégration de la commande - Order embedding

Dans la théorie des ordres , une branche des mathématiques , une incorporation d'ordre est un type spécial de fonction monotone , qui fournit un moyen d'inclure un ensemble partiellement ordonné dans un autre. Comme les connexions galoisiennes , les plongements d'ordre constituent une notion strictement plus faible que le concept d' isomorphisme d'ordre . Ces deux affaiblissements peuvent être compris en termes de théorie des catégories .

Définition formelle

Formellement, étant donné deux ensembles partiellement ordonnés (les Posets) et , une fonction est un ordre enrobage si est à la fois afin de préservation et de l' ordre de réflexion , soit pour l' ensemble et dans , on a ${\ displaystyle (S, \ leq)}$${\ displaystyle (T, \ preceq)}$ ${\ displaystyle f: S \ à T}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle S}$

${\ displaystyle x \ leq y {\ text {si et seulement si}} f (x) \ preceq f (y).}$

Une telle fonction est nécessairement injective , puisqu'elle implique et . Si un ordre s'insérant entre deux posets et existe, on dit qu'il peut y être intégré . ${\ Displaystyle f (x) = f (y)}$${\ displaystyle x \ leq y}$${\ displaystyle y \ leq x}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S}$${\ displaystyle T}$

Propriétés

Intégration de l'ordre mutuel de et , utilisation dans les deux sens. ${\ displaystyle (0,1)}$${\ displaystyle [0,1]}$${\ displaystyle f (x) = (94x + 3) / 100}$

L'ensemble des diviseurs de 6, partiellement ordonnés par x divise y . L'incorporation ne peut pas être une coretraction. ${\ displaystyle S}$${\ Displaystyle id: \ {1,2,3 \} \ to S}$

Un isomorphisme d'ordre peut être caractérisé comme un encastrement d'ordre surjectif . En conséquence, tout ordre d'enfouissement f se limite à un isomorphisme entre son domaine S et son image f ( S ), ce qui justifie le terme «embeddage». D'un autre côté, il se pourrait bien que deux posets (nécessairement infinis) soient mutuellement insérables l'un dans l'autre sans être isomorphes d'ordre.

Un exemple est fourni par l' intervalle ouvert des nombres réels et l' intervalle fermé correspondant . La fonction mappe le premier au sous - ensemble du second et le second au sous-ensemble du premier, voir l'image. Ordonner les deux ensembles de manière naturelle est à la fois préservant l'ordre et reflétant l'ordre (car il s'agit d'une fonction affine ). Pourtant, aucun isomorphisme entre les deux posets ne peut exister, puisque par exemple a un moindre élément alors qu'il n'en a pas. Pour un exemple similaire utilisant arctan pour ordonner les nombres réels dans un intervalle, et la carte d'identité pour la direction inverse, voir par exemple Just et Weese (1996). ${\ displaystyle (0,1)}$ ${\ displaystyle [0,1]}$${\ displaystyle f (x) = (94x + 3) / 100}$ ${\ displaystyle (0.03,0.97)}$${\ displaystyle [0.03,0.97]}$${\ displaystyle f}$${\ displaystyle [0,1]}$${\ displaystyle (0,1)}$

Un retrait est une paire de cartes préservant l'ordre dont la composition est l'identité. Dans ce cas, s'appelle une coretraction et doit être une incorporation d'ordre. Cependant, toutes les incorporations d'ordre ne sont pas une coretraction. À titre d'exemple trivial, l'ordre unique d'incorporation du poset vide à un poset non vide n'a pas de retrait, car il n'y a pas de carte de préservation de l'ordre . De manière plus illustrative, considérons l'ensemble des diviseurs de 6, partiellement ordonnés par x divise y , voir l'image. Considérez le sous-poste intégré . Un retrait de l'incorporation devrait être envoyé quelque part au- dessus des deux et , mais il n'y a pas un tel endroit. ${\ displaystyle (f, g)}$ ${\ displaystyle g \ circ f}$${\ displaystyle f}$${\ displaystyle f: \ emptyset \ to \ {1 \}}$${\ displaystyle g: \ {1 \} \ to \ emptyset}$${\ displaystyle S}$ ${\ displaystyle \ {1,2,3 \}}$${\ Displaystyle id: \ {1,2,3 \} \ to S}$${\ displaystyle 6}$${\ displaystyle \ {1,2,3 \}}$${\ displaystyle 2}$${\ displaystyle 3}$

Perspectives supplémentaires

Les positions peuvent être directement visualisées sous de nombreux angles, et les incorporations de commandes sont suffisamment basiques pour qu'elles aient tendance à être visibles de partout. Par exemple:

• ( Modéliser théoriquement ) Un poset est un ensemble équipé d'une relation binaire (réflexive, antisymétrique et transitive) . Un ordre enrobage A → B est un isomorphisme de A à une sous - structure élémentaire de B .
• ( Graphique théorique ) Un poset est un (transitive, acyclique dirigé, réflexif) graphique . Un ordre enrobage A → B est un isomorphisme de graphe de A à un sous - graphe induit de B .
• ( Catégorie théoriquement ) A poset est un (petit, mince et squelettique) catégorie de telle sorte que chaque homset a au plus un seul élément. Un ordre enrobage A → B est une complète et fidèle foncteur de A à B , qui est injective sur les objets, ou de manière équivalente un isomorphisme de A à une sous - catégorie pleine de B .

Voir également

• Théorème de Dushnik-Miller
• Théorème de Laver

Références