Conjunto parcialmente ordenado

Relaciones binarias transitivas en a mi
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Total, Semiconnex Anti- reflexivo Relación de equivalencia Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido anticipado (cuasi pedido) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Orden parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido anticipado total ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Pedido total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Pedido previo al pozo ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Bien-cuasi-ordenamiento ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Buen orden ✗ Y Y Y ✗ ✗ Y ✗ ✗ Enrejado ✗ Y ✗ ✗ Y Y Y ✗ ✗ Unión de semirrejilla ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Conocer-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Orden parcial estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden débil estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden total estricta ✗ Y Y ✗ ✗ ✗ ✗ Y Y Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Definiciones, para todos y${\estilo de visualización a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ y }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ o }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}$ ${\estilo de visualización aRa}$ ${\displaystyle {\text{no }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{no }}bRa\end{aligned}}}$
Yindica que la propiedad de la columna siempre es verdadera para el término de la fila (a la izquierda), mientras que ✗ indica que la propiedad no está garantizada en general (puede cumplirse o no). Por ejemplo, que toda relación de equivalencia es simétrica, pero no necesariamente antisimétrica, se indica con en la columna "Simétrica" ​​y ✗ en la columna "Antisimétrica", respectivamente.Y Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : para todo si y entonces La definición de un término puede requerir propiedades adicionales que no están enumeradas en esta tabla.${\estilo de visualización R}$${\estilo de visualización a,b,c,}$${\estilo de visualización aRb}$${\estilo de visualización bRc}$${\estilo de visualización aRc.}$

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 )}$${\estilo de visualización X}$${\estilo de visualización P}$${\estilo de visualización \leq}$${\estilo de visualización X}$${\estilo de visualización X}$

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.

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:${\estilo de visualización P}$${\displaystyle a,b,c\en 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í.${\estilo de visualización a\leq b}$${\displaystyle b\leq a}$${\estilo de visualización a=b}$
3. Transitividad : si y entonces .${\estilo de visualización a\leq b}$${\displaystyle b\leq c}$${\displaystyle a\leq c}$

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

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${\estilo de visualización P}$${\displaystyle a,b,c\en P:}$

1. Irreflexividad : es decir, ningún elemento está relacionado consigo mismo (también llamado antirreflexivo).${\displaystyle \neg \izquierda(a<a\derecha)}$
2. Asimetría : si entonces no .${\estilo de visualización a<b}$${\displaystyle b<a}$
3. Transitividad : si y entonces .${\estilo de visualización a<b}$${\estilo de visualización 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 .

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:${\estilo de visualización P}$${\estilo de visualización \leq}$${\displaystyle a\leq a;}$${\displaystyle <\;:=\ \leq \ \setminus \ \Delta _{P}}$${\displaystyle \Delta _{P}:=\{(p,p):p\en P\}}$${\displaystyle P\times P}$${\estilo de visualización \;\setminus \;}$${\estilo de visualización P}$${\displaystyle \leq \;:=\;\Delta _{P}\;\cup \;<\;}$${\estilo de visualización \leq}$$${\displaystyle a<b{\text{ si }}a\leq b{\text{ y }}a\neq b.}$$${\estilo de visualización \leq}$$${\displaystyle a\leq b{\text{ si }}a<b{\text{ o }}a=b.}$$

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}}}$${\estilo de visualización R}$${\displaystyle R^{\text{op}}}$${\estilo de visualización R}$${\displaystyle xR^{\text{op}}y}$${\estilo de visualización yRx}$

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]${\estilo de visualización P}$${\estilo de visualización \leq}$${\displaystyle \leq ,}$ ${\estilo de visualización <,}$ ${\estilo de visualización \geq ,}$${\estilo de visualización >}$${\estilo de visualización \leq}$${\estilo de visualización P}$${\estilo de visualización <}$${\estilo de visualización P}$${\estilo de visualización \leq}$${\estilo de visualización \geq}$${\estilo de visualización \leq}$${\estilo de visualización >}$${\estilo de visualización <}$${\displaystyle (P,\leq )}$${\estilo de visualización (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 }$

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 <}$

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.

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 .

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.

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 que sean 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\}.}$

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\}\}.}$

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\},}$

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} }$

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 ).

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^{*}]}$

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 .

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 .

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.}$

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 .

Wikimedia Commons tiene medios relacionados con el diagrama de Hasse.