Incrustaciones 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 permite incluir un conjunto parcialmente ordenado en otro. Al igual que las conexiones de Galois , las incrustaciones de orden constituyen una noción estrictamente más débil que el concepto de isomorfismo de orden . Ambas debilitaciones pueden entenderse en términos de la teoría de categorías .

Formalmente, dados dos conjuntos parcialmente ordenados (posets)${\displaystyle (S,\leq )}$y${\displaystyle (T,\preceq )}$, una función${\displaystyle f:S\to T}$es una incrustación de orden si${\displaystyle f}$es a la vez preservador y reflejo del orden , es decir, para todo${\displaystyle x}$y${\displaystyle y}$en${\displaystyle S}$, uno tiene

${\displaystyle x\leq y{\text{ si y solo si }}f(x)\preceq f(y).}$^{[ 1 ]}

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

Un isomorfismo de orden puede caracterizarse como una incrustación de orden sobreyectiva . En consecuencia, cualquier incrustación de orden 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 darse el caso de que dos conjuntos parcialmente ordenados (necesariamente infinitos) sean mutuamente incrustables en orden sin ser isomorfos en orden.

Un ejemplo lo proporciona el intervalo abierto.${\displaystyle (0,1)}$de números reales y el intervalo cerrado correspondiente${\displaystyle [0,1]}$. La función${\displaystyle f(x)=(94x+3)/100}$asigna el primero al subconjunto${\displaystyle (0.03,0.97)}$de este último y este último al subconjunto${\displaystyle [0.03,0.97]}$del primero, ver imagen. Ordenando ambos conjuntos de forma natural,${\displaystyle f}$es a la vez preservadora y reflejadora del orden (porque es una función afín ). Sin embargo, no puede existir ningún isomorfismo entre los dos conjuntos parcialmente ordenados, ya que, por ejemplo,${\displaystyle [0,1]}$tiene un elemento mínimo mientras${\displaystyle (0,1)}$No. Para un ejemplo similar que utiliza la función arcotangente para incrustar ordenadamente los números reales en un intervalo, y el mapa identidad para la dirección inversa, véase, por ejemplo, Just y Weese (1996). ^{[ 2 ]}

Una retracción es un par${\displaystyle (f,g)}$de mapas que preservan el orden cuya composición${\displaystyle g\circ f}$es la identidad. En este caso,${\displaystyle f}$se denomina coretracción y debe ser una incrustación de orden. ^{[ 3 ]} Sin embargo, no toda incrustación de orden es una coretracción. Como ejemplo trivial, la incrustación de orden única${\displaystyle f:\emptyset \to \{1\}}$La transformación de un poset vacío a un poset no vacío no tiene retracción, porque no existe una función que preserve el orden.${\displaystyle g:\{1\}\to \emptyset }$. De manera más ilustrativa, consideremos el conjunto${\displaystyle S}$de divisores de 6, parcialmente ordenados por x divide a y , ver imagen. Considere el subconjunto parcialmente ordenado incrustado.${\displaystyle \{1,2,3\}}$. Una retracción de la incrustación${\displaystyle id:\{1,2,3\}\to S}$necesitaría enviar${\displaystyle 6}$a algún lugar en${\displaystyle \{1,2,3\}}$por encima de ambos${\displaystyle 2}$y${\displaystyle 3}$, pero ese lugar no existe.

Los conjuntos parcialmente ordenados pueden verse fácilmente desde muchas perspectivas, y las incrustaciones de orden son lo suficientemente básicas como para que tiendan a ser visibles desde cualquier lugar. Por ejemplo:

• ( Teóricamente, un modelo ) Un poset es un conjunto equipado con una relación binaria (reflexiva, antisimétrica y transitiva) . Una incrustación de orden A → B es un isomorfismo de A a una subestructura elemental de B.
• ( Teoría de grafos ) Un poset es un grafo (transitivo, acíclico, dirigido, reflexivo) . Una incrustación de orden A → B es un isomorfismo de grafos de A a un subgrafo inducido de B.
• ( Categoría teórica ) Un poset es una categoría (pequeña, delgada y esquelética) tal que cada conjunto hom tiene como máximo un elemento. Una incrustación de orden A → B es un functor completo y fiel de A a B que es inyectivo en los objetos, o equivalentemente un isomorfismo de A a una subcategoría completa de B.

• Teorema de Dushnik-Miller
• Teorema de Laver