Conjunto parcialmente ordenado

Conjunto matemático con orden.

Fig. 1 El diagrama de Hasse del conjunto de todos los subconjuntos de un conjunto de tres elementos ordenados por inclusión . Los conjuntos conectados por un camino ascendente, como y , son comparables, mientras que, por ejemplo , y no lo son. ${\displaystyle \{x,y,z\},}$ ${\displaystyle \emptyset }$ ${\displaystyle \{x,y\}}$ ${\displaystyle \{x\}}$ ${\displaystyle \{y\}}$

En matemáticas , especialmente en teoría del orden , un orden parcial en un conjunto es una disposición tal que, para ciertos pares de elementos, uno precede al otro. La palabra parcial se utiliza para indicar que no todos los pares de elementos necesitan ser comparables; es decir, puede haber pares en los que ningún elemento precede al otro. Los pedidos parciales generalizan así los pedidos totales , en los que cada par es comparable.

Formalmente, un orden parcial es una relación binaria homogénea que es reflexiva , antisimétrica y transitiva . Un conjunto parcialmente ordenado ( poset para abreviar) es un par ordenado de un conjunto (llamado conjunto básico de ) y un orden parcial de . Cuando el significado queda claro a partir del contexto y no hay ambigüedad sobre el orden parcial, el conjunto en sí a veces se denomina poset. ${\displaystyle P=(X,\leq )}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle X}$

Relaciones de orden parcial

El término orden parcial suele referirse a las relaciones de orden parcial reflexivas, denominadas en este artículo órdenes parciales no estrictas . Sin embargo, algunos autores utilizan el término para el otro tipo común de relaciones de orden parcial, las relaciones de orden parcial irreflexivas, también llamadas órdenes parciales estrictas. Los pedidos parciales estrictos y no estrictos 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.

Órdenes parciales

Un reflexivo , débil , ^[1] oEl orden parcial no estricto ,^[2]comúnmente denominado simplementeorden parcial, es unarelación homogénea≤ en unconjunto que esreflexivo,antisimétricoytransitivo. Es decir, por tododebe satisfacer: ${\displaystyle P}$ ${\displaystyle a,b,c\in P,}$

1. Reflexividad : , es decir, cada elemento está relacionado consigo mismo. ${\displaystyle a\leq a}$
2. Antisimetría : si y entonces , es decir, no hay dos elementos distintos que se precedan entre sí. ${\displaystyle a\leq b}$ ${\displaystyle b\leq a}$ ${\displaystyle a=b}$
3. Transitividad : si y entonces . ${\displaystyle a\leq b}$ ${\displaystyle b\leq c}$ ${\displaystyle a\leq c}$

Un orden parcial no estricto también se conoce como preorden antisimétrico .

Órdenes parciales estrictas

Un irreflexivo , fuerte , ^[1] oel orden parcial estricto es una relación homogénea < en un conjuntoque esirreflexivo,asimétricoytransitivo; es decir, satisface las siguientes condiciones para todos ${\displaystyle P}$ ${\displaystyle a,b,c\in P:}$

1. Irreflexividad : no , es decir, ningún elemento está relacionado consigo mismo (también llamado antirreflexivo). ${\displaystyle a<a}$
2. Asimetría : si entonces no . ${\displaystyle a<b}$ ${\displaystyle b<a}$
3. Transitividad : si y entonces . ${\displaystyle a<b}$ ${\displaystyle b<c}$ ${\displaystyle a<c}$

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 sólo si es irreflexiva. ^[3] Entonces, la definición es la misma si omite la irreflexividad o la asimetría (pero no ambas).

Un orden parcial estricto también se conoce como preorden estricto asimétrico .

Correspondencia de relaciones de orden parcial estrictas y no estrictas.

Fig. 2 Diagrama conmutativo sobre las conexiones entre relaciones estrictas/no estrictas y sus duales, mediante las operaciones de cierre reflexivo ( cls ), núcleo irreflexivo ( ker ) y relación inversa ( cnv ). Cada relación se representa mediante su matriz lógica para el poset cuyo diagrama de Hasse se representa en el centro. Por ejemplo , la fila 3, columna 4 de la matriz inferior izquierda está vacía. ${\displaystyle 3\not \leq 4}$

