Conjunto parcialmente ordenado - Partially ordered set
Relaciones binarias transitivas | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : A " " indica que la propiedad de la columna es requerida por la definición del término de la fila (en el extremo izquierdo). Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Aquí se enumeran las propiedades adicionales que puede satisfacer una relación homogénea.
|
En matemáticas , especialmente en la teoría del orden , un conjunto parcialmente ordenado (también poset ) formaliza y generaliza el concepto intuitivo de un ordenamiento, secuenciación 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 ordenamiento. La relación en sí se llama "orden parcial". La palabra parcial en 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 que ningún elemento precede al otro en el poset. Por tanto, los pedidos parciales generalizan los pedidos totales , en los que cada par es comparable.
Definición informal
Un orden parcial define una noción de comparación . Dos elementos x y y pueden presentarse en cualquiera de las cuatro mutuamente excluyentes relaciones entre sí: o bien x < y , o x = y o x > y , o x y y son incomparable .
Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado (también llamado poset ). El término conjunto ordenado también se utiliza a veces, siempre que quede claro por el contexto que no se refiere a 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 conjuntos.
Un poset se puede visualizar a través de su diagrama de Hasse , que representa la relación de ordenamiento.
Relación de orden parcial
Una relación de orden parcial es una relación homogénea que es transitiva y antisimétrica . Hay dos subdefiniciones comunes para una relación de orden parcial, para relaciones de orden parcial reflexivas e irreflexivas, también llamadas "no estrictas" y "estrictas" respectivamente. Las dos definiciones se pueden poner en una correspondencia uno a uno , por lo que para cada orden parcial estricto hay un orden parcial no estricto correspondiente único, y viceversa. El término orden parcial se refiere típicamente a una relación de orden parcial no estricta.
Pedido parcial no estricto
Un reflexivo , débil o El orden parcial no estricto es unarelación homogénea≤ sobre unconjunto que esreflexivo,antisimétricoytransitivo. Es decir, para tododebe satisfacer:
- reflexividad :, es decir, todo elemento se relaciona consigo mismo.
- antisimetría : si , es decir, no se preceden dos elementos distintos.
- transitividad : si .
Un orden parcial no estricto también se conoce como preorden antisimétrico .
Orden parcial estricto
Un irreflexivo , fuerte oel orden parcial estricto sobrees una relación homogénea <sobreque esirreflexiva,transitivayasimétrica; es decir, satisface las siguientes condiciones para todos
- Irreflexividad : no , es decir, ningún elemento está relacionado consigo mismo.
- Transitividad : si
- Asimetría : si no .
La irreflexividad y la transitividad juntas implican asimetría. Además, la asimetría implica irreflexividad. En otras palabras, una relación transitiva es asimétrica si y solo si es irreflexiva. Entonces, la definición es la misma si omite la irreflexividad o la asimetría (pero no ambas).
Un pedido parcial estricto también se conoce como un pedido anticipado estricto .
Correspondencia de relaciones de orden parcial estrictas y no estrictas
Las órdenes parciales estrictas y no estrictas de un conjunto están estrechamente relacionadas. Una orden parcial no estricto se puede convertir en un orden parcial estricto mediante la eliminación de todas las relaciones de la forma que es, el orden parcial estricto es el conjunto , donde es la relación de identidad en y marca el conjunto de sustracción . A la inversa, un orden parcial estricto <on puede convertirse en un orden parcial no estricto uniendo todas las relaciones de esa forma; es decir, es un pedido parcial no estricto. Por tanto, si es un orden parcial no estricto, entonces el correspondiente orden parcial estricto <es el núcleo irreflexivo dado por
Órdenes duales
El dual (u opuesto ) de una relación de orden parcial se define dejando ser la
relación inversa de , es decir, si y sólo si . El dual de un orden parcial no estricto es un orden parcial no estricto, y el dual de un orden parcial estricto es un orden parcial estricto. El dual de un dual de una relación es la relación original.Notación
Podemos considerar un poset como una tupla de 3 , o incluso una tupla de 5 , donde y son relaciones de orden parcial no estrictas y son relaciones de orden parcial estrictas, el dual de es y y son igualmente duales entre sí.
Cualquiera de las cuatro relaciones de orden parcial de un conjunto determinado determina de forma única las otras tres. Por tanto, como cuestión de notación, podemos escribir o , y asumir que las otras relaciones están definidas de forma apropiada. La definición mediante un orden parcial no estricto es lo más común. Algunos autores utilizan diferentes símbolos que como o para distinguir órdenes parciales de los pedidos totales.
Al referirse a pedidos parciales, no debe tomarse como
complemento de . es el inverso del núcleo irreflexivo de , que siempre es un subconjunto del complemento de , pero es igual al complemento de si, y solo si , es un orden total.Ejemplos de
Los ejemplos estándar de postulados que surgen en matemáticas incluyen:
- Los números reales , o en general cualquier conjunto totalmente ordenado, ordenados por la relación estándar menor o igual ≤, es un orden parcial no estricto.
- En los números reales, la relación habitual
Un ejemplo familiar de un conjunto parcialmente ordenado es una colección de personas ordenadas por descendencia genealógica . Algunos pares de personas tienen la relación descendiente-ancestro, pero otros pares de personas son incomparables, sin que ninguno sea descendiente del otro.
Órdenes sobre el producto cartesiano de conjuntos parcialmente ordenados
En orden de fuerza creciente, es decir, conjuntos decrecientes de pares, tres de los posibles órdenes parciales en el producto cartesiano de dos conjuntos parcialmente ordenados son (vea la figura 3-5):
- el orden lexicográfico : ( a , b ) ≤ ( c , d ) si a < c o ( a = c y b ≤ d );
- el pedido de productos : ( a , b ) ≤ ( c , d ) si un ≤ c y b ≤ d ;
- el cierre reflexivo del producto directo de los correspondientes órdenes estrictos: ( a , b ) ≤ ( c , d ) si ( a < c y b < d ) o ( a = c y b = d ).
Los tres pueden definirse 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.
Ver también pedidos sobre el producto cartesiano de conjuntos totalmente ordenados .
Sumas de conjuntos parcialmente ordenados
Otra forma de combinar dos posets (disjuntos) es la suma ordinal (o suma lineal ), 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 , también lo está su suma ordinal.
Los órdenes parciales en serie-paralelos se forman a partir de la operación de suma ordinal (en este contexto llamada composición en serie) y otra operación llamada composición en paralelo. La composición paralela es 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.
Nociones derivadas
Los ejemplos usan el poset que consiste en el
conjunto de todos los subconjuntos de un conjunto de tres elementos ordenados por inclusión de conjuntos (ver Figura 1).- a está relacionada con b cuando a ≤ b . Esto no implica que b también esté relacionado con a , porque la relación no necesita ser simétrica . Por ejemplo, está relacionado pero no al revés.
- un y b son comparable si un ≤ b o b ≤ una . De lo contrario, son incomparables . Por ejemplo, y son comparables, mientras que y no lo son.
- Un orden total u
Extrema
Hay varias nociones de elemento "mayor" y "menor" en un conjunto, en particular:
- Elemento mayor y elemento menor: Un elemento es un elemento mayor si para cada elemento Un elemento es un elemento mínimo si para cada elemento Un poset solo puede tener un elemento mayor o menor. En nuestro ejemplo de ejecución, el conjunto es el elemento más grande y el menor.
- Elementos máximos y elementos mínimos: Un elemento es un elemento máximo si no hay ningún elemento tal que De manera similar, un elemento es un elemento mínimo si no hay ningún elemento tal que Si un poset tiene un elemento mayor, 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. En nuestro ejemplo de ejecución, y son los elementos máximo y mínimo. Eliminando estos, hay 3 elementos máximos y 3 elementos mínimos (ver Fig.6).
- 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 elemento más grande de P es un límite superior de P en sí, y un elemento de menos es un límite inferior de P . En nuestro ejemplo, el conjunto es un límite superior para la colección de elementos.
Como otro ejemplo, considere los números enteros positivos , ordenados por divisibilidad: 1 es un elemento mínimo, ya que divide a todos los demás elementos; por otro lado, este poset no tiene un elemento mayor (aunque si uno incluye 0 en el poset, que es un múltiplo de cualquier número entero, ese sería un elemento mayor; ver Fig.7). 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, pero cualquier número primo es un elemento mínimo para él. En este poset, 60 es un límite superior (aunque no al menos un límite superior) del subconjunto 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.
Mapeos entre conjuntos parcialmente ordenados
Dados dos conjuntos parcialmente ordenados ( S , ≤) y ( T , ≼), una función se llama preservadora del orden , o monótona , o isotona , si para todos implica f ( x ) ≼ f ( y ). Si ( U , ≲) también es un conjunto parcialmente ordenado, y ambos y conservan el orden, su composición también conserva el orden. Una función se llama reflectante de orden si para todo f ( x ) ≼ f ( y ) implica Si es a la vez preservadora y reflectora de orden, entonces se denomina incrustación de orden de ( S , ≤) en ( T , ≼ ). En el último caso, es necesariamente inyectiva , ya que implica a su vez de acuerdo con la antisimetría de Si una orden-incrustación de entre dos Posets S y T existe, se dice que S puede ser incrustado en T . Si una inserción de orden es biyectiva , se denomina isomorfismo de orden , y se dice que los órdenes parciales ( S , ≤) y ( T , ≼) son isomorfos . Los órdenes isomorfos tienen diagramas de Hasse estructuralmente similares (ver Figura 8). Se puede demostrar que si existen mapas que preservan el orden y que y produce la función de identidad en S y T , respectivamente, entonces S y T son orden-isomorfos.
Por ejemplo, un mapeo del conjunto de números naturales (ordenados por divisibilidad) al conjunto de potencias de números naturales (ordenados por inclusión de conjuntos) se puede definir tomando cada número al conjunto de sus divisores primos . Conserva el orden: si divide, entonces cada divisor primo de es también un divisor primo de Sin embargo, no es inyectivo (ya que asigna 12 y 6 a ) ni refleja el orden (ya que 12 no divide 6). En su lugar, tomar cada número al conjunto de sus divisores de potencia principales define un mapa que preserva el orden, refleja el orden y, por lo tanto, incrusta el orden. No es un orden-isomorfismo (ya que, por ejemplo, no asigna ningún número al conjunto ), pero se puede convertir en uno restringiendo su codominio a la Figura 9 muestra un subconjunto de y su imagen isomórfica bajo La construcción de tal orden-isomorfismo en un conjunto de potencias 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
La secuencia A001035 en OEIS da el número de órdenes parciales en un conjunto de n elementos etiquetados:
Elementos | Alguna | Transitivo | Reflexivo | Hacer un pedido | Orden parcial | Reserva total | Orden total | Relación de equivalencia |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | dieciséis | 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 |
norte | 2 n 2 | 2 n 2 - n | S ( n , k ) | n ! | S ( n , k ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
El número de pedidos parciales estrictos es el mismo que el de pedidos parciales.
Si el recuento se realiza solo hasta el isomorfismo, se obtiene la secuencia 1, 1, 2, 5, 16, 63, 318, ... (secuencia A000112 en la OEIS ).
Extensión lineal
Un orden parcial en un conjunto es una extensión de otro orden parcial en siempre que para todos los elementos siempre sea el caso que Una extensión lineal sea una extensión que también sea un orden lineal (es decir, total). Como ejemplo clásico, el orden lexicográfico de conjuntos totalmente ordenados es una extensión lineal de su orden de productos. Cada pedido parcial se puede extender a un pedido total ( principio de extensión de pedido ).
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 .
Gráficos acíclicos dirigidos
Los órdenes parciales estrictos corresponden directamente a los gráficos acíclicos dirigidos (DAG). Si un gráfico se construye tomando cada elemento de como un nodo y cada elemento de como un borde, entonces 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. . Por el contrario, un orden parcial no estricto tendría bucles propios en cada nodo y, por lo tanto, no sería un DAG.
En teoría de categorías
Cada poset (y cada conjunto preordenado ) puede ser considerado como una categoría donde, para objetos y hay como máximo un morfismo de a Más explícitamente, sea hom ( x , y ) = {( x , y )} si x ≤ y ( y de lo contrario el conjunto vacío) y estas categorías a veces se denominan posetal .
Los Posets son equivalentes entre sí si y solo si son isomorfos . 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 es isomorfismo-cerrado .
Órdenes parciales en espacios topológicos
Si 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 es un subconjunto cerrado del espacio de 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 para todos entonces
Intervalos
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 .
Los intervalos semiabiertos [ a , b ) y ( a , b ] se definen de manera similar.
A veces, las definiciones se amplían para permitir a > b , en cuyo caso el intervalo está vacío.
Un intervalo I está acotado si existen elementos tales que I ⊆ [ a , b ] . Cada intervalo que se puede representar en notación de intervalo está obviamente acotado, pero lo contrario no es cierto. Por ejemplo, sea P = (0, 1) ∪ (1, 2) ∪ (2, 3) como una subposición de los números reales . El subconjunto (1, 2) es un intervalo acotado, pero no tiene infimum o supremo 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 todo intervalo acotado es finito. Por ejemplo, los números enteros son localmente finitos bajo su orden 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
Este concepto de intervalo en un orden parcial no debe confundirse con la clase particular de órdenes parciales conocida como órdenes de intervalo .
Ver también
- Antimatroid , una formalización de pedidos en un conjunto que permite familias de pedidos más generales que posets
- Conjunto causal , un enfoque basado en poset de la gravedad cuántica
- Gráfico de comparabilidad
- Orden parcial completa
- Conjunto dirigido : conjunto con un pedido anticipado en el que dos elementos son siempre menores o iguales a un tercer elemento.
- Poset calificado
- Álgebra de incidencia
- Lattice - Estructura abstracta estudiada en las subdisciplinas matemáticas de la teoría de órdenes y el álgebra abstracta.
- Poset localmente finito
- Función de moebius en posets
- Colección de conjuntos anidados
- Solicitar politopo
- Campo ordenado
- Grupo ordenado
- Espacio vectorial ordenado
- Topología de Poset , una especie de espacio topológico que se puede definir desde cualquier poset
- Continuidad de Scott : continuidad de una función entre dos órdenes parciales.
- Semirredura
- Semiorder
- Dominio estocástico
- Orden estricto débil : orden parcial estricto "<" en el que la relación "ni a < b ni b < a " es transitiva.
- Orden total : orden cuyos elementos son todos comparables
- Árbol : estructura de datos de la inclusión de conjuntos
- Lema de Zorn - Proposición matemática equivalente al axioma de elección
Notas
Citas
Referencias
- Davey, BA; Priestley, HA (2002). Introducción a las celosías y el orden (2ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-78451-1.
- Deshpande, Jayant V. (1968). "Sobre la continuidad de una orden parcial" . Actas de la American Mathematical Society . 19 (2): 383–386. doi : 10.1090 / S0002-9939-1968-0236071-7 .
- Schmidt, Gunther (2010). Matemáticas relacionales . Enciclopedia de Matemáticas y sus Aplicaciones. 132 . Prensa de la Universidad de Cambridge. ISBN 978-0-521-76268-7.
- Bernd Schröder (11 de mayo de 2016). Conjuntos ordenados: una introducción con conexiones desde la combinatoria a la topología . Birkhäuser. ISBN 978-3-319-29788-0.
- Stanley, Richard P. (1997). Combinatoria enumerativa 1 . Estudios de Cambridge en Matemáticas Avanzadas. 49 . Prensa de la Universidad de Cambridge. ISBN 0-521-66351-2.