Incrustación de pedidos

En la teoría del orden , una rama de las matemáticas , una incrustación de orden es un tipo especial de función monótona , que proporciona una manera de incluir un conjunto parcialmente ordenado en otro. Al igual que las conexiones de Galois , las incorporaciones de orden constituyen una noción que es estrictamente más débil que el concepto de isomorfismo de orden . Ambos debilitamientos pueden entenderse en términos de la teoría de categorías .

Definicion formal

Formalmente, dados dos conjuntos parcialmente ordenados (posets) y , una función es una incrustación de orden si preserva y refleja el orden , es decir , para todos y en , uno tiene ${\displaystyle (S,\leq )}$ ${\displaystyle (T,\preceq )}$ ${\displaystyle f:S\to T}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle S}$

${\displaystyle x\leq y{\text{ if and only if }}f(x)\preceq f(y).}$^[1]

Tal función es necesariamente inyectiva , ya que implica y . ^[1] Si existe un orden de incrustación entre dos posets , se dice que se puede incrustar en . ${\displaystyle f(x)=f(y)}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq x}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$

Propiedades

Incrustación de orden mutuo de y , utilizando en ambas direcciones. ${\displaystyle (0,1)}$ ${\displaystyle [0,1]}$ ${\displaystyle f(x)=(94x+3)/100}$

El conjunto de divisores de 6, parcialmente ordenados por x divide y . La incrustación no puede ser una coretracción. ${\displaystyle S}$ ${\displaystyle id:\{1,2,3\}\to S}$

Un isomorfismo de orden se puede caracterizar como una incrustación de orden sobreyectiva . Como consecuencia, cualquier orden que incruste f se restringe a un isomorfismo entre su dominio S y su imagen f ( S ), lo que justifica el término "incrustación". ^[1] Por otro lado, bien podría ser que dos posets (necesariamente infinitos) sean mutuamente incrustables en orden entre sí sin ser isomorfos en orden.

Un ejemplo lo proporciona el intervalo abierto de números reales y el correspondiente intervalo cerrado . La función asigna el primero al subconjunto del segundo y el segundo al subconjunto del primero, ver imagen. Ordenar ambos conjuntos de forma natural preserva y refleja el orden (porque es una función afín ). Sin embargo, no puede existir ningún isomorfismo entre los dos posets, ya que, por ejemplo, tiene un elemento mínimo mientras que no lo tiene. Para ver un ejemplo similar que utiliza arctan para ordenar e incrustar los números reales en un intervalo, y el mapa de identidad para la dirección inversa, consulte, por ejemplo, Just y Weese (1996). ^[2] ${\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)}$

Una retractación es un par de mapas que preservan el orden y cuya composición es la identidad. En este caso, se llama corretracción y debe ser una orden de incrustación. ^[3] Sin embargo, no toda incorporación de órdenes es una coretracción. Como ejemplo trivial, el orden único que se incrusta desde el poset vacío a un poset no vacío no tiene retracción, porque no existe un mapa que preserve el orden . De manera más ilustrativa, considere el conjunto de divisores de 6, parcialmente ordenados por x divide y , vea la imagen. Considere el subconjunto incrustado . Una retracción de la incrustación debería enviarse a algún lugar arriba de ambos y , pero no existe tal lugar. ${\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}$

Perspectivas adicionales

Los posets se pueden ver directamente desde muchas perspectivas, y las incrustaciones de orden son lo suficientemente básicas como para ser visibles desde todas partes. Por ejemplo:

• ( Modelo teóricamente ) Un poset es un conjunto equipado con una relación binaria (reflexiva, antisimétrica y transitiva) . Un orden que incluye A → B es un isomorfismo de A a una subestructura elemental de B.
• ( Grafica teóricamente ) Un poset es un grafo (transitivo, acíclico, dirigido, reflexivo) . Un orden que incorpora A → B es un isomorfismo gráfico de A a un subgrafo inducido de B.
• ( Categoría teóricamente ) Un poset es una categoría (pequeña, delgada y esquelética) tal que cada homset tiene como máximo un elemento. Un orden que incrusta A → B es un funtor completo y fiel de A a B que es inyectivo en objetos, o de manera equivalente, un isomorfismo de A a una subcategoría completa de B.

Ver también

• Teorema de Dushnik-Miller
• teorema de laver

Referencias

1. Davey, Licenciatura en Letras; Priestley, HA (2002), "Mapas entre conjuntos ordenados", Introducción a las celosías y el orden (2ª ed.), Nueva York: Cambridge University Press, págs. 23-24, ISBN 0-521-78451-4, SEÑOR  1902334.
2. Simplemente, Winfried; Weese, Martin (1996), Descubriendo la teoría moderna de conjuntos: conceptos básicos, Monografías del Fields Institute, vol. 8, Sociedad Estadounidense de Matemáticas, pág. 21, ISBN 9780821872475
3. Duffus, Dwight; Laflamme, Claude; Pouzet, Maurice (2008), "Retracciones de posets: la propiedad de la brecha de cadena y la propiedad de selección son independientes", Algebra Universalis , 59 (1–2): 243–255, arXiv : math/0612458 , doi :10.1007/s00012 -008-2125-6, SEÑOR  2453498, S2CID  14259820.