Conjunto parcialmente ordenado

Relaciones binarias
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple 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 ✗ ✓ ✗ ✗ ✗ ✓
Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Todas las definiciones requieren tácitamente transitividad y reflexividad .

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.

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

Formalmente, un orden parcial es cualquier relación binaria que es reflexiva (cada elemento es comparable a sí mismo), antisimétrica (no hay dos elementos diferentes que se precedan entre sí) y transitiva (el comienzo de una cadena de relaciones de precedencia debe preceder al final de la cadena ).

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.

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

Definicion formal

Un orden parcial (no estricto) ^[2] es una relación binaria homogénea ≤ sobre un conjunto P que satisface axiomas particulares que se analizan a continuación. 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 ).

Los axiomas para un orden parcial no estricto establecen que la relación ≤ es reflexiva , antisimétrica y transitiva . Es decir, para todo un , b , y c en P , debe satisfacer:

1. a ≤ a ( reflexividad : todo elemento está relacionado consigo mismo).
2. si a ≤ b y b ≤ a , entonces a = b ( antisimetría : dos elementos distintos no pueden relacionarse en ambas direcciones).
3. si un ≤ b y b ≤ c , a continuación, un ≤ c ( transitividad : si un primer elemento está relacionado con un segundo elemento, y, a su vez, ese elemento está relacionado con un tercer elemento, a continuación, el primer elemento está relacionado con la tercera elemento).

En otras palabras, un pedido parcial es un pedido anticipado antisimétrico .

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.

Para una , b , elementos de un conjunto parcialmente ordenado P , si un ≤ b o b ≤ una , a continuación, una y b son comparables . De lo contrario, son incomparables . En la figura de arriba a la derecha, por ejemplo, { x } y { x ,  y ,  z } son comparables, mientras que { x } e { y } no lo son. 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). Un subconjunto de un conjunto en el que no hay dos elementos distintos que sean comparables se llama antichain (por ejemplo, el conjunto de singletons {{ x }, { y }, { z }} en la figura superior derecha). Un elemento una se dice que es estrictamente inferior a un elemento b , si un ≤ b y un ≠ b . 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 un ≠ b son verdad, y un ≤ c ≤ b es falsa para cada c con un ≠ c ≠ b . Una definición más concisa se dará a continuación utilizando el orden estricto correspondiente a "≤". Por ejemplo, { x } está cubierto por { x ,  z } en la figura superior derecha, pero no por { x ,  y ,  z }.

Ejemplos de

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

• Los números reales ordenados por la relación estándar menor o igual ≤ (un conjunto totalmente ordenado también).
• 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, ( a _n ) _{n ∈ℕ} ≤ ( b _n ) _{n ∈ℕ} si y solo si a _n ≤ b _n para todos los n en ℕ, es decir, un orden de componentes .
• Para un conjunto X y un conjunto parcialmente ordenado P , el espacio funcional que contiene todas las funciones de X a P , donde f ≤ g si y sólo si f ( x ) ≤ g ( x ) para todo x en 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, ^[3] 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 .

Extrema

Enteros no negativos, ordenados por divisibilidad

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 . El conjunto { x , y } es un límite superior para la colección de elementos {{ x }, { y }} .

Hay varias nociones de elemento "mayor" y "menor" en un poset P , en particular:

• Elemento mayor y elemento menor: Un elemento g en P es un elemento mayor si para cada elemento a en P , a  ≤  g . Un elemento m en P es un elemento mínimo si para cada elemento a en P , a  ≥  m . Un poset solo puede tener un elemento mayor o menor.
• Elementos máximos y elementos mínimos: Un elemento g en P es un elemento máximo si no hay un elemento a en P tal que a  >  g . De manera similar, un elemento m en P es un elemento mínimo si no hay un elemento a en P tal que a  <  m . 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.
• Límites superior e inferior : Para un subconjunto A de P , un elemento x en P es un límite superior de A si un  ≤  x , para cada elemento de una en una . En particular, x no necesitan estar en un ser un límite superior de A . Del mismo modo, un elemento x en P es un límite inferior de A si un  ≥  x , para cada elemento de una en una . Un elemento más grande de P es un límite superior de P en sí, y un elemento de menos es un límite inferior de P .