Los órdenes parciales estrictos y no estrictos en un conjunto están estrechamente relacionados. Un orden parcial no estricto se puede convertir en un orden parcial estricto eliminando todas las relaciones de la forma , es decir, el orden parcial estricto es el conjunto donde está la relación de identidad y denota la resta de conjuntos . Por el contrario, un orden parcial estricto < on puede convertirse en un orden parcial no estricto uniendo todas las relaciones de esa forma; es decir, es un orden parcial no estricto. Por lo tanto, si es un orden parcial no estricto, entonces el orden parcial estricto correspondiente < es el núcleo irreflexivo dado por ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle a\leq a;}$ ${\displaystyle <\;:=\ \leq \ \setminus \ \Delta _{P}}$ ${\displaystyle \Delta _{P}:=\{(p,p):p\in P\}}$ ${\displaystyle P\times P}$ ${\displaystyle \;\setminus \;}$ ${\displaystyle P}$ ${\displaystyle \leq \;:=\;\Delta _{P}\;\cup \;<\;}$ ${\displaystyle \leq }$

$${\displaystyle a<b{\text{ if }}a\leq b{\text{ and }}a\neq b.}$$

cierre reflexivo ${\displaystyle \leq }$

$${\displaystyle a\leq b{\text{ if }}a<b{\text{ or }}a=b.}$$

Ó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, ^[4] 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. ${\displaystyle R^{\text{op}}}$ ${\displaystyle R}$ ${\displaystyle R^{\text{op}}}$ ${\displaystyle R}$ ${\displaystyle xR^{\text{op}}y}$ ${\displaystyle yRx}$

Notación

Dado un conjunto y una relación de orden parcial, típicamente el orden parcial no estricto , podemos extender de manera única nuestra notación para definir cuatro relaciones de orden parcial y , donde es una relación de orden parcial no estricta en , es la relación de orden parcial estricta asociada en (el núcleo irreflexivo de ), es el dual de , y es el dual de . En sentido estricto, el término conjunto parcialmente ordenado se refiere a un conjunto con todas estas relaciones definidas apropiadamente. Pero en la práctica, sólo es necesario considerar una relación única, o , o, en casos raros, las relaciones estrictas y no estrictas juntas . ^[5] ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle \leq ,}$ ${\displaystyle <,}$ ${\displaystyle \geq ,}$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle P}$ ${\displaystyle <}$ ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle \geq }$ ${\displaystyle \leq }$ ${\displaystyle >}$ ${\displaystyle <}$ ${\displaystyle (P,\leq )}$ ${\displaystyle (P,<)}$ ${\displaystyle (P,\leq ,<)}$

El término conjunto ordenado se utiliza a veces como abreviatura de conjunto parcialmente ordenado , siempre que del contexto quede claro 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 posets. Algunos autores utilizan símbolos diferentes a los de ^[6] o ^[7] para distinguir los pedidos parciales de los pedidos totales. ${\displaystyle \leq }$ ${\displaystyle \sqsubseteq }$ ${\displaystyle \preceq }$

Cuando se hace referencia a pedidos parciales, no se debe tomar como complemento de . La relación es la inversa del núcleo irreflexivo de , que siempre es un subconjunto del complemento de , pero es igual al complemento de si, y sólo si , es un orden total. ^[a] ${\displaystyle \leq }$ ${\displaystyle >}$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle \leq }$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle \leq }$

Definiciones alternativas

Otra forma de definir un orden parcial, que se encuentra en la informática , es mediante una noción de comparación . Específicamente, dado lo definido anteriormente, se puede observar que dos elementos x e y pueden estar en cualquiera de las cuatro relaciones mutuamente excluyentes entre sí: o x < y , o x = y , o x > y , o x e y son incomparable . Esto se puede representar mediante una función que devuelve uno de cuatro códigos cuando se le dan dos elementos. ^{[8] [9]} Esta definición es equivalente a un orden parcial en un setoide , donde la igualdad se considera una relación de equivalencia definida en lugar de la noción primitiva de igualdad de conjuntos. ^[10] ${\displaystyle \leq ,<,\geq ,{\text{ and }}>}$ ${\displaystyle {\text{compare}}:P\times P\to \{<,>,=,\vert \}}$

