En matemáticas , especialmente la teoría del orden , un conjunto parcialmente ordenado (también poset ) formaliza y generaliza el concepto intuitivo de un orden, secuencia o disposición de los elementos de un conjunto . Un poset consiste en un conjunto junto con una relación binaria que indica que, para ciertos pares de elementos en el conjunto, uno de los elementos precede al otro en el orden. La relación en sí misma se llama "orden parcial". La palabra parcialen los nombres "orden parcial" y "conjunto parcialmente ordenado" se utiliza como una indicación de que no todos los pares de elementos deben ser comparables. Es decir, puede haber pares de elementos para los cuales ninguno de los elementos precede al otro en el poset. Los pedidos parciales generalizan los pedidos totales , en los que cada par es comparable.
Formalmente, un orden parcial es cualquier relación binaria que es reflexiva (cada elemento es comparable a sí mismo), antisimétrica (no hay dos elementos diferentes que se precedan entre sí) y transitiva (el inicio de una cadena de relaciones de precedencia debe preceder al final de la cadena )
Un ejemplo familiar de un conjunto parcialmente ordenado es una colección de personas ordenadas por descendencia genealógica . Algunas parejas de personas llevan la relación descendiente-ancestro, pero otros pares de la gente son incomparables, con ni ser un descendiente de la otra.
Un poset se puede visualizar a través de su diagrama de Hasse , que representa la relación de ordenamiento.
Definición formal [ editar ]
Un orden parcial (no estricto) [2] es una relación binaria ≤ sobre un conjunto P que satisface axiomas particulares que se analizan a continuación. Cuando a ≤ b , decimos que a está relacionado con b . (Esto no implica que b también esté relacionado con a , porque la relación no necesita ser simétrica ).
Los axiomas para un orden parcial no estricto establecen que la relación ≤ es reflexiva , antisimétrica y transitiva . Es decir, para todo un , b , y c en P , debe satisfacer:
- a ≤ a ( reflexividad : cada elemento está relacionado con sí mismo).
- si a ≤ b y b ≤ a , entonces a = b ( antisimetría : dos elementos distintos no pueden relacionarse en ambas direcciones).
- si a ≤ b y b ≤ c , entonces a ≤ c ( transitividad : si un primer elemento está relacionado con un segundo elemento y, a su vez, ese elemento está relacionado con un tercer elemento, entonces el primer elemento está relacionado con el tercero elemento).
Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado (también denominado poset ). El término conjunto ordenado a veces también se usa, siempre y cuando quede claro por el contexto que no se entiende ningún otro tipo de orden. En particular, los conjuntos totalmente ordenados también pueden denominarse "conjuntos ordenados", especialmente en áreas donde estas estructuras son más comunes que los posets.
Para a, b , elementos de un conjunto parcialmente ordenado P , si un ≤ b o b ≤ una , a continuación, una y b son comparables . De lo contrario son incomparables . En la figura superior derecha, por ejemplo, {x} y {x, y, z} son comparables, mientras que {x} e {y} no lo son. Un orden parcial bajo el cual cada par de elementos es comparable se llama orden total u orden lineal ; un conjunto totalmente ordenado también se llama cadena(por ejemplo, los números naturales con su orden estándar). Un subconjunto de un poset en el que no hay dos elementos distintos comparables se llama antichain (por ejemplo, el conjunto de singletons {{x}, {y}, {z}} en la figura superior derecha). Un elemento una se dice que es estrictamente inferior a un elemento b, si un ≤ b y un ≠ b . Se dice que un elemento a está cubierto por otro elemento b , escrito a ⋖ b (o a <: font="" nbsp="">b ), si a es estrictamente menor que by ningún tercer elemento c cabe entre ellos; formalmente: si tanto a ≤ b como a ≠ b son verdaderos, y a ≤ c ≤ b es falso para cada c con a ≠ c ≠ b . Una definición más concisa se dará a continuación utilizando el orden estricto correspondiente a "≤". Por ejemplo, {x} está cubierto por {x, z} en la figura superior derecha, pero no por {x, y, z}.
Ejemplos [ editar ]
Los ejemplos estándar de posets que surgen en matemáticas incluyen:
- Los números reales ordenados por la relación estándar menor o igual ≤ (un conjunto totalmente ordenado también).
- El conjunto de subconjuntos de un conjunto dado (su conjunto de potencia ) ordenados por inclusión (ver la figura en la parte superior derecha). Del mismo modo, el conjunto de secuencias ordenadas por subsecuencia y el conjunto de cadenas ordenadas por subcadena .
- El conjunto de números naturales equipados con la relación de divisibilidad .
- El conjunto de vértices de un gráfico acíclico dirigido ordenado por accesibilidad .
- El conjunto de subespacios de un espacio vectorial ordenado por inclusión.
- Para un conjunto P parcialmente ordenado , el espacio de secuencia que contiene todas las secuencias de elementos de P , donde la secuencia a precede a la secuencia b si cada elemento en a precede al elemento correspondiente en b . Formalmente, ( a n ) n ∈ℕ ≤ ( b n ) n ∈ℕ si y solo si a n ≤ b n para todo n en ℕ, es decir, un orden componente .
- Para un conjunto X y un conjunto parcialmente ordenado P , el espacio funcional que contiene todas las funciones de X a P , donde f ≤ g si y sólo si f ( x ) ≤ g ( x ) para todo x en X .
- Una cerca , un conjunto parcialmente ordenado definido por una secuencia alterna de relaciones de orden a < b > c < d ...
- El conjunto de eventos en relatividad especial y, en la mayoría de los casos, [3] relatividad general , donde para dos eventos X e Y, X ≤ Y si y solo si Y está en el futuro cono de luz de X. Un evento Y solo puede ser afectado causalmente por X si X ≤ Y.
Extrema [ editar ]
Hay varias nociones de elemento "mayor" y "menor" en un poset P , en particular:
- El elemento más grande y el elemento menos: un elemento g en P es un elemento más grande si para cada elemento a en P , a ≤ g . Un elemento m en P es un elemento mínimo si para cada elemento a en P , a ≥ m . Un poset solo puede tener un elemento mayor o menor.
- Elementos máximos y elementos mínimos: un elemento g en P es un elemento máximo si no hay un elemento a en P tal que a > g . De manera similar, un elemento m en P es un elemento mínimo si no hay un elemento a en P tal que a < m . Si un poset tiene un elemento más grande, debe ser el elemento máximo único, pero de lo contrario puede haber más de un elemento máximo, y de manera similar para elementos mínimos y elementos mínimos.
- Límites superior e inferior : Para un subconjunto A de P , un elemento x en P es un límite superior de A si un ≤ x , para cada elemento de una en una . En particular, x no necesitan estar en un ser un límite superior de A . Del mismo modo, un elemento x en P es un límite inferior de A si un ≥ x , para cada elemento de una en una . Un gran elemento de P es un límite superior deP sí mismo, y un elemento de menos es un límite inferior de P .
Por ejemplo, considere los enteros positivos , ordenados por divisibilidad: 1 es un elemento mínimo, ya que divide todos los demás elementos; por otro lado, este poset no tiene un elemento mayor (aunque si se incluyera 0 en el poset, que es un múltiplo de cualquier número entero, ese sería un elemento mayor; ver figura). Este conjunto parcialmente ordenado ni siquiera tiene elementos máximos, ya que cualquier g divide, por ejemplo, 2 g , que es distinto de él, por lo que g no es máximo. Si se excluye el número 1, mientras se mantiene la divisibilidad como orden en los elementos mayores que 1, entonces el poset resultante no tiene un elemento mínimo, sino un número primoEs un elemento mínimo para ello. En este poset, 60 es un límite superior (aunque no un límite superior) del subconjunto {2,3,5,10}, que no tiene ningún límite inferior (ya que 1 no está en el poset); por otro lado, 2 es un límite inferior del subconjunto de potencias de 2, que no tiene ningún límite superior.
Órdenes en el producto cartesiano de conjuntos parcialmente ordenados [ editar ]
En orden de resistencia creciente, es decir, conjuntos de pares decrecientes, tres de los posibles pedidos parciales en el producto cartesiano de dos conjuntos parcialmente ordenados son (ver figuras):
- el orden lexicográfico : ( a , b ) ≤ ( c , d ) si a < c o ( a = c y b ≤ d );
- el pedido del producto : ( a , b ) ≤ ( c , d ) si a ≤ c y b ≤ d ;
- El cierre reflexivo del producto directo de las órdenes estrictas correspondientes: ( a , b ) ≤ ( c , d ) if ( a < c y b < d ) o ( a = c y b = d ).
Los tres se pueden definir de manera similar para el producto cartesiano de más de dos conjuntos.
Aplicado a espacios vectoriales ordenados sobre el mismo campo , el resultado es en cada caso también un espacio vectorial ordenado.
Sumas de conjuntos parcialmente ordenados [ editar ]
Otra forma de combinar dos posets es la suma ordinal [4] (o suma lineal [5] ), Z = X ⊕ Y , definida en la unión de los conjuntos subyacentes X e Y por el orden a ≤ Z b si y solo si :
- a , b ∈ X con a ≤ X b , o
- a , b ∈ Y con a ≤ Y b , o
- un ∈ X y b ∈ Y .
Si dos posets están bien ordenados , entonces también lo está su suma ordinal. [6] La operación de suma ordinal es una de las dos operaciones que se utilizan para formar órdenes parciales paralelas en serie , y en este contexto se denomina composición en serie. La otra operación utilizada para formar estos pedidos, la unión disjunta de dos conjuntos parcialmente ordenados (sin relación de orden entre los elementos de un conjunto y los elementos del otro conjunto) se llama en este contexto composición paralela.
Órdenes parciales estrictas y no estrictas [ editar ]
En algunos contextos, el orden parcial definido anteriormente se denomina no estricto (o reflexiva ) orden parcial . En estos contextos, un estricto (o irreflexive ) orden parcial "<" es una relación binaria que es irreflexive , transitiva y asimétrica , es decir, que satisface para todos un , b , y c en P :
- no a (irreflexividad),
- si a y b
entonces a (transitividad), y - si a entonces no b (asimetría; implicada por irreflexividad y transitividad [7] ).
Las órdenes parciales estrictas y no estrictas están estrechamente relacionadas. Un orden parcial no estricto puede convertirse en un orden parcial estricto eliminando todas las relaciones de la forma a ≤ a . Por el contrario, un orden parcial estricto se puede convertir en un orden parcial no estricto al unir todas las relaciones de esa forma. Por lo tanto, si "≤" es un orden parcial no estricto, entonces el orden parcial estricto correspondiente "<" es el núcleo irreflexivo dado por:
- a < b si a ≤ b y a ≠ b
Por el contrario, si "<" es un orden parcial estricto, entonces el correspondiente orden parcial no estricto "≤" es el cierre reflexivo dado por:
- a ≤ b si a < b o a = b .
Esta es la razón para usar la notación "≤".
Usando el orden estricto "<", la relación " a está cubierta por b " puede reformularse de manera equivalente como " a < b , pero no a < c < b para ninguna c ". Los órdenes parciales estrictos son útiles porque corresponden más directamente a los gráficos acíclicos dirigidos (dags): cada orden parcial estricto es un dag, y el cierre transitivo de un dag es tanto un orden parcial estricto como también un dag en sí mismo.
Inverso y orden dual [ editar ]
El inverso (o inverso) de una relación de orden parcial ≤ es el inverso de ≤. Típicamente denotado ≥, es la relación que satisface x ≥ y si y solo si y ≤ x . La inversa de una relación de orden parcial es reflexiva, transitiva y antisimétrica y, por lo tanto, es una relación de orden parcial. El orden dual de un conjunto parcialmente ordenado es el mismo conjunto con la relación de orden parcial reemplazada por su inverso. La relación irreflexiva> es a ≥ como
Cualquiera de las cuatro relaciones ≤, <, ≥ y> en un conjunto determinado determina de forma única las otras tres.
En general, dos elementos x e y de un orden parcial pueden estar en cualquiera de las cuatro relaciones mutuamente excluyentes entre sí: x < y , o x = y , o x > y , o x e y son incomparables (ninguno de los otros Tres). Un conjunto totalmente ordenado es aquel que descarta esta cuarta posibilidad: todos los pares de elementos son comparables y luego decimos que la tricotomía es válida. Los números naturales , los enteros , los racionales y ellos reales están totalmente ordenados por su magnitud algebraica (con signo) mientras que los números complejos no lo están. Esto no quiere decir que los números complejos no se puedan ordenar totalmente; podríamos, por ejemplo, ordenarlos lexicográficamente a través de x + i y < u + i v si y solo si x < u o ( x = u e y < v ), pero esto no está ordenando por magnitud en ningún sentido razonable, ya que tiene 1 mayor que 100 i. Ordenarlos por magnitud absoluta produce un preorden en el que todos los pares son comparables, pero este no es un orden parcial ya que 1 y yo tenemos la misma magnitud absoluta pero no son iguales, violando la antisimetría.
Mapeos entre conjuntos parcialmente ordenados [ editar ]
Dados dos conjuntos parcialmente ordenados ( S , ≤) y ( T , ≤), una función f : S → T se llama preservar el orden , o monótono , o isotono , si para todo x e y en S , x ≤ y implica f ( x ) ≤ f ( y ). Si ( U , ≤) es también un conjunto parcialmente ordenado, y ambos f : S → T y g : T →U conserva el orden, su composición ( g ∘ f ): S → U también preserva el orden. Una función f : S → T se llama orden de reflexión si para todo x e y en S , f ( x ) ≤ f ( y ) implica x ≤ y . Si f es a la vez preservación del orden y reflejo del orden, entonces se denomina incrustación del orden de ( S , ≤) en (T , ≤). En el último caso, f es necesariamente inyectiva , ya que f ( x ) = f ( y ) implica x ≤ y e y ≤ x . Si una orden-incrustación de entre dos Posets S y T existe, se dice que S puede ser incrustado en T . Si una incrustación de orden f : S → T es biyectiva , se llama isomorfismo de orden y los órdenes parciales ( S, ≤) y ( T , ≤) se dice que son isomorfos . Las órdenes isomorfas tienen diagramas de Hasse estructuralmente similares (véase la imagen de la derecha). Se puede demostrar que si los mapas de preservación del orden f : S → T y g : T → S existen de manera tal que g ∘ f y f ∘ g producen la función de identidad en S y T , respectivamente, entonces S y T son isomórficos de orden . [8]
Por ejemplo, un mapeo f : ℕ → ℙ (ℕ) del conjunto de números naturales (ordenados por divisibilidad) al conjunto de potencias de números naturales (ordenados por inclusión de conjunto) se puede definir llevando cada número al conjunto de su primo divisores . Preserva el orden: si x divide y , entonces cada divisor primo de x también es un divisor primo de y . Sin embargo, no es inyectiva (ya que asigna 12 y 6 a {2,3}) ni refleja el orden (ya que además de 12 no divide 6). En cambio, tomar cada número al conjunto de sus divisores de potencia primarios define un mapa g: ℕ → ℙ (ℕ) que preserva el orden, refleja el orden y, por lo tanto, incrusta el orden. No es un isomorfismo de orden (ya que, por ejemplo, no asigna ningún número al conjunto {4}), pero puede hacerse uno restringiendo su codominio a g (ℕ). La imagen de la derecha muestra un subconjunto de ℕ y su imagen isomorfa bajo g . La construcción de tal orden-isomorfismo en un conjunto de potencia se puede generalizar a una amplia clase de órdenes parciales, llamadas redes distributivas , ver " Teorema de representación de Birkhoff ".
Número de pedidos parciales [ editar ]
La secuencia A001035 en OEIS proporciona el número de órdenes parciales en un conjunto de n elementos etiquetados:
| Elementos | Ninguna | Transitivo | Reflexivo | Hacer un pedido | Orden parcial | Pedido total | Orden total | Relación de equivalencia |
|---|---|---|---|---|---|---|---|---|
| 0 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | dieciséis | 13 | 4 4 | 4 4 | 3 | 3 | 2 | 2 |
| 3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 6 | 5 5 |
| 4 4 | 65,536 | 3,994 | 4,096 | 355 | 219 | 75 | 24 | 15 |
| norte | 2 n 2 | 2 n 2 - n | ∑ n k = 0 k ! S ( n , k ) | n ! | ∑ n k = 0 S ( n , k ) | |||
| OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
El número de órdenes parciales estrictas es el mismo que el de las órdenes parciales.
Si el recuento se realiza solo hasta el isomorfismo, se obtiene la secuencia 1, 1, 2, 5, 16, 63, 318, ... (secuencia A000112 en el OEIS ).
Extensión lineal [ editar ]
Un orden parcial ≤ * en un conjunto X es una extensión de otro orden parcial ≤ en X siempre que para todos los elementos x e y de X , siempre que x ≤ y , también sea el caso de que x ≤ * y . Una extensión lineal es una extensión que también es un orden lineal (es decir, total). Cada orden parcial puede extenderse a una orden total ( principio de extensión de orden ). [9]
En informática , los algoritmos para encontrar extensiones lineales de órdenes parciales (representados como órdenes de accesibilidad de gráficos acíclicos dirigidos ) se denominan clasificación topológica .
En teoría de la categoría [ editar ]
Cada poset (y cada preorden ) se puede considerar como una categoría donde, para los objetos x e y , existe como máximo un morfismo de x a y . Más explícitamente, sea hom ( x , y ) = {( x , y )} if x ≤ y (y de lo contrario el conjunto vacío) y ( y , z ) ∘ ( x , y ) = ( x , z ). Tales categorías a veces se llaman posetales .
Los posets son equivalentes entre sí si y solo si son isomórficos . En un poset, el elemento más pequeño, si existe, es un objeto inicial , y el elemento más grande, si existe, es un objeto terminal . Además, cada conjunto preordenado es equivalente a un poset. Finalmente, cada subcategoría de un poset está cerrada por isomorfismo .
Ordenes parciales en espacios topológicos [ editar ]
Si P es un conjunto parcialmente ordenado al que también se le ha dado la estructura de un espacio topológico , entonces se acostumbra suponer que {( a , b ): a ≤ b } es un subconjunto cerrado del espacio del producto topológico . Bajo este supuesto, las relaciones de orden parcial se comportan bien en los límites en el sentido de que si, y a i ≤ b i para todo i , entonces a ≤ b . [10]
Intervalos [ editar ]
Un intervalo en un poset P es un subconjunto I de P con la propiedad de que, para cualquier x y y en I y cualquier z en P , si x ≤ z ≤ y , a continuación, z es también en I . (Esta definición generaliza la definición de intervalo para números reales).
Para a ≤ b , el intervalo cerrado [ a , b ] es el conjunto de elementos x que satisfacen a ≤ x ≤ b (es decir, a ≤ x y x ≤ b ). Contiene al menos los elementos una y b .
Usando la correspondiente relación estricta "<", el intervalo abierto ( a , b ) es el conjunto de elementos x que satisfacen a < x < b (es decir, a < x y x < b ). Un intervalo abierto puede estar vacío incluso si a < b . Por ejemplo, el intervalo abierto (1, 2) en los enteros está vacío ya que no hay enteros I tales que 1 < I <2 font=""> .
Los intervalos medio abiertos [ a , b ) y ( a , b ] se definen de manera similar.
Algunas veces las definiciones se extienden para permitir a > b , en cuyo caso el intervalo está vacío.
Un intervalo I está delimitado si existen elementos a y b de P de modo que I ⊆ [ a , b ] . Obviamente, cada intervalo que se puede representar en notación de intervalo está limitado, pero lo contrario no es cierto. Por ejemplo, sea P = (0, 1) ∪ (1, 2) ∪ (2, 3) como un subconjunto de los números reales . El subconjunto (1, 2) es un intervalo acotado, pero no tiene infimum o supremum en P, Por lo que no se puede escribir en notación de intervalos usando elementos de P .
Un poset se llama localmente finito si cada intervalo acotado es finito. Por ejemplo, los enteros son localmente finitos bajo su ordenamiento natural. El orden lexicográfico del producto cartesiano ℕ × ℕ no es localmente finito, ya que (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Usando la notación de intervalo, la propiedad " a está cubierta por b " se puede reformular de manera equivalente como [ a , b ] = { a , b }.
No hay comentarios:
Publicar un comentario