Conjunto parcialmente ordenado

Set ordered by a transitive, antisymmetric, and reflexive binary relation

Relaciones binarias transitivas
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico También conocido como: Total, Semiconnex Antirreflejos Relación de equivalencia ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Orden parcial ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ Reserva total ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Orden total ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ Ordenamiento previo ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Bien casi ordenado ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ Bien ordenado ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ Enrejado ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ Unión-semirrejilla ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ Encuentro-semilattice ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ Orden parcial estricto ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Orden estrictamente débil ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ Orden total estricto ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✓ Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Definiciones: ${\displaystyle \scriptstyle {{\text{For all}}\,a,b\,{\text{and}}\,S\neq \varnothing :}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow bRa}}$ ${\displaystyle \scriptstyle {aRb\,{\text{and}}\,bRa\Rightarrow a=b}}$ ${\displaystyle \scriptstyle {a\neq b\Rightarrow aRb\,{\text{or}}\,bRa}}$ ${\displaystyle \scriptstyle {\min S\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {a\vee b\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {a\wedge b\,{\text{exists}}}}$ ${\displaystyle \scriptstyle {aRa}}$ ${\displaystyle \scriptstyle {{\text{not}}\,aRa}}$ ${\displaystyle \scriptstyle {aRb\Rightarrow {\text{not}}\,bRa}}$
Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Aquí se enumeran las propiedades adicionales que puede satisfacer una relación homogénea.${\displaystyle R}$${\displaystyle \scriptstyle {{\text{For all}}\,a,b,c,{\text{ if }}aRb{\text{ and }}bRc{\text{ then }}aRc}.}$

En matemáticas , especialmente en la teoría del orden , un conjunto parcialmente ordenado (también poset ) formaliza y generaliza el concepto intuitivo de un ordenamiento, secuenciación o disposición de los elementos de un conjunto . Un poset consiste en un conjunto junto con una relación binaria que indica que, para ciertos pares de elementos en el conjunto, uno de los elementos precede al otro en el ordenamiento. La relación en sí se llama "orden parcial". La palabra parcialen los nombres "orden parcial" y "conjunto parcialmente ordenado" se utiliza como una indicación de que no todos los pares de elementos deben ser comparables. Es decir, puede haber pares de elementos para los que ningún elemento precede al otro en el poset. Por tanto, los pedidos parciales generalizan los pedidos totales , en los que cada par es comparable.

Definición informal

Un orden parcial define una noción de comparación. Dos elementos x y y pueden presentarse en cualquiera de las cuatro relaciones mutuamente excluyentes entre sí: o bien x  <  y , o x  =  y o x  >  y , o x y y son incomparable (ninguno de los otros tres). Por el contrario, un conjunto totalmente ordenado sigue a la tricotomía y descarta la posibilidad de incomparabilidad: todos los pares de elementos son comparables.

Un conjunto con un orden parcial se denomina conjunto parcialmente ordenado (también llamado poset ). El término conjunto ordenado también se utiliza a veces, siempre que quede claro por el contexto que no se refiere a ningún otro tipo de orden. En particular, los conjuntos totalmente ordenados también pueden denominarse "conjuntos ordenados", especialmente en áreas donde estas estructuras son más comunes que los conjuntos.

Un poset se puede visualizar a través de su diagrama de Hasse , que representa la relación de ordenamiento. ^[1]

Definicion formal

Podemos considerar un orden parcial como una tupla de 3 , ^[2] , o incluso una tupla de 5 , ^{[ cita requerida ]} donde y son órdenes parciales no estrictas y y son órdenes parciales estrictas.${\displaystyle (P,\leq ,<)}$${\displaystyle (P,\leq ,<,\geq ,>)}$${\displaystyle (P,\leq )}$${\displaystyle (P,\geq )}$${\displaystyle (P,<)}$${\displaystyle (P,>)}$

Notación

Cualquiera de las cuatro relaciones de un conjunto determinado determina de forma única las otras tres. Por lo tanto, como una cuestión de notación, podemos escribir o , y asumir que las otras relaciones están definidas apropiadamente. La definición mediante un orden parcial no estricto es la más común. Algunos autores utilizan diferentes símbolos que tal como ^[3] o ^[4] para distinguir órdenes parciales de los pedidos totales.${\displaystyle \leq ,<,\geq ,{\text{ and }}>}$${\displaystyle (P,\leq )}$${\displaystyle (P,<)}$${\displaystyle \leq }$${\displaystyle \leq }$${\displaystyle \sqsubseteq }$${\displaystyle \preceq }$

Pedido parcial no estricto

Un reflexivo oEl orden parcial no estricto ^[5] es unarelación binaria homogénea≤ sobre unconjunto que esreflexivo,antisimétricoytransitivo. Es decir, para tododebe satisfacer:${\displaystyle P}$${\displaystyle a,b,c\in P,}$

1. ${\displaystyle a\leq a}$( reflexividad : cada elemento está relacionado consigo mismo).
2. if ( antisimetría : no se preceden dos elementos distintos).${\displaystyle a\leq b{\text{ and }}b\leq a{\text{ then }}a=b}$
3. if ( transitividad : si un primer elemento está relacionado con un segundo elemento y, a su vez, ese elemento está relacionado con un tercer elemento, entonces el primer elemento está relacionado con el tercer elemento).${\displaystyle a\leq b{\text{ and }}b\leq c{\text{ then }}a\leq c}$

En otras palabras, un orden parcial no estricto es un preorden antisimétrico .

Orden parcial estricto

Un irreflexivo oel orden parcial estricto , también conocido como preorden estricto ,es unarelación binariahomogéneaque esirreflexiva,transitivayasimétrica; es decir, satisface las siguientes condiciones para todos${\displaystyle P}$${\displaystyle P}$${\displaystyle a,b,c\in P:}$

1. Irreflexividad : no${\displaystyle a<a,}$
2. Transitividad : si y${\displaystyle a<b{\text{ and }}b<c{\text{ then }}a<c,}$
3. Asimetría : si no${\displaystyle a<b}$${\displaystyle b<a.}$

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. ^[6] Entonces, la misma estructura se define omitiendo la irreflexividad o la asimetría (pero no ambas).

Equivalencia de órdenes parciales estrictas y no estrictas

Las órdenes parciales estrictas y no estrictas de un conjunto están estrechamente relacionadas. 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 es la diagonal de y denota la resta de conjuntos . A la inversa, un orden parcial estricto <on puede convertirse en un orden parcial no estricto uniendo todas las relaciones de esa forma; es decir, es un pedido parcial no estricto. Por tanto, si es un orden parcial no estricto, entonces el correspondiente orden parcial estricto <es el núcleo irreflexivo dado por${\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.}$$

Por el contrario, si <es un orden parcial estricto, entonces el orden parcial no estricto correspondiente es el cierre reflexivo dado por:${\displaystyle \leq }$

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

Órdenes duales

Artículo principal: Dualidad (teoría del orden)

El dual (u opuesto ) de un orden parcial no estricto se define dejando ser la relación inversa de , es decir, si y sólo si . El dual también es un orden parcial no estricto. ^[7] El dual de es , entonces y cada uno puede definirse en términos del otro. De manera análoga, se puede definir el dual de un orden parcial estricto, y luego y son órdenes parciales estrictos que se pueden definir cada uno en términos del otro.${\displaystyle (P,\geq )}$${\displaystyle (P,\leq )}$${\displaystyle \geq }$${\displaystyle \leq }$${\displaystyle x\geq y}$${\displaystyle y\leq x.}$${\displaystyle (P,\geq )}$${\displaystyle (P,\leq )}$${\displaystyle (P,\geq )}$${\displaystyle (P,\leq )}$${\displaystyle (P,<)}$${\displaystyle (P,>)}$

Ejemplos de

Los ejemplos estándar de postulados que surgen en matemáticas incluyen:

• Los números reales , o en general cualquier conjunto totalmente ordenado, ordenados por la relación estándar menor o igual ≤, es un orden parcial no estricto.
• En los números reales, la relación habitual menor que <es un orden parcial estricto y lo mismo ocurre con la relación habitual mayor que > en${\displaystyle P:=\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 de potencias ) ordenados por inclusión (ver la figura en la parte superior derecha). De manera similar, el conjunto de secuencias ordenadas por subsecuencia y el conjunto de cadenas ordenadas por subcadena .
• El conjunto de números naturales equipados con la relación de divisibilidad .
• El conjunto de vértices de un gráfico acíclico dirigido ordenado por accesibilidad .
• El conjunto de subespacios de un espacio vectorial ordenados por inclusión.
• Para un conjunto P parcialmente ordenado , el espacio de secuencia que contiene todas las secuencias de elementos de P , donde la secuencia a precede a la secuencia b si cada elemento de a precede al elemento correspondiente de 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 de X a P , donde f ≤ g si y solo si f ( x ) ≤ g ( x ) para todos${\displaystyle x\in X.}$
• Una cerca , un conjunto parcialmente ordenado definido por una secuencia alterna de relaciones de orden a < b > c < d ...
• El conjunto de los acontecimientos en la relatividad especial y, en la mayoría de los casos, ^[8] la relatividad general , donde por dos eventos X y Y , X ≤ Y si y sólo si Y está en el futuro cono de luz de X . Un evento Y sólo puede ser causalmente afectada por X si X ≤ Y .

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

Órdenes sobre el producto cartesiano de conjuntos parcialmente ordenados

Cierre reflexivo del estricto pedido directo de productos en Los elementos cubiertos por (3,3) y que cubren (3,3) están resaltados en verde y rojo, respectivamente.${\displaystyle \mathbb {N} \times \mathbb {N} .}$

Pedido de producto en ${\displaystyle \mathbb {N} \times \mathbb {N} }$

Orden lexicográfico en ${\displaystyle \mathbb {N} \times \mathbb {N} }$

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 figuras):

• el orden lexicográfico : ( a , b ) ≤ ( c , d ) si a < c o ( a = c y b ≤ d );
• el pedido de productos : ( a , b ) ≤ ( c , d ) si un ≤ c y b ≤ d ;
• el cierre reflexivo del producto directo de los correspondientes órdenes estrictos: ( a , b ) ≤ ( c , d ) si ( a < c y b < d ) o ( a = c y b = d ).

Los tres se pueden definir de manera similar para el producto cartesiano de más de dos conjuntos.

Aplicado a espacios vectoriales ordenados sobre el mismo campo , el resultado es en cada caso también un espacio vectorial ordenado.

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 ^[9] (o suma lineal ), ^[10] Z = X ⊕ Y , definida en la unión de los conjuntos subyacentes X e Y por el orden a ≤ _Z b si y solo si:

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

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

Los órdenes parciales en serie-paralelos se forman a partir de la operación de suma ordinal (en este contexto llamada composición en serie) y otra operación llamada composición en paralelo. La composición paralela es la unión disjunta de dos conjuntos parcialmente ordenados, sin relación de orden entre los elementos de un conjunto y los elementos del otro conjunto.

Nociones derivadas

El diagrama de Hasse del conjunto de todos los subconjuntos de un conjunto de tres elementos ordenados por inclusión. Los distintos conjuntos en el mismo nivel horizontal son incomparables entre sí. Algunas otras parejas, como y también son incomparables.${\displaystyle \{x,y,z\},}$${\displaystyle \{x\}}$${\displaystyle \{y,z\},}$

Los ejemplos usan el poset que consiste en el conjunto de todos los subconjuntos de un conjunto de tres elementos ordenados por inclusión de conjuntos (ver figura). ${\displaystyle (P(\{x,y,z\}),\subseteq )}$${\displaystyle \{x,y,z\},}$

• Cuando a ≤ b , decimos que a está relacionado con b . Esto no implica que b también esté relacionado con a , porque la relación no necesita ser simétrica . Por ejemplo, está relacionado pero no al revés.${\displaystyle \{x\},}$${\displaystyle \{x,y\},}$
• Dada elementos un , b de parcialmente ordenado conjunto P , si un ≤ b o b ≤ una , a continuación, una y b son comparables . 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 parcial bajo el cual cada par de elementos es comparable se llama orden total u orden lineal ; un conjunto totalmente ordenado también se llama cadena (por ejemplo, los números naturales con su orden estándar). Por ejemplo, es una cadena.${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$
• Un subconjunto de un poset en el que no hay dos elementos distintos que sean comparables se denomina antichain . Por ejemplo, el conjunto de singletons ${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• Un elemento una se dice que es estrictamente inferior a un elemento b , si un ≤ 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 tanto un ≤ b y son verdad, y un ≤ c ≤ b es falsa para cada c con Usando el orden estricto <, la relación una ⋖ b puede ser reformulada equivalentemente como " un <${\displaystyle a\neq b}$${\displaystyle a\neq c\neq b.}$b pero no a < b < c para cualquier c ". Por ejemplo, está cubierto por pero no está cubierto por${\displaystyle \{x\}}$${\displaystyle \{x,z\},}$${\displaystyle \{x,y,z\}.}$

Extrema

La figura de arriba con los elementos mayores y menores 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 un elemento mayor ni menor .

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

• Elemento mayor y elemento menor: Un elemento es un elemento mayor si para cada elemento Un elemento es un elemento mínimo si para cada elemento Un poset solo puede tener un elemento mayor o menor. En nuestro ejemplo de ejecución, el conjunto es el elemento más grande y el menor.${\displaystyle g\in P}$${\displaystyle a\in P,a\leq g.}$${\displaystyle m\in P}$${\displaystyle a\in P,m\leq a.}$${\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 de lo contrario puede haber más de un elemento máximo, y de manera similar para elementos mínimos y elementos mínimos. En nuestro ejemplo de ejecución, y son los elementos máximo y mínimo. Eliminando estos, hay 3 elementos máximos y 3 elementos mínimos (ver figura).${\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 un  ≤  x , para cada elemento de una en una . En particular, x no necesitan estar en un ser un límite superior de A . Del mismo modo, un elemento x en P es un límite inferior de A si un  ≥  x , para cada elemento de una en una . Un elemento mayor de P es un límite superior deP sí mismo, y un elemento de menos es un límite inferior de P . En nuestro ejemplo, el conjunto es un límite superior para la colección de elementos.${\displaystyle \{x,y\}}$${\displaystyle \{\{x\},\{y\}\}.}$

Enteros no negativos, ordenados por divisibilidad

Como otro ejemplo, considere los números enteros positivos , ordenados por divisibilidad: 1 es un elemento mínimo, ya que divide a todos los demás elementos; por otro lado, este poset no tiene un elemento mayor (aunque si uno incluye 0 en el poset, que es un múltiplo de cualquier número entero, ese sería un elemento mayor; ver figura). Este conjunto parcialmente ordenado ni siquiera tiene elementos máximos, ya que cualquier g divide, por ejemplo, 2 g , que es distinto de él, por lo que g no es máximo. Si se excluye el número 1, mientras se mantiene la divisibilidad ordenando los elementos mayores que 1, entonces el poset resultante no tiene un elemento mínimo, sino un número primo.es un elemento mínimo para ello. En este poset, 60 es un límite superior (aunque no al menos un límite superior) del subconjunto que no tiene ningún límite inferior (ya que 1 no está en el poset); por otro lado, 2 es un límite inferior del subconjunto de potencias de 2, que no tiene ningún límite superior.${\displaystyle \{2,3,5,10\},}$

Mapeos entre conjuntos parcialmente ordenados

Isomorfismo de orden entre los divisores de 120 (parcialmente ordenados por divisibilidad) y los subconjuntos de divisor cerrado de {2, 3, 4, 5, 8 } (parcialmente ordenados por inclusión de conjuntos)

Figura 1 : Mapa que conserva el orden, pero no refleja el orden (ya que f ( u ) ≼ f ( v ), pero no ).${\displaystyle u\leq v}$

Dados dos conjuntos parcialmente ordenados ( S , ≤) y ( T , ≼), ^{[nota 1]} una función se llama preservadora de orden , o monótona , o isotona , si para todos implica f ( x ) ≼ f ( y ). Si ( U , ≲) también es un conjunto parcialmente ordenado, y ambos y conservan el orden, su composición también conserva el orden. Una función se llama reflejo de orden si para todo f ( x ) ≼ f ( y${\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,}$ ) implica Si conserva el orden y refleja el orden, entonces se denomina incrustación de orden de ( S , ≤) en ( T , ≼). En el último caso, es necesariamente inyectiva , ya que implica a su vez de acuerdo con la antisimetría de Si una orden-incrustación de entre dos Posets S y T existe, se dice que S puede ser incrustado en T . Si una inserción de orden es biyectiva , se denomina isomorfismo de orden y los órdenes parciales ( S${\displaystyle x\leq y.}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f(x)=f(y)}$${\displaystyle x\leq y{\text{ and }}y\leq x}$${\displaystyle x=y}$${\displaystyle \leq .}$${\displaystyle f:S\to T}$, ≤) y ( T , ≼) se dice que son isomorfos . Los órdenes isomórficos tienen diagramas de Hasse estructuralmente similares (véase la imagen de la derecha). Se puede demostrar que si existen mapas que preservan el orden y que y produce la función de identidad en S y T , respectivamente, entonces S y T son orden-isomorfos. ^[12]${\displaystyle f:S\to T}$${\displaystyle g:T\to U}$${\displaystyle g\circ f}$${\displaystyle f\circ g}$

Por ejemplo, un mapeo del conjunto de números naturales (ordenados por divisibilidad) al conjunto de potencias de números naturales (ordenados por inclusión de conjuntos) se puede definir tomando cada número al conjunto de sus divisores primos . Conserva el orden: si divide, entonces cada divisor primo de es también un divisor primo de Sin embargo, no es inyectivo (ya que asigna 12 y 6 a ) ni refleja el orden (ya que 12 no divide 6). En su lugar, tomar cada número al conjunto de sus divisores de potencia principales define un mapa que preserva el orden, refleja el orden y, por lo tanto, incrusta el orden. No es un orden-isomorfismo (ya que, por ejemplo, no asigna ningún número al conjunto${\displaystyle f:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$${\displaystyle x}$${\displaystyle y,}$${\displaystyle x}$${\displaystyle y.}$${\displaystyle \{2,3\}}$${\displaystyle g:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$${\displaystyle \{4\}}$), pero se puede convertir en uno restringiendo su codominio a § La figura 1 muestra un subconjunto de y su imagen isomorfa bajo La construcción de tal orden-isomorfismo en un conjunto de potencia se puede generalizar a una amplia clase de órdenes parciales, denominada distributiva celosías , ver " Teorema de representación de Birkhoff ".${\displaystyle g(\mathbb {N} ).}$ ${\displaystyle \mathbb {N} }$${\displaystyle g.}$

Número de pedidos parciales

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

Número de relaciones binarias de n elementos de diferentes tipos

Elementos	Ninguna	Transitivo	Reflexivo	Hacer un pedido	Orden parcial	Reserva total	Orden total	Relación de equivalencia
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	dieciséis	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3.994	4.096	355	219	75	24	15
norte	2 n 2		2 n 2 - n			${\textstyle \sum _{k=0}^{n}k!}$S ( n , k )	n !	${\textstyle \sum _{k=0}^{n}}$S ( n , k )
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

El número de pedidos parciales estrictos es el mismo que el de pedidos parciales.

Si el recuento se realiza solo hasta el isomorfismo, se obtiene la secuencia 1, 1, 2, 5, 16, 63, 318, ... (secuencia A000112 en la OEIS ).

Extensión lineal

Un orden parcial en un conjunto es una extensión de otro orden parcial en siempre que para todos los elementos siempre sea ​​el caso que Una extensión lineal sea ​​una extensión que también sea un orden lineal (es decir, total). Como ejemplo clásico, el orden lexicográfico de conjuntos totalmente ordenados es una extensión lineal de su orden de productos. Cada pedido parcial se puede extender a un pedido total ( principio de extensión de pedido ). ^[13]${\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 .

Gráficos acíclicos dirigidos

Los órdenes parciales estrictos corresponden directamente a los gráficos acíclicos dirigidos (DAG). Si un gráfico se construye tomando cada elemento de como un nodo y cada elemento de como un borde, entonces cada orden parcial estricto es un DAG, y el cierre transitivo de un DAG es tanto un orden parcial estricto como un DAG en sí mismo. . Por el contrario, un orden parcial no estricto tendría bucles propios en cada nodo y, por lo tanto, no sería un DAG.${\displaystyle P}$${\displaystyle \leq }$

En teoría de categorías

Cada poset (y cada conjunto preordenado ) puede ser considerado como una categoría donde, para objetos y hay como máximo un morfismo de a Más explícitamente, sea hom ( x , y ) = {( x , y )} si x ≤ y ( y de lo contrario el conjunto vacío) y estas categorías a veces se denominan posetal .${\displaystyle x}$${\displaystyle y,}$${\displaystyle x}$${\displaystyle y.}$${\displaystyle (y,z)\circ (x,y)=(x,z).}$

Los Posets son equivalentes entre sí si y solo si son isomorfos . En un poset, el elemento más pequeño, si existe, es un objeto inicial , y el elemento más grande, si existe, es un objeto terminal . Además, cada conjunto preordenado es equivalente a un poset. Finalmente, cada subcategoría de un poset es isomorfismo-cerrado .

Órdenes parciales en espacios topológicos

Artículo principal: espacio parcialmente ordenado

Si es un conjunto parcialmente ordenado al que también se le ha dado la estructura de un espacio topológico , entonces se acostumbra suponer que es un subconjunto cerrado del espacio de producto topológico Bajo este supuesto, las relaciones de orden parcial se comportan bien en los límites en el sentido de que si y para todos entonces ^[14]${\displaystyle P}$${\displaystyle \{(a,b):a\leq b\}}$ ${\displaystyle P\times P.}$${\displaystyle a_{i}\to a,}$${\displaystyle b_{i}\to b,}$${\displaystyle i}$ ${\displaystyle a_{i}\leq b_{i},}$${\displaystyle a\leq b.}$

Intervalos

Un intervalo en un poset P es un subconjunto I de P con la propiedad de que, para cualquier x y y en I y cualquier z en P , si x ≤ z ≤ y , a continuación, z es también en I . (Esta definición generaliza la definición de intervalo para números reales).

Para a ≤ b , el intervalo cerrado [ a , b ] es el conjunto de elementos x que satisfacen a ≤ x ≤ b (es decir, a ≤ x y x ≤ b ). Contiene al menos los elementos una y b .

Usando la correspondiente relación estricta "<", el intervalo abierto ( a , b ) es el conjunto de elementos x que satisfacen a < x < b (es decir, a < x y x < b ). Un intervalo abierto puede estar vacío incluso si a < b . Por ejemplo, el intervalo abierto (1, 2) en los enteros está vacío ya que no hay enteros I tales que 1 < I <2 .

Los intervalos semiabiertos [ a , b ) y ( a , b ] se definen de manera similar.

A veces, las definiciones se amplían para permitir a > b , en cuyo caso el intervalo está vacío.

Un intervalo I está acotado si existen elementos tales que I ⊆ [ a , b ] . Cada intervalo que se puede representar en notación de intervalo está obviamente acotado, pero lo contrario no es cierto. Por ejemplo, sea P = (0, 1) ∪ (1, 2) ∪ (2, 3) como una subposición de los números reales . El subconjunto (1, 2) es un intervalo acotado, pero no tiene infimum o supremo en P , por lo que no se puede escribir en notación de intervalos usando elementos de P .${\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 bajo su orden natural. El orden lexicográfico del producto cartesiano no es localmente finito, ya que (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Usando la notación de intervalo, la propiedad " a está cubierta por b " se puede reformular de manera equivalente como${\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

• Antimatroid , una formalización de pedidos en un conjunto que permite familias de pedidos más generales que posets
• Conjunto causal , un enfoque poset a la gravedad cuántica
• Gráfico de comparabilidad
• Orden parcial completa
• Conjunto dirigido  : conjunto con un pedido anticipado en el que dos elementos son siempre menores o iguales a un tercer elemento.
• Poset calificado
• Álgebra de incidencia
• Lattice  - Estructura abstracta estudiada en las subdisciplinas matemáticas de la teoría de órdenes y el álgebra abstracta.
• Poset localmente finito
• Función de moebius en posets
• Colección de conjuntos anidados
• Solicitar politopo
• Campo ordenado
• Grupo ordenado
• Espacio vectorial ordenado
• Topología de Poset , una especie de espacio topológico que se puede definir desde cualquier poset
• Continuidad de Scott : continuidad de una función entre dos órdenes parciales.
• Semirredura
• Semiorder
• Dominio estocástico
• Orden estricto débil : orden parcial estricto "<" en el que la relación "ni a < b ni b < a " es transitiva.
• Orden total  : ordenamiento matemático donde se pueden comparar todos los elementos
• Árbol (estructura de datos de inclusión de conjuntos)
• Lema de Zorn  : proposición matemática equivalente al axioma de elección

Notas

1. Los pedidos parcialesy ≼ pueden ser diferentes, pero no es necesario.${\displaystyle \leq }$

Citas

1. 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 ...
2. Avigad, Jeremy; Lewis, Robert Y .; van Doorn, Floris (29 de marzo de 2021). "13.2. Más sobre pedidos". Lógica y prueba (versión 3.18.4 ed.) . Consultado el 24 de julio de 2021 . Por tanto, podemos pensar en cada orden parcial como si fuera realmente un par, que consta de un orden parcial débil y uno estricto asociado.
3. Rondas, William C. (7 de marzo de 2002). "Diapositivas de conferencias" (PDF) . EECS 203: MATEMÁTICAS DISCRETAS . Consultado el 23 de julio de 2021 .
4. Kwong, Harris (25 de abril de 2018). "7.4: Pedidos parciales y totales". Un libro de trabajo en espiral para matemáticas discretas . Consultado el 23 de julio de 2021 .
5. 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 . Saltador. ISBN 9781848002012.
6. Flaška, V .; Ježek, J .; Kepka, T .; Kortelainen, J. (2007). Clausura transitiva de Binary Relaciones I . Praga: Escuela de Matemáticas - Universidad Charles de Física. pag. 1.Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
7. Davey, BA; Priestley, HA (18 de abril de 2002). Introducción a las celosías y el orden . Prensa de la Universidad de Cambridge. págs. 14-15. ISBN 978-0-521-78451-1.
8. Ver relatividad general # Viaje en el tiempo
9. Neggers, J .; Kim, Hee Sik (1998), "4.2 Orden de productos y orden lexicográfico", Basic Posets , World Scientific, págs. 62–63, ISBN 9789810235895
10. Davey, BA; Priestley, HA (2002). Introducción a las celosías y el orden (Segunda ed.). Nueva York: Cambridge University Press. págs.  17-18 . ISBN 0-521-78451-4. - En la primera edición (1990, ISBN 0-521-36766-2), la definición se encuentra en las mismas páginas.
11. PR Halmos (1974). Teoría de conjuntos ingenua . Saltador. pag. 82 . ISBN 978-1-4757-1645-0.
12. Davey y Priestley (2002 , págs. 23-24) error de harvtxt: objetivos múltiples (2x): CITEREFDaveyPriestley2002 ( ayuda )
13. Jech, Thomas (2008) [1973]. El axioma de la elección . Publicaciones de Dover . ISBN 978-0-486-46624-8.
14. 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

• Deshpande, Jayant V. (1968). "Sobre la continuidad de una orden parcial" . Actas de la American Mathematical Society . 19 (2): 383–386. doi : 10.1090 / S0002-9939-1968-0236071-7 .
• Schmidt, Gunther (2010). Matemáticas relacionales . Enciclopedia de Matemáticas y sus Aplicaciones. 132 . Prensa de la Universidad de Cambridge. ISBN 978-0-521-76268-7.
• Bernd Schröder (11 de mayo de 2016). Conjuntos ordenados: una introducción con conexiones desde la combinatoria a la topología . Birkhäuser. ISBN 978-3-319-29788-0.
• Stanley, Richard P. (1997). Combinatoria enumerativa 1 . Estudios de Cambridge en Matemáticas Avanzadas. 49 . Prensa de la Universidad de Cambridge. ISBN 0-521-66351-2.

enlaces externos

Wikimedia Commons tiene medios relacionados con el diagrama de Hasse .

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