Wallis define una noción más general de relación de orden parcial como cualquier relación homogénea que sea transitiva y antisimétrica . Esto incluye órdenes parciales tanto reflexivos como irreflexivos como subtipos. ^[1]

Un poset finito se puede visualizar a través de su diagrama de Hasse . ^[11] Específicamente, tomando una relación de orden parcial estricta , se puede construir un gráfico acíclico dirigido (DAG) tomando cada elemento de como un nodo y cada elemento de como un borde. La reducción transitiva de este DAG ^[b] es entonces el diagrama de Hasse. De manera similar, este proceso se puede revertir para construir órdenes parciales estrictas a partir de ciertos DAG. Por el contrario, el grafo asociado a un orden parcial no estricto tiene self-loops en cada nodo y por tanto no es un DAG; Cuando se dice que un diagrama de Hasse representa un orden no estricto, en realidad se muestra el orden estricto correspondiente. ${\displaystyle (P,<)}$ ${\displaystyle P}$ ${\displaystyle <}$

Ejemplos

Fig. 3 Gráfica de la divisibilidad de números del 1 al 4. Este conjunto está parcialmente, pero no totalmente, ordenado porque existe una relación del 1 con cualquier otro número, pero no hay relación del 2 al 3 o del 3 al 4.

Ejemplos estándar de posets que surgen en matemáticas incluyen:

• Los números reales , o en general cualquier conjunto totalmente ordenado, ordenado por la relación estándar menor o igual ≤, es un orden parcial.
• En los números reales , la relación habitual menor que < es un orden parcial estricto. Lo mismo ocurre con la relación habitual mayor que > on . ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$
• Por definición, todo orden estricto débil es un orden estricto parcial.
• El conjunto de subconjuntos de un conjunto dado (su conjunto potencia ) ordenados por inclusión (ver Fig. 1). De manera similar, el conjunto de secuencias ordenadas por subsecuencia y el conjunto de cadenas ordenadas por subcadena .
• El conjunto de los números naturales dotados de la relación de divisibilidad . (ver Fig. 3 y Fig. 6)
• El conjunto de vértices de un gráfico acíclico dirigido ordenado por accesibilidad .
• El conjunto de subespacios de un espacio vectorial ordenados por inclusión.
• Para un conjunto parcialmente ordenado P , 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, si y sólo si para todos ; es decir, un orden por componentes . ${\displaystyle \left(a_{n}\right)_{n\in \mathbb {N} }\leq \left(b_{n}\right)_{n\in \mathbb {N} }}$ ${\displaystyle a_{n}\leq b_{n}}$ ${\displaystyle n\in \mathbb {N} }$
• 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 todos ${\displaystyle x\in X.}$
• Una valla , un conjunto parcialmente ordenado definido por una secuencia alterna de relaciones de orden a < b > c < d ...
• El conjunto de eventos en la relatividad especial y, en la mayoría de los casos, ^[c] 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 puede verse afectado causalmente por X sólo si X ≤ Y.

Un ejemplo familiar de conjunto parcialmente ordenado es un conjunto de personas ordenadas por descendencia genealógica . Algunos pares de personas mantienen la relación descendiente-ancestro, pero otros pares de personas son incomparables, ya que ninguno es descendiente del otro.

Órdenes sobre el producto cartesiano de conjuntos parcialmente ordenados

En orden de fuerza creciente, es decir, conjuntos de pares decrecientes, tres de los posibles órdenes parciales en el producto cartesiano de dos conjuntos parcialmente ordenados son (ver Fig. 4):

