Conjunto parcialmente ordenado

Conjunto matemático con un ordenamiento

Fig. 1 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 para los cuales ningún elemento precede al otro. Los órdenes parciales, por lo tanto, generalizan los órdenes totales , en los que todos los pares son comparables.

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

Relaciones de orden parcial

El término orden parcial se refiere generalmente a las relaciones de orden parcial reflexivas, a las que en este artículo se hace referencia como órdenes parciales no estrictos . 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 estrictos. Los órdenes parciales estrictos y no estrictos se pueden poner en una correspondencia uno a uno , por lo que para cada orden parcial estricto existe 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 esreflexiva,antisimétricaytransitiva. Es decir, para todosdebe 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 esirreflexiva,asimétricaytransitiva; es decir, satisface las siguientes condiciones para todos ${\displaystyle P}$ ${\displaystyle a,b,c\in P:}$

1. Irreflexividad : es decir, ningún elemento está relacionado consigo mismo (también llamado antirreflexivo). ${\displaystyle \neg \left(a<a\right)}$
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 solo si es irreflexiva. ^[3] Por lo tanto, 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, a través de 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 conjunto parcial 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 puede convertirse en un orden parcial estricto eliminando todas las relaciones de la forma , es decir, el orden parcial estricto es el conjunto donde es la relación de identidad en y denota la resta del conjunto . Por el contrario, un orden parcial estricto < en puede convertirse en un orden parcial no estricto adjuntando 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 Por el contrario, si < es un orden parcial estricto, entonces el orden parcial no estricto correspondiente es la clausura reflexiva dada 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.}$$ ${\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 que sea la relación inversa de , es decir, si y solo 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 . Estrictamente hablando, el término conjunto parcialmente ordenado se refiere a un conjunto con todas estas relaciones definidas apropiadamente. Pero prácticamente, uno solo necesita considerar una sola relación, o , o, en casos raros, las relaciones no estrictas y 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 una abreviatura de conjunto parcialmente ordenado , siempre que quede claro por el contexto que no se hace referencia 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 parciales. Algunos autores utilizan símbolos diferentes, como ^[6] o ^[7], para distinguir los órdenes parciales de los órdenes totales. ${\displaystyle \leq }$ ${\displaystyle \sqsubseteq }$ ${\displaystyle \preceq }$

Cuando se hace referencia a órdenes parciales, no debe tomarse como el 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 solo 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 como se definió anteriormente, se puede observar que dos elementos x e y pueden estar en cualquiera de cuatro relaciones mutuamente excluyentes entre sí: o bien x < y , o bien x = y , o bien x > y , o bien x e y son incomparables . Esto se puede representar mediante una función que devuelve uno de cuatro códigos cuando se dan dos elementos. ^{[8] [9]} Esta definición es equivalente a un orden parcial en un setoide , donde la igualdad se toma como una relación de equivalencia definida en lugar de una 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 una relación de orden parcial como cualquier relación homogénea que sea transitiva y antisimétrica . Esto incluye tanto los órdenes parciales reflexivos como los irreflexivos como subtipos. ^[1]

Un conjunto de elementos finitos puede visualizarse a través de su diagrama de Hasse . ^[11] Específicamente, tomando una relación de orden parcial estricta , se puede construir un grafo acíclico dirigido (DAG) tomando cada elemento de como un nodo y cada elemento de como una arista. La reducción transitiva de este DAG ^[b] es entonces el diagrama de Hasse. De manera similar, este proceso se puede invertir para construir órdenes parciales estrictos a partir de ciertos DAG. En contraste, el grafo asociado a un orden parcial no estricto tiene bucles propios en cada nodo y, por lo tanto, no es un DAG; cuando se dice que un orden no estricto está representado por un diagrama de Hasse, en realidad se muestra el orden estricto correspondiente. ${\displaystyle (P,<)}$ ${\displaystyle P}$ ${\displaystyle <}$

Ejemplos

Fig. 3 Gráfica de la divisibilidad de los 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 existe una relación del 2 con el 3 o del 3 con el 4.

Algunos ejemplos estándar de conjuntos parciales 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 que ≤, es un orden parcial.
• En los números reales , la relación usual menor que < es un orden parcial estricto. Lo mismo es cierto también para la relación usual mayor que > en . ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$
• Por definición, todo orden débil estricto es un orden parcial estricto.
• El conjunto de subconjuntos de un conjunto dado (su conjunto potencia ) ordenados por inclusión (véase la figura 1). De manera similar, el conjunto de secuencias ordenadas por subsecuencia , y el conjunto de cadenas ordenadas por subcadena .
• El conjunto de números naturales dotado 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 alcanzabilidad .
• El conjunto de subespacios de un espacio vectorial ordenados por inclusión.
• Para un conjunto parcialmente ordenado P , el espacio de secuencias 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 solo 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 desde X hasta P , donde f ≤ g si y solo si f ( x ) ≤ g ( x ) para todas ${\displaystyle x\in X.}$
• Una valla , un conjunto parcialmente ordenado definido por una secuencia alternada de relaciones de orden a < b > c < d ...
• El conjunto de eventos en la relatividad especial y, en la mayoría de los casos, en ^{la [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 solo si X ≤ Y.

Un ejemplo conocido 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-antepasado, pero otros pares de personas son incomparables, ya que ninguno es descendiente del otro.

Órdenes en 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 Figura 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 ;
• el cierre reflexivo 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 cuerpo , el resultado es en cada caso también un espacio vectorial ordenado.

Véase también los órdenes en el producto cartesiano de conjuntos totalmente ordenados .

Sumas de conjuntos parcialmente ordenados

Otra forma de combinar dos conjuntos parciales (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 solo si:

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

Si dos conjuntos parciales están bien ordenados , entonces también lo está su suma ordinal. ^[14]

Los órdenes parciales serie-paralelo 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 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 conjunto 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). ${\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 necesita ser simétrica . Por ejemplo, está relacionado con pero no a la inversa. ${\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 en el que 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 conjunto posexpuesto que es un conjunto totalmente ordenado. Por ejemplo, es una cadena. ${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$
• Una anticadena es un subconjunto de un conjunto parcial 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 b y ningún tercer elemento c cabe entre ellos; formalmente: si tanto a ≤ b como son verdaderos, y a ≤ c ≤ b es falso para cada c con Usando el orden estricto <, la relación a ⋖ b puede reformularse 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\}.}$

Extrema

Fig. 5 La figura anterior con los elementos mayor y menor eliminados. En este conjunto parcial 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 .

Existen varias nociones de elemento "mayor" y "menor" en un conjunto posexpuesto, 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 conjunto parcial solo puede tener un elemento mayor o menor. En nuestro ejemplo en ejecución, el conjunto es el elemento mayor y es 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 conjunto parcial tiene un elemento mayor, debe ser el único elemento máximo, pero de lo contrario puede haber más de un elemento máximo, y de manera similar para los elementos menores 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, x no necesita estar 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 máximo de P es un límite superior de P mismo, 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 Números enteros no negativos , ordenados por divisibilidad

Como otro ejemplo, considere los enteros positivos , ordenados por divisibilidad: 1 es un elemento mínimo, ya que divide a todos los demás elementos; por otro lado, este conjunto parcial no tiene un elemento máximo. Este conjunto parcialmente ordenado ni siquiera tiene elementos máximos, ya que cualquier g divide, por ejemplo, a 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 ordenación en los elementos mayores que 1, entonces el conjunto parcial resultante no tiene un elemento mínimo, pero cualquier número primo es un elemento mínimo para él. En este conjunto parcial, 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 conjunto parcial); 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 máximo, ya que es un múltiplo de cada entero (ver Figura 6). ${\displaystyle \{2,3,5,10\},}$

Mapeos entre conjuntos parcialmente ordenados

Dados dos conjuntos parcialmente ordenados ( S , ≤) y ( T , ≼) , una función se llama conservadora del orden , o monótona , o isótona , si para todo implica f ( x ) ≼ f ( y ) . Si ( U , ≲) es también un conjunto parcialmente ordenado, y ambos y son conservadores del orden, su composición también es conservadora del orden. Una función se llama reflectora del orden si para todo f ( x ) ≼ f ( y ) implica Si f es tanto conservadora del orden como reflectora del 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 de acuerdo con la antisimetría de Si existe una incrustación de orden entre dos conjuntos parciales S y T , se dice que S puede ser incrustado en T . Si una incrustació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 (véase la figura 7a). Se puede demostrar que si existen mapas que preservan el orden y tales que y producen la función identidad en S y T , respectivamente, entonces S y T son isomorfos en 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, una aplicación del conjunto de números naturales (ordenados por divisibilidad) al conjunto potencia de números naturales (ordenados por inclusión de conjuntos) se puede definir llevando cada número al conjunto de sus divisores primos . Es preservadora del orden: si x divide a y , entonces cada divisor primo de x es también un divisor primo de y . Sin embargo, no es ni inyectiva (ya que asigna tanto 12 como 6 a ) ni refleja el orden (ya que 12 no divide a 6). Llevar en cambio cada número al conjunto de sus divisores de potencia primos define una aplicación que preserva el orden, refleja el orden y, por lo tanto, es una incrustación de 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 isomorfa bajo g . La construcción de tal isomorfismo de orden en un conjunto de potencia se puede generalizar 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 da el número de órdenes parciales en un conjunto de n elementos etiquetados:

Téngase en cuenta que S ( n , k ) se refiere a 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 la OEIS ).

Subconjuntos

Un conjunto parcial se denomina subconjunto parcial de otro conjunto parcial siempre que sea un subconjunto de y sea un subconjunto de . La última condición es equivalente al requisito de que para cualquier y en (y por lo tanto también en ), si entonces . ${\displaystyle P^{*}=(X^{*},\leq ^{*})}$ ${\displaystyle P=(X,\leq )}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle \leq ^{*}}$ ${\displaystyle \leq }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle x\leq ^{*}y}$ ${\displaystyle x\leq y}$