Por 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 como orden en los elementos mayores que 1, entonces el poset resultante no tiene un elemento mínimo, pero cualquier número primo es un elemento mínimo para él. En este poset, 60 es un límite superior (aunque no al menos un límite superior) del subconjunto {2, 3, 5, 10}, 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.

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

Pedido de producto el ℕ × ℕ

Orden lexicográfico en ℕ × ℕ

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

Diagrama de Hasse de un orden parcial serie-paralelo , formado como la suma ordinal de tres órdenes parciales más pequeños.

Otra forma de combinar dos conjuntos es la suma ordinal ^[4] (o suma lineal ^[5] ), 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. ^[6] La operación de suma ordinal es una de las dos operaciones que se utilizan para formar órdenes parciales serie-paralelas , y en este contexto se denomina composición en serie. La otra operación utilizada para formar estos órdenes, 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) se denomina en este contexto composición paralela.

Órdenes parciales estrictas y no estrictas

Una orden parcial puede ser denominado como un no estricto (o reflexiva ) orden parcial para dar énfasis o contraste con órdenes parciales estrictas . Una orden parcial estricta (o irreflexiva )- también conocido como preorden estricto - en${\displaystyle P}$es una relación binaria homogénea${\displaystyle \,<\,}$ en ${\displaystyle P}$que sea irreflexivo , transitivo y asimétrico ; es decir, satisface las siguientes condiciones para todos${\displaystyle a,b,c\in P}$:

1. Irreflexividad : no a < a ,
2. Transitividad : si a < b y b < c entonces a < c , y
3. Asimetría : si a < b entonces no b < a .

La irreflexividad y la transitividad juntas implican asimetría, ^[7] por lo que una relación homogénea es un orden parcial estricto si y solo si es transitiva e irreflexiva. Además, la asimetría implica irreflexividad ^[7] por lo que una relación homogénea es un orden parcial estricto si y solo si es transitiva y asimétrica. En otras palabras, una relación transitiva es asimétrica si y solo si es irreflexiva.

Por definición, todo orden débil estricto es un orden parcial estricto. En los números reales ${\displaystyle P:=\mathbb {R} ,}$la habitual relación menor${\displaystyle \,<\,}$es un orden parcial estricto y lo mismo es cierto también de la relación mayor que habitual${\displaystyle \,>\,}$ en ${\displaystyle \mathbb {R} .}$

Equivalencia

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

${\displaystyle a<b}$}> Si ${\displaystyle a\leq b}$ y ${\displaystyle a\neq b.}$

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

${\displaystyle a\leq b}$ Si ${\displaystyle a<b}$}> o ${\displaystyle a=b.}$

Esta es la razón para usar la notación ${\displaystyle \,\leq .}$

Usando el orden estricto ${\displaystyle \,<,}$ la relación "${\displaystyle a}$está cubierto por${\displaystyle b}$"se puede reformular de forma equivalente como"${\displaystyle a<b,}$,}> pero no ${\displaystyle a<c<b}$ para cualquier ${\displaystyle c}$".

Gráficos acíclicos dirigidos

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

Inverso y orden dual

La inversa (o inversa) de una relación de orden parcial ≤ es la inversa de ≤. Denominada típicamente ≥, es la relación que satisface x  ≥  y si y solo si y  ≤  x . La inversa de una relación de orden parcial es reflexiva, transitiva y antisimétrica y, por lo tanto, es en sí misma una relación de orden parcial. El orden dual de un conjunto parcialmente ordenado es el mismo conjunto con la relación de orden parcial reemplazada por su inversa. La relación irreflexiva> es a ≥ como