• el orden lexicográfico :   ( a , b ) ≤ ( c , d ) si a < c o ( a = c y b ≤ d );
• el orden del producto : ( a , b ) ≤ ( c , d ) si a ≤ c y b ≤ d ;
• la clausura reflexiva del producto directo de los órdenes estrictos correspondientes:   ( 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 ^[12] (o suma lineal ), ^[13] Z = X ⊕ Y , definida en la unión de los conjuntos subyacentes X e Y por el orden a ≤ _Z b si y sólo si:

• a , b ∈ X con a ≤ _X b , o
• a , b ∈ Y con a ≤ _Y b , o
• a ∈ X y b ∈ Y .

Si dos posets están bien ordenados , también lo estará su suma ordinal. ^[14]

Los órdenes parciales series-paralelos se forman a partir de la operación de suma ordinal (en este contexto llamada composición de series) y otra operación llamada composición paralela. 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 utilizan el poset que consiste en el conjunto de todos los subconjuntos de un conjunto de tres elementos ordenados por inclusión de conjuntos (ver Fig. 1). ${\displaystyle ({\mathcal {P}}(\{x,y,z\}),\subseteq )}$ ${\displaystyle \{x,y,z\},}$

• a está relacionado con b cuando a ≤ b . Esto no implica que b también esté relacionado con a , porque la relación no tiene por qué ser simétrica . Por ejemplo, está relacionado pero no al revés. ${\displaystyle \{x\}}$ ${\displaystyle \{x,y\},}$
• a y b son comparables si a ≤ b o b ≤ a . De lo contrario son incomparables . Por ejemplo, y son comparables, mientras que y no lo son. ${\displaystyle \{x\}}$ ${\displaystyle \{x,y,z\}}$ ${\displaystyle \{x\}}$ ${\displaystyle \{y\}}$
• Un orden total u orden lineal es un orden parcial bajo el cual cada par de elementos es comparable, es decir, se cumple la tricotomía . Por ejemplo, los números naturales con su orden estándar.
• Una cadena es un subconjunto de un poset que es un conjunto totalmente ordenado. Por ejemplo, es una cadena. ${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$
• Una anticadena es un subconjunto de un poset en el que no hay dos elementos distintos comparables. Por ejemplo, el conjunto de singletons ${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• Se dice que un elemento a es estrictamente menor que un elemento b , si a ≤ b y, por ejemplo, es estrictamente menor que ${\displaystyle a\neq b.}$ ${\displaystyle \{x\}}$ ${\displaystyle \{x,y\}.}$
• Se dice que un elemento a está cubierto por otro elemento b , escrito a ⋖ b (o a <: b ), si a es estrictamente menor que by ningún tercer elemento c encaja entre ellos; formalmente: si a ≤ b y son verdaderos, y a ≤ c ≤ b es falso para cada c con Usando el orden estricto <, la relación a ⋖ b se puede reformular de manera equivalente como " a < b pero no a < c < b para cualquier c ". Por ejemplo, está cubierto por pero no está cubierto por ${\displaystyle a\neq b}$ ${\displaystyle a\neq c\neq b.}$ ${\displaystyle \{x\}}$ ${\displaystyle \{x,z\},}$ ${\displaystyle \{x,y,z\}.}$

extremo

Fig. 5 La figura de arriba con los elementos mayor y menor eliminados. En este conjunto reducido, la fila superior de elementos son todos elementos máximos y la fila inferior son todos elementos mínimos , pero no hay ningún elemento mayor ni menor .

Hay varias nociones de elemento "mayor" y "menor" en un poset, en particular: ${\displaystyle P,}$

• Elemento mayor y elemento menor: Un elemento es un elemento mayor si para cada elemento Un elemento es un elemento menor si para cada elemento Un poset solo puede tener un elemento mayor o menor. En nuestro ejemplo en ejecución, el conjunto es el elemento mayor y el menor. ${\displaystyle g\in P}$ ${\displaystyle a\leq g}$ ${\displaystyle a\in P.}$ ${\displaystyle m\in P}$ ${\displaystyle m\leq a}$ ${\displaystyle a\in P.}$ ${\displaystyle \{x,y,z\}}$ ${\displaystyle \{\,\}}$
• 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 por lo demás puede haber más de un elemento máximo, y lo mismo ocurre con los elementos mínimos y los elementos mínimos. En nuestro ejemplo en ejecución, y son los elementos máximo y mínimo. Quitándolos, hay 3 elementos máximos y 3 elementos mínimos (ver Fig. 5). ${\displaystyle g\in P}$ ${\displaystyle a\in P}$ ${\displaystyle a>g.}$ ${\displaystyle m\in P}$ ${\displaystyle a\in P}$ ${\displaystyle a<m.}$ ${\displaystyle \{x,y,z\}}$ ${\displaystyle \{\,\}}$
• Límites superior e inferior : Para un subconjunto A de P , un elemento x en P es un límite superior de A si a  ≤  x , para cada elemento a en A. En particular, no es necesario que x esté en A para ser un límite superior de A. De manera similar, un elemento x en P es un límite inferior de A si a  ≥  x , para cada elemento a en A . Un elemento mayor de P es un límite superior del propio P , y un elemento mínimo es un límite inferior de P. En nuestro ejemplo, el conjunto es un límite superior para la colección de elementos. ${\displaystyle \{x,y\}}$ ${\displaystyle \{\{x\},\{y\}\}.}$

Fig. 6 Enteros no negativos , ordenados por divisibilidad

Como otro ejemplo, considere los números enteros positivos , ordenados por divisibilidad: 1 es el elemento mínimo, ya que divide a todos los demás elementos; por otro lado este poset no tiene un elemento mayor. 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, manteniendo la divisibilidad como orden de 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 un límite superior mínimo) 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. Si se incluye el número 0, este será el elemento mayor, ya que es un múltiplo de cada número entero (ver Fig. 6). ${\displaystyle \{2,3,5,10\},}$

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 isótona , 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 reflejo de orden si para todo f ( x ) ≼ f ( y ) implica que si f preserva y refleja el orden, entonces se llama incrustación de orden de ( S , ≤) en ( T , ≼) . En el último caso, f es necesariamente inyectiva , ya que implica y a su vez según la antisimetría de Si existe un orden de incrustación entre dos posets S y T , se dice que S puede incrustarse en T. Si una incrustación de orden es biyectiva , se llama isomorfismo de orden , y los órdenes parciales ( S , ≤) y ( T , ≼) se dicen isomorfos . Los órdenes isomórficos tienen diagramas de Hasse estructuralmente similares (ver Fig. 7a). Se puede demostrar que si existen mapas que preservan el orden y de modo que y produzcan la función de identidad en S y T , respectivamente, entonces S y T son isomorfos de orden. ^[15] ${\displaystyle f:S\to T}$ ${\displaystyle x,y\in S,}$ ${\displaystyle x\leq y}$ ${\displaystyle f:S\to T}$ ${\displaystyle g:T\to U}$ ${\displaystyle g\circ f:S\to U}$ ${\displaystyle f:S\to T}$ ${\displaystyle x,y\in S,}$ ${\displaystyle x\leq y.}$ ${\displaystyle f(x)=f(y)}$ ${\displaystyle x\leq y{\text{ and }}y\leq x}$ ${\displaystyle x=y}$ ${\displaystyle \leq .}$ ${\displaystyle f:S\to T}$ ${\displaystyle f:S\to T}$ ${\displaystyle g:T\to U}$ ${\displaystyle g\circ f}$ ${\displaystyle f\circ g}$

Por ejemplo, se puede definir una correspondencia del conjunto de números naturales (ordenados por divisibilidad) al conjunto de potencias de números naturales (ordenados por inclusión de conjuntos) llevando cada número al conjunto de sus divisores primos . Conserva el orden: si x divide y , entonces cada divisor primo de x también es un divisor primo de y . Sin embargo, no es inyectivo (ya que asigna 12 y 6 a ) ni refleja el orden (ya que 12 no divide a 6). En cambio, llevar cada número al conjunto de sus divisores de potencias primos define un mapa que preserva el orden, refleja el orden y, por tanto, incrusta el orden. No es un isomorfismo de orden (ya que, por ejemplo, no asigna ningún número al conjunto ), pero se puede convertir en uno restringiendo su codominio a . La figura 7b muestra un subconjunto de y su imagen isomórfica bajo g . La construcción de tal isomorfismo de orden en un conjunto de potencias puede generalizarse a una amplia clase de órdenes parciales, llamados redes distributivas ; véase el teorema de representación de Birkhoff . ${\displaystyle f:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$ ${\displaystyle \{2,3\}}$ ${\displaystyle g:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$ ${\displaystyle \{4\}}$ ${\displaystyle g(\mathbb {N} ).}$ ${\displaystyle \mathbb {N} }$

Número de pedidos parciales

La secuencia A001035 en OEIS proporciona el número de órdenes parciales en un conjunto de n elementos etiquetados:

Tenga en cuenta que S ( n , k ) se refiere a los números de Stirling del segundo tipo .

El número de órdenes parciales estrictas es el mismo que el de órdenes parciales.

Si el recuento se realiza sólo hasta el isomorfismo se obtiene la secuencia 1, 1, 2, 5, 16, 63, 318,... (secuencia A000112 en el 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 que también se dé el caso de que Una extensión lineal es una extensión que también es un orden lineal (es decir, total). Como ejemplo clásico, el orden lexicográfico de conjuntos totalmente ordenados es una extensión lineal del orden de sus productos. Cada orden parcial puede ampliarse a una orden total ( principio de extensión de orden ). ^[dieciséis] ${\displaystyle \leq ^{*}}$ ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle x,y\in X,}$ ${\displaystyle x\leq y,}$ ${\displaystyle x\leq ^{*}y.}$

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 la teoría de categorías

Cada poset (y cada conjunto preordenado ) puede considerarse 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 en caso contrario el conjunto vacío ) y estas categorías a veces se denominan posetal . En topología diferencial, la teoría de la homología (HT) se utiliza para clasificar variedades suaves equivalentes M, relacionadas con las formas geométricas de M. ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle x}$ ${\displaystyle y.}$ ${\displaystyle (y,z)\circ (x,y)=(x,z).}$

Los posets son equivalentes entre sí si y sólo 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 reservado equivale a un poset. Finalmente, cada subcategoría de un poset está cerrada por isomorfismo . En topología diferencial, la teoría de la homología (HT) se utiliza para clasificar variedades suaves equivalentes M, relacionadas con las formas geométricas de M. En la teoría de la homología se da un enfoque HT axiomático, especialmente para la homología singular. ^{[ aclaración necesaria ]} Los miembros de HT son invariantes algebraicos bajo difeomorfismos. La categoría axiomática HT está tomada en G. Kalmbach del libro Eilenberg-Steenrod (ver las referencias) para mostrar que el concepto topológico teórico de conjuntos para la definición HT se puede extender a conjuntos ordenados parciales P. Son importantes las cadenas y los filtros en P (reemplazando formas de M) para definir clasificaciones HT, disponible para muchas aplicaciones de P no relacionadas con la teoría de conjuntos.

Ó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 asumir que es un subconjunto cerrado del espacio producto topológico . Bajo esta suposición las relaciones de orden parcial se comportan bien en los límites en el sentido de que si y y para todos entonces ^[17] ${\displaystyle P}$ ${\displaystyle \{(a,b):a\leq b\}}$ ${\displaystyle P\times P.}$ ${\displaystyle \lim _{i\to \infty }a_{i}=a,}$ ${\displaystyle \lim _{i\to \infty }b_{i}=b,}$ ${\displaystyle i,}$ ${\displaystyle a_{i}\leq b_{i},}$ ${\displaystyle a\leq b.}$

Intervalos

Un conjunto convexo en un poset P es un subconjunto I de P con la propiedad de que, para cualquier x e y en I y cualquier z en P , si x ≤ z ≤ y , entonces z también está en I. Esta definición generaliza la definición de intervalos de números reales . Cuando existe una posible confusión con conjuntos de geometría convexos , se utiliza orden-convexo en lugar de "convexo".

Una subred convexa de una red L es una subred de L que también es un conjunto convexo de L. Cada subred convexa no vacía se puede representar de forma única como la intersección de un filtro y un ideal de L.

Un intervalo en un poset P es un subconjunto que se puede definir con notación de intervalo:

• 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 a 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 (0, 1) en los números enteros está vacío ya que no existe ningún número entero x tal que 0 < x < 1 .
• Los intervalos semiabiertos [ a , b ) y ( a , b ] se definen de manera similar.

Siempre que a ≤ b no se cumple, todos estos intervalos están vacíos. Todo intervalo es un conjunto convexo, pero lo contrario no se cumple; por ejemplo, en el conjunto de divisores de 120, ordenados por divisibilidad (ver Fig. 7b), el conjunto {1, 2, 4, 5, 8} es convexo, pero no es un intervalo.

Un intervalo I está acotado si existen elementos tales que I ⊆ [ a , b ] . Todo intervalo que puede representarse en notación de intervalo es obviamente acotado, 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 mínimo ni supremo en  P , por lo que no se puede escribir en notación de intervalo usando elementos de  P. ${\displaystyle a,b\in P}$

Un poset se llama localmente finito si todo intervalo acotado es finito. Por ejemplo, los números enteros son localmente finitos según 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 ${\displaystyle \mathbb {N} \times \mathbb {N} }$ ${\displaystyle [a,b]=\{a,b\}.}$

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

• Antimatroide , una formalización de ordenamientos en un conjunto que permite familias de ordenamientos más generales que los posets.
• Conjunto causal , un enfoque basado en poset para la gravedad cuántica
• Gráfico de comparabilidad  : gráfico que vincula pares de elementos comparables en un orden parcial
• Orden parcial completo  : término utilizado en la teoría del orden matemáticoPages displaying wikidata descriptions as a fallback
• Conjunto dirigido  : ordenamiento matemático con límites superiores
• Poset clasificado  : conjunto parcialmente ordenado equipado con una función de clasificación, a veces denominado poset clasificado.Pages displaying wikidata descriptions as a fallback
• Álgebra de incidencia  : álgebra asociativa utilizada en combinatoria, una rama de las matemáticasPages displaying wikidata descriptions as a fallback
• Lattice  : conjunto cuyos pares tienen mínimos y máximos.
• Poset localmente finito  - MatemáticasPages displaying wikidata descriptions as a fallbackPages displaying short descriptions with no spaces
• Función de Möbius en posets  : álgebra asociativa utilizada en combinatoria, una rama de las matemáticasPages displaying wikidata descriptions as a fallback
• Colección de conjuntos anidados
• Orden politopo
• Campo ordenado  : objeto algebraico con una estructura ordenada
• Grupo ordenado  – Grupo con un pedido parcial compatiblePages displaying short descriptions of redirect targets
• Espacio vectorial ordenado  : espacio vectorial con orden parcial
• Topología poset , una especie de espacio topológico que puede definirse a partir de cualquier poset
• Continuidad de Scott : continuidad de una función entre dos órdenes parciales.
• Semilattice  – Orden parcial con uniones
• Semiorden  : ordenamiento numérico con margen de error
• Teorema de extensión de Szpilrajn : todo orden parcial está contenido en algún orden total.
• Dominio estocástico  : orden parcial entre variables aleatorias
• Ordenamiento débil estricto : 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 inclusión de conjuntos.
• Lema de Zorn  : proposición matemática equivalente al axioma de elección

Notas

1. Puede encontrar una prueba aquí .
2. que siempre existe y es único, ya que se supone finito ${\displaystyle P}$
3. Ver Relatividad general § Viaje en el tiempo .

Citas

1. Wallis, WD (14 de marzo de 2013). Una guía para principiantes de matemáticas discretas. Medios de ciencia y negocios de Springer. pag. 100.ISBN​ 978-1-4757-3826-1.
2. Simovici, Dan A. y Djeraba, Chabane (2008). "Conjuntos parcialmente ordenados". Herramientas matemáticas para minería de datos: teoría de conjuntos, órdenes parciales, combinatoria . Saltador. ISBN 9781848002012.
3. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). "Cierres transitivos de relaciones binarias I". Acta Universitatis Carolinae. Matemática y Física . Praga: Escuela de Matemáticas – Universidad Carolina de Física. 48 (1): 55–69.Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
4. Davey y Priestley (2002), págs. 14-15.
5. Avigad, Jeremy; Lewis, Robert Y.; van Doorn, Floris (29 de marzo de 2021). "13.2. Más información sobre pedidos". Lógica y prueba (versión 3.18.4 ed.) . Consultado el 24 de julio de 2021 . Por tanto, podemos pensar que cada orden parcial es realmente un par, que consta de un orden parcial débil y uno estricto asociado.
6. Rondas, William C. (7 de marzo de 2002). "Diapositivas de conferencias" (PDF) . EECS 203: MATEMÁTICAS DISCRETAS . Consultado el 23 de julio de 2021 .
7. Kwong, Harris (25 de abril de 2018). "7.4: Ordenamiento Parcial y Total". Un libro de ejercicios en espiral para matemáticas discretas . Consultado el 23 de julio de 2021 .
8. "Posets finitos". Manual de referencia de Sage 9.2.beta2: combinatoria . Consultado el 5 de enero de 2022 . compare_elements( x , y ): Compara xey en el poset . Si x < y , devuelve −1. Si x = y , devuelve 0. Si x > y , devuelve 1. Si xey no son comparables, devuelve Ninguno.
9. Chen, Pedro; Ding, Guoli; Seiden, Steve. Sobre Poset Merging (PDF) (Informe técnico). pag. 2 . Consultado el 5 de enero de 2022 . Una comparación entre dos elementos s, t en S devuelve uno de tres valores distintos, a saber, s≤t, s>t o s|t.
10. Prevosto, Virgilio; Jaume, Mathieu (11 de septiembre de 2003). Realización de pruebas en una jerarquía de estructuras matemáticas. CALCULEMUS-2003 – XI Simposio sobre la Integración de la Computación Simbólica y el Razonamiento Mecanizado. Roma, Italia: Aracne. págs. 89-100.
11. Merrifield, Richard E.; Simmons, Howard E. (1989). Métodos topológicos en química . Nueva York: John Wiley & Sons. págs.28. ISBN 0-471-83817-9. Consultado el 27 de julio de 2012 . Un conjunto parcialmente ordenado se representa convenientemente mediante un diagrama de Hasse ...
12. Neggers, J.; Kim, Hee Sik (1998), "4.2 Orden de productos y orden lexicográfico", Posets básicos , World Scientific, págs. 62–63, ISBN 9789810235895
13. Davey y Priestley (2002), págs. 17-18.
14. PR Halmos (1974). Teoría de conjuntos ingenua . Saltador. pag. 82.ISBN​ 978-1-4757-1645-0.
15. Davey y Priestley (2002), págs. 23-24.
16. Jech, Thomas (2008) [1973]. El axioma de elección . Publicaciones de Dover . ISBN 978-0-486-46624-8.
17. Ward, LE Jr (1954). "Espacios topológicos parcialmente ordenados". Actas de la Sociedad Matemática Estadounidense . 5 (1): 144–161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

Referencias

• Davey, Licenciatura en Letras; Priestley, HA (2002). Introducción a las celosías y al orden (2ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-78451-1.
• Deshpande, Jayant V. (1968). "Sobre la continuidad de un orden parcial". Actas de la Sociedad Matemática Estadounidense . 19 (2): 383–386. doi : 10.1090/S0002-9939-1968-0236071-7 .
• Schmidt, Günther (2010). Matemáticas Relacionales . Enciclopedia de Matemáticas y sus Aplicaciones. vol. 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 hasta 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. vol. 49. Prensa de la Universidad de Cambridge. ISBN 0-521-66351-2.
• Eilenberg, S. (2016). Fundamentos de la topología algebraica . Prensa de la Universidad de Princeton.
• Kalmbach, G. (1976). "Extensión de la teoría de la homología a conjuntos parcialmente ordenados". J. Reina Angew. Matemáticas . 280 : 134-156.

enlaces externos

• Secuencia OEIS A001035 (Número de posets con n elementos etiquetados)
• Secuencia OEIS A000112 (Número de conjuntos parcialmente ordenados ("posets") con n elementos sin etiquetar).