Si es un subconjunto de y además, para todos y en , siempre que también tengamos , entonces llamamos al subconjunto de inducido por , y escribimos . ${\displaystyle P^{*}}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X^{*}}$ ${\displaystyle x\leq y}$ ${\displaystyle x\leq ^{*}y}$ ${\displaystyle P^{*}}$ ${\displaystyle P}$ ${\displaystyle X^{*}}$ ${\displaystyle P^{*}=P[X^{*}]}$

Extensión lineal

Un orden parcial de un conjunto se denomina extensión de otro orden parcial de un conjunto , siempre que para todos los elementos se dé también 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 los conjuntos totalmente ordenados es una extensión lineal de su orden producto. Todo orden parcial puede extenderse a un orden total ( principio de extensión de orden ). ^[16] ${\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 los órdenes de alcanzabilidad de gráficos acíclicos dirigidos ) se denominan ordenamiento topológico .

En la teoría de categorías

Cada conjunto poset (y cada conjunto preordenado ) puede considerarse como una categoría donde, para los 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 posetales . ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle x}$ ${\displaystyle y.}$ ${\displaystyle (y,z)\circ (x,y)=(x,z).}$

Los conjuntos ordenados por partes son equivalentes entre sí si y solo si son isomorfos . En un conjunto ordenado por partes, 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 conjunto ordenado por partes. Finalmente, cada subcategoría de un conjunto ordenado por partes es isomorfista-cerrada .