Cualquiera de las cuatro relaciones ≤, <, ≥ y> en un conjunto dado determina de forma única las otras tres.

En general, dos elementos x y y de un orden parcial puede estar 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, la definición de incomparabilidad aquí es diferente de la del orden débil ). Un conjunto totalmente ordenado es aquel que descarta esta cuarta posibilidad: todos los pares de elementos son comparables y luego decimos que la tricotomía es válida. Los números naturales , los enteros , los racionales y los reales están todos totalmente ordenados por su magnitud algebraica (con signo), mientras que los números complejos no lo están. Esto no quiere decir que los números complejos no puedan ordenarse totalmente; que podría, por ejemplo para ellos lexicográficamente a través de x + i y  <  u + i V si y sólo si x  <  u o ( x  =  u y y  <  v ), pero esto no está ordenando por magnitud en cualquier sentido razonable, ya que hace 1 mayor que 100 i . Ordenarlos por magnitud absoluta produce un preorden en el que todos los pares son comparables, pero este no es un orden parcial ya que 1 y yo tenemos la misma magnitud absoluta pero no son iguales, violando la antisimetría.

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)

Mapa que conserva el orden, pero no refleja el orden (ya que f ( u ) ≼ f ( v ), pero no u ≤ v ).

Dados dos conjuntos parcialmente ordenados ( S , ≤) y ( T , ≼), ^[8] una función f : S → T se llama preservadora de orden , o monótona , o isotona , si para todo x e y en S , x ≤ y implica f ( x ) ≼ f ( y ). Si ( U , ≲) también es un conjunto parcialmente ordenado, y tanto f : S → T como g : T → U conservan el orden, su composición g ∘ f  : S → U también preserva el orden. Una función f : S → T se llama orden de reflexión de si para todo x y y en S , f ( x ) ≼ f ( y ) implica x ≤ y . Si f preserva el orden y refleja el orden, entonces se denomina incrustación de orden de ( S , ≤) en ( T , ≼). En el último caso, f es necesariamente inyectiva , ya que f ( x ) = f ( y ) implica x ≤ y e y ≤ x y a su vez x = y según 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 incrustación de orden f : S → T es biyectiva , se denomina isomorfismo de orden , y se dice que los órdenes parciales ( S , ≤) y ( T ,) son isomorfos . Los órdenes isomórficos tienen diagramas de Hasse estructuralmente similares (véase la imagen de la derecha). Se puede demostrar que si mapas orden de preservación f : S → T y g : T → S existen tales que g ∘ f y f ∘ g rendimientos la función identidad en S y T , respectivamente, a continuación, S y T son orden-isomorfo . ^[9]

Por ejemplo, un mapeo f : ℕ → ℙ (ℕ) 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 su primo. divisores . Conserva el orden: si x divide y , entonces cada divisor primo de x es también un divisor primo de y . Sin embargo, no es inyectivo (ya que asigna 12 y 6 a {2, 3}) ni refleja el orden (ya que 12 no divide a 6). En cambio, tomando cada número al conjunto de sus divisores de potencia primos se define un mapa g : ℕ → ℙ (ℕ) 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 {4}), pero puede convertirse en uno restringiendo su codominio a g (ℕ). La imagen de la derecha muestra un subconjunto de ℕ y su imagen isomórfica bajo g . La construcción de tal orden-isomorfismo en un conjunto de potencias se puede generalizar a una amplia clase de órdenes parciales, llamadas redes distributivas , ver " Teorema de representación de Birkhoff ".

Número de pedidos parciales

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

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

Elementos	Alguna	Transitivo	Reflexivo	Hacer un pedido	Orden parcial	Reserva total	Orden total	Relación de equivalencia
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	dieciséis	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65,536	3.994	4.096	355	219	75	24	15
norte	2 n 2		2 n 2 - n			∑n k = 0  k ! S ( n , k )	n !	∑n k = 0  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

Una orden parcial ≤ ^* en un conjunto X es una extensión de otro orden parcial ≤ en X siempre que para todos los elementos x y y de X , siempre que x ≤ y , también es el caso de que x  ≤ ^*  y . Una extensión lineal es una extensión que también es un orden lineal (es decir, total). Como ejemplo clásico, el orden lexicográfico de conjuntos totalmente ordenados es una extensión lineal de su orden de productos. Cada pedido parcial se puede extender a un pedido total ( principio de extensión de pedido ). ^[10]

En informática , los algoritmos para encontrar extensiones lineales de órdenes parciales (representados como órdenes de accesibilidad de gráficos acíclicos dirigidos ) se denominan clasificación topológica .

En teoría de categorías

Cada conjunto parcialmente ordenado (y cada conjunto preordenado ) pueden ser considerados como una categoría donde, para los objetos de x y y , hay a lo sumo un morfismo de x a y . Más explícitamente, sea hom ( x , y ) = {( x , y )} si x ≤ y (y de lo contrario el conjunto vacío) y ( y , z ) ∘ ( x , y ) = ( x , z ). A veces, estas categorías se denominan posetal .

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

Órdenes parciales en espacios topológicos

Si P 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${\displaystyle \{(a,b):a\leq b\}}$es un subconjunto cerrado del espacio de productos topológicos ${\displaystyle P\times P}$. Bajo este supuesto, las relaciones de orden parcial se comportan bien en los límites en el sentido de que si${\displaystyle a_{i}\to a}$, y ${\displaystyle b_{i}\to b}$y para todos ${\displaystyle i}$   ${\displaystyle a_{i}\leq b_{i}}$, luego ${\displaystyle a\leq b}$. ^[11]

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á limitada si existen elementos un y b de P de tal manera que I ⊆ [ un , b ] . Cada intervalo que se puede representar en notación de intervalo está obviamente acotado, pero lo contrario no es cierto. Por ejemplo, sea P = (0, 1) ∪ (1, 2) ∪ (2, 3) como una subposición de los números reales . El subconjunto (1, 2) es un intervalo acotado, pero no tiene infimum o supremo en P , por lo que no se puede escribir en notación de intervalos usando elementos de P .

Un poset se llama localmente finito si todo intervalo acotado es finito. Por ejemplo, los números enteros son localmente finitos bajo su orden natural. El orden lexicográfico del producto cartesiano ℕ × ℕ no es localmente finito, ya que (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Usando la notación de intervalo, la propiedad " a está cubierta por b " se puede reformular de manera equivalente como [ 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 basado en poset de la gravedad cuántica
• Gráfico de comparabilidad
• Orden parcial completa
• Conjunto dirigido
• Poset calificado
• Álgebra de incidencia
• enrejado
• Poset localmente finito
• Función de moebius en posets
• Colección de conjuntos anidados
• Solicitar politopo
• Grupo 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.
• Semirretículo
• 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
• Árbol (estructura de datos de inclusión de conjuntos)
• Lema de Zorn

Notas

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. 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.
3. Ver Relatividad_general # Viaje_tiempo
4. 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
5. 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.
6. PR Halmos (1974). Teoría de conjuntos ingenua . Saltador. pag. 82 . ISBN 978-1-4757-1645-0.
7. Flaška, V .; Ježek, J .; Kepka, T .; Kortelainen, J. (2007). Clausura transitiva de Binary Relaciones I . Praga: Escuela de Matemáticas - Universidad de Física Charles. pag. 1.Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
8. los órdenes parciales ≤ y ≼ pueden ser diferentes, pero no es necesario
9. Davey y Priestley (2002 , págs. 23-24)
10. Jech, Thomas (2008) [1973]. El axioma de la elección . Publicaciones de Dover . ISBN 978-0-486-46624-8.
11. 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

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