Ó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 es habitual suponer que 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 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 conjunto parcial 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 los conjuntos convexos de geometría , se utiliza el término "convexo de orden " 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 conjunto posexpuesto 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 relación estricta correspondiente "<", 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 no se cumple el caso inverso; por ejemplo, en el conjunto de divisores de 120, ordenados por divisibilidad (véase la figura 7b), el conjunto {1, 2, 4, 5, 8} es convexo, pero no un intervalo.

Un intervalo I está acotado si existen elementos tales que I ⊆ [ a , b ] . Todo intervalo que se pueda representar en notación de intervalos es obviamente acotado, pero la recíproca no es cierta. 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 ínfimo ni supremo en  P , por lo que no se puede escribir en notación de intervalos utilizando elementos de  P . ${\displaystyle a,b\in P}$

Un conjunto parcial se denomina localmente finito si cada intervalo acotado es finito. Por ejemplo, los números enteros son localmente finitos según su orden natural. El orden lexicográfico en el producto cartesiano no es localmente finito, ya que (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Utilizando la notación de intervalo, la propiedad " a está cubierto por b " se puede reformular de forma 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 conocidas como órdenes de intervalo .

Véase 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 conjuntos parciales 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
• Conjunto  parcialmente ordenado, dotado de una función de rango.Pages displaying wikidata descriptions as a fallback
• Álgebra de incidencia  : Álgebra asociativa utilizada en combinatoria, una rama de las matemáticas.
• Retículo  – Conjunto cuyos pares tienen mínimos y máximos
• Conjunto parcial finito localmente  – MatemáticasPages displaying wikidata descriptions as a fallbackPages displaying short descriptions with no spaces
• Función de Möbius en conjuntos parciales  : álgebra asociativa utilizada en combinatoria, una rama de las matemáticas
• Colección de conjuntos anidados
• Ordenar politopo
• Campo ordenado  – Objeto algebraico con una estructura ordenada
• Grupo ordenado  – Grupo con un orden parcial compatiblePages displaying short descriptions of redirect targets
• Espacio vectorial ordenado  – Espacio vectorial con un orden parcial
• Topología poset , un tipo de espacio topológico que se puede definir a partir de cualquier poset
• Continuidad de Scott : continuidad de una función entre dos órdenes parciales.
• Semirretículo  – 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.
• Dominancia estocástica  – 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
• Lema de Zorn  – Proposición matemática equivalente al axioma de elección

Notas

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

Citas

1. Wallis, WD (14 de marzo de 2013). Guía para principiantes de matemáticas discretas. Springer Science & Business Media. pág. 100. ISBN 978-1-4757-3826-1.
2. Simovici, Dan A. y Djeraba, Chabane (2008). "Conjuntos parcialmente ordenados". Herramientas matemáticas para la minería de datos: teoría de conjuntos, órdenes parciales, combinatoria . Springer. ISBN 9781848002012.
3. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). "Cierres transitivos de relaciones binarias I". Acta Universitatis Carolinae. Mathematica et Physica . 48 (1). Praga: Facultad de Matemáticas – Física de la Universidad Carolina: 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 sobre ordenamientos". Logic and Proof (edición 3.18.4) . Consultado el 24 de julio de 2021. Por lo tanto, podemos pensar en cada orden parcial como si en realidad fuera un par, que consta de un orden parcial débil y uno estricto asociado.
6. Rounds, William C. (7 de marzo de 2002). "Diapositivas de las clases" (PDF) . EECS 203: MATEMÁTICA DISCRETA . Consultado el 23 de julio de 2021 .
7. Kwong, Harris (25 de abril de 2018). "7.4: Ordenamiento parcial y total". Un cuaderno 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 x e y en el conjunto parcial. Si x < y , devuelve −1. Si x = y , devuelve 0. Si x > y , devuelve 1. Si x e y no son comparables, devuelve None.
9. Chen, Peter; Ding, Guoli; Seiden, Steve. On Poset Merging (PDF) (Informe técnico). pág. 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, Virgile; Jaume, Mathieu (11 de septiembre de 2003). Realización de pruebas en una jerarquía de estructuras matemáticas. CALCULEMUS-2003 – 11.º Simposio sobre la integración de la computación simbólica y el razonamiento mecanizado. Roma, Italia: Aracne. pp. 89–100.
11. Merrifield, Richard E.; Simmons, Howard E. (1989). Métodos topológicos en química . Nueva York: John Wiley & Sons. pp. 28. ISBN 0-471-83817-9. Recuperado 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 del producto y orden lexicográfico", Basic Posets , 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 la elección . Dover Publications . ISBN. 978-0-486-46624-8.
17. Ward, LE Jr (1954). "Espacios topológicos parcialmente ordenados". Actas de la American Mathematical Society . 5 (1): 144–161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

Referencias

• Davey, BA; Priestley, HA (2002). Introducción a los enrejados y el 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 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. Vol. 132. Cambridge University Press. 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. Cambridge Studies in Advanced Mathematics. Vol. 49. Cambridge University Press. ISBN 0-521-66351-2.
• Eilenberg, S. (2016). Fundamentos de topología algebraica . Princeton University Press.
• Kalmbach, G. (1976). "Extensión de la teoría de homología a conjuntos parcialmente ordenados". J. Reine Angew. Math . 280 : 134–156.

Enlaces externos

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