Conxunto parcialmente ordenado

Fig. 1 O diagrama de Hasse do conxunto de todos os subconxuntos dun conxunto de tres elementos $\{x,y,z\},$ ordenado por inclusión. Os conxuntos ligados por un camiño ascendente, como $\mathrm{\varnothing }$ e $\{x,y\}$, son comparábeis, mentres que. por exemplo, $\{x\}$ e $\{y\}$ non o son.

En matemáticas, especialmente na teoría da orde, unha orde parcial nun conxunto é unha disposición tal que, para certos pares de elementos, un precede ao outro. A palabra parcial úsase para indicar que non todos os pares de elementos han de ser comparábeis; é dicir, pode haber pares para os que ningún elemento precede ao outro. As ordes parciais xeneralizan as ordes totais, nas que todo par é comparábel.

Formalmente, unha orde parcial é unha relación binaria homoxénea que é reflexiva, antisimétrica e transitiva. Un conxunto parcialmente ordenado (poset en inglés) é un par ordenado $P=(X,\le )$ composto por un conxunto $X$ (chamado conxunto base de $P$) e unha orde parcial $\le$ sobre $X$.

Relacións de orde parcial

O termo orde parcial refírese xeralmente ás relacións de orde parcial reflexivas, referidas neste artigo como ordes parciais non estritas. Porén, algúns autores usan o termo para o outro tipo común de relacións de orde parcial, as relacións de orde parcial irreflexivas, tamén chamadas ordes parciais estritas. As ordes parciais estritas e as non estritas pódense poñer nunha correspondencia un a un, polo que para cada orde parcial estrita hai unha única orde parcial non estrita correspondente, e viceversa.

Ordes parciais

Unha orde parcial non estrita, ou débil, ou reflexiva, comunmente coñecida simplemente como orde parcial, é unha relación homoxénea ≤ nun conxunto $P$ que é reflexiva, antisimétrica e transitiva. É dicir, para todos $a,b,c\in P,$ debe satisfacer:

1. Reflexividade: $a\le a$, é dicir, cada elemento está relacionado consigo mesmo.
2. Antisimetría: se $a\le b$ e $b\le a$ entón $a=b$.
3. Transitividade se $a\le b$ e $b\le c$ entón $a\le c$ .

Unha orde parcial non estrita tamén se coñece como preorde antisimétrica.

Ordes parciais estritas

Un orde parcial estrita, ou forte, ou irreflexiva é unha relación homoxénea < nun conxunto $P$ que é irreflexiva, asimétrica e transitivoa; é dicir, cumpre as seguintes condicións para todos $a,b,c\in P:$

1. Irreflexividade : $\mathrm{\neg }(a<a)$, é dicir, ningún elemento está relacionado consigo mesmo (tamén chamada antirreflexivo).
2. Asimetría : se $a<b$ entón non $b<a$.
3. Transitividade : se $a<b$ e $b<c$ entón $a<c$.

A irreflexividade e a transitividade xuntas implican asimetría. A maiores, a asimetría implica irreflexividade. Noutras palabras, unha relación transitiva é asimétrica se e só se é irreflexiva. Lemma 1.1 (iv).</ref> Polo tanto, a definición é a mesma se omite a irreflexividade ou a asimetría (mais non ambas as dúas).

Unha orde parcial estrita tamén se coñece como preorde estrita asimétrica.

Correspondencia entre relacións de orde parcial estrita e non estrita

As ordes parciais estritas e non estritas nun conxunto $P$ están estreitamente relacionados. Unha orde parcial non estrita $\le$ pódese converter nunha orde parcial estrita eliminando todas as relacións da forma $a\le a;$ é dicir, a orde parcial estrita é o conxunto $<:=\le \setminus {\mathrm{\Delta }}_P$ onde ${\mathrm{\Delta }}_P:=\{(p,p):p\in P\}$ é a relación de identidade sobre $P\times P$ e $\setminus$ indica a resta de conxuntos. No outro sentido, unha orde parcial estrita < sobre $P$ pódese converter nunha orde parcial non estrita agregando todas as relacións desa forma; é dicir, $\le :={\mathrm{\Delta }}_P\cup <$ é unha orde parcial non estrita. Así, se $\le$ é unha orde parcial non estrita, entón a orde parcial estrita correspondente < é o kernel irreflexivo dado por $$a<b\text{ if }a\le b\text{ and }a\ne b.$$ Pola contra, se < é unha orde parcial estrita, entón a orde parcial non estrita correspondente $\le$ é o peche reflexivo dado por: $$a\le b\text{ if }a<b\text{ or }a=b.$$

Orde dual

A dual (ou oposta) $R^{\text{op}}$ dunha relación de orde parcial $R$ defínese por $R^{\text{op}}$ sendo a relación inversa de $R$, é dicir $x{R}^{\text{op}}y$ se e só se $yRx$. A dual dunha orde parcial non estrita é tamén non estrita, Modelo:Sfnp e a dual dunha orde parcial estrita tamén estrita. A dual dunha relación dual é a relación orixinal.

Notación

Dado un conxunto $P$ e unha relación de orde parcial, normalmente a orde parcial non estrita $\le$, podemos estender de forma única a nosa notación para definir catro relacións de orde parcial $\le ,$$<,$$\ge ,$ e $>$, onde $\le$ é unha relación de orde parcial non estrita sobre $P$, $<$ é a relación de orde parcial estrita asociada en $P$ (o kernel irreflexivo de $\le$ ), $\ge$ é o dual de $\le$, e $>$ é o dual de $<$. En rigor, o termo conxunto parcialmente ordenado refírese a un conxunto con todas estas relacións definidas adecuadamente, mais na práctica, só hai que considerar unha única relación, $(P,\le )$ ou $(P,<)$, ou, en casos raros, as relacións non estritas e estritas entre si, $(P,\le ,<)$.

Cando se refire a ordes parciais, $\le$ non debe tomarse como complemento de $>$. A relación $>$ é a inversa do kernel irreflexivo de $\le$, que sempre é un subconxunto do complemento de $\le$, mais $>$ é igual ao complemento de $\le$ se, e só se, $\le$ é unha orde total.Modelo:Efn

Exemplos

Fig. 3 Gráfico da divisibilidade dos números do 1 ao 4. Este conxunto está parcialmente ordenado, mais non totalmente ordenado porque hai unha relación de 1 con todos os demais números, mais non hai relación de 2 con 3 nin de 3 con 4.

Exemplos estándar de posets (conxuntos parcialmente ordenados) que aparecen en matemáticas inclúen:

• Os números reais, ou en xeral calquera conxunto totalmente ordenado, ordenados pola relación estándar menor ou igual ≤, é unha orde parcial.
• Sobre os números reais $ℝ$, a relación usual menor que < é unha orde parcial estrita. O mesmo ocorre tamén coa relación usual maior que > en $ℝ$.
• Por definición, toda orde débil estrita é unha orde parcial estrita.
• O conxunto de subconxuntos dun conxunto dado (o seu conxunto de partes) ordenados por inclusión (ver Fig. 1). Do mesmo xeito, o conxunto de secuencias ordenadas por subsecuencia, e o conxunto de cadeas ordenadas por subcadea.
• O conxunto de números naturais equipados coa relación de divisibilidade. (ver Fig. 3 e Fig. 6)
• O conxunto de vértices dun grafo acíclico dirixido ordenado por alcanzabilidade.
• O conxunto de subespazos dun espazo vectorial ordenados por inclusión.

Ordes no produto cartesiano de conxuntos parcialmente ordenados

En orde crecente de forza, tres das posíbeis ordes parciais no produto cartesiano de dous conxuntos parcialmente ordenados son:

• orde lexicográfica: Modelo:Nowrap se Modelo:Nowrap ou ( Modelo:Nowrap e Modelo:Nowrap );
• a orde do produto: (a, b) ≤ (c, d) se a ≤ c e b ≤ d;
• o peche reflexivo do produto directo das correspondentes ordes estritas: Modelo:Nowrap se (Modelo:Nowrap e Modelo:Nowrap) ou (Modelo:Nowrap e Modelo:Nowrap).

As tres poden definirse de xeito similar para o produto cartesiano de máis de dous conxuntos.

Aplicado a espazos vectoriais ordenados sobre o mesmo corpo, o resultado é en cada caso tamén un espazo vectorial ordenado.

Ver tamén ordes sobre o produto cartesiano de conxuntos totalmente ordenados.

Sumas de conxuntos parcialmente ordenados

Outra forma de combinar dous posets (disxuntos) é a suma ordinal (ou suma linear), Modelo:Sfnp Modelo:Nowrap, definida na unión dos conxuntos subxacentes X e Y pola orde Modelo:Nowrap se e só se:

• a, b ∈ X con a ≤ _X b, ou
• a, b ∈ Y con a ≤ _Y b, ou
• a ∈ X e b ∈ Y.

Se dous posets están ben ordenados, entón tamén o está a súa suma ordinal.

Nocións derivadas

Os exemplos usan o poset $(𝒫(\{x,y,z\}),\subseteq )$ constituído polo conxunto de todos os subconxuntos dun conxunto de tres elementos $\{x,y,z\},$ ordenados por inclusión do conxunto (ver Fig. 1).

• a está relacionado con b cando a ≤ b. Isto non implica que b tamén estea relacionado con a, porque a relación non ten por que ser simétrica. Por exemplo, $\{x\}$ está relacionado con $\{x,y\},$ mais non ao revés.
• a e b son comparábeis se Modelo:Nowrap ou Modelo:Nowrap. Se non se dá ningunha delas son non comparábeis. Por exemplo, $\{x\}$ e $\{x,y,z\}$ son comparábeis, mentres que $\{x\}$ e $\{y\}$ non o son.
• Unha orde total ou orde linear é unha orde parcial baixo a cal cada par de elementos é comparábeis, é dicir, a tricotomía vale. Por exemplo, os números naturais coa súa orde estándar.
• Unha cadea é un subconxunto dun poset que é un conxunto totalmente ordenado. Por exemplo, $\{\{\},\{x\},\{x,y,z\}\}$ é unha cadea.
• Unha anticadea é un subconxunto dun poset no que non hai dous elementos distintos comparábeis. Por exemplo, o conxunto de conxuntos unitarios $\{\{x\},\{y\},\{z\}\}.$
• Dise que un elemento a é estritamente menor que un elemento b, se a ≤ b e $a\ne b.$ Por exemplo, $\{x\}$ é estritamente menor que $\{x,y\}.$
• Dise que un elemento a está cuberto por outro elemento b, escrito a ⋖ b (ou a <: b), se a é estritamente menor que b e non cabe un terceiro elemento c entre eles; formalmente: se tanto a ≤ b como $a\ne b$ son verdadeiras, e a ≤ c ≤ b é falsa para cada c con $a\ne c\ne b.$ Usando a orde estrita <, a relación a ⋖ b pódese reformular de forma equivalente como "Modelo:Nowrap mais non Modelo:Nowrap para calquera c". Por exemplo, $\{x\}$ está cuberto por $\{x,z\},$ mais non está cuberto por $\{x,y,z\}.$

Extrema

Figura 5 A figura anterior cos elementos maiores e menores eliminados. Neste poset reducido, a fila superior de elementos son todos elementos Modelo:Em e a fila inferior son todos elementos Modelo:Em, mais non hai ningún elemento Modelo:Em nen Modelo:Em.

Hai varias nocións de elemento "maior" e "menor" nun poset $P,$ en particular:

• Elemento maior e menor : Un elemento $g\in P$ é un Modelo:Em se $a\le g$ para todo elemento $a\in P.$ Un elemento $m\in P$ é un Modelo:Em se $m\le a$ para todo elemento $a\in P.$ Un poset só pode ter un elemento maior e un menor. No noso exemplo, o conxunto $\{x,y,z\}$ é o elemento maior e $\{\}$ é o elemento menor.
• Elementos maximais e minimais: Un elemento $g\in P$ é maximal se non hai ningún elemento $a\in P$ tal que $a>g.$ Similarmente, un elemento $m\in P$ é minimal se non hai ningún elemento $a\in P$ tal que $a<m.$ Se un poset ten un elemento maior entón debe ser o único elemento maximal, mais sen elemento maior podería haber varios elementos maximais, e de forma similar para os elementos minimais. No noso examplo, $\{x,y,z\}$ e $\{\}$ son o elemento único maximal e minimal respectivamente. Se os eliminamos, daquela fican 3 elementos maximais e 3 elementos minimais (ver Fig. 5).
• Elemento maiorante e minorante: Para un subconxunto A de P, un elemento x en P é un elemento maiorante de A se a ≤ x, para todo elemento a en A. En particular, x non necesita estar en A para ser elemento maiorante de A. Similarmente, un elemento x en P é un elemento minorante de A se a ≥ x, para todo elemento a en A. Un elemento maior de P é un elemento maiorante de P, e un elemento menor é un elemento minorante de P. No noso examplo, o conxunto $\{x,y\}$ é un Modelo:Em para a colección de elementos $\{\{x\},\{y\}\}.$

Fig. 6 Números enteiros non negativos, ordenados por divisibilidade

Como outro exemplo, considere os enteiros positivos, ordenados por divisibilidade: 1 é un elemento mínimo, xa que divide a todos os demais elementos; por outra banda este poset non ten un elemento maior. Este conxunto parcialmente ordenado nin sequera ten elementos máximais, xa que calquera g divide por exemplo a 2g, que é distinto del, polo que g non é máximal. Se se exclúe o número 1, mantendo a divisibilidade como orde nos elementos maiores que 1, entón o poset resultante non ten un elemento mínimal, pero calquera número primo é un elemento mínimal para el. Neste poset, 60 é un límite superior (aínda que non o mínimo deles ou supremo) do subconxunto $\{2,3,5,10\},$ que non ten límite inferior (xa que 1 non está no poset); por outra banda 2 é un límite inferior do subconxunto de potencias de 2, que non ten ningún límite superior. Se se inclúe o número 0, este será o elemento máis grande, xa que este é un múltiplo de todo número enteiro (ver Fig. 6).

Mapas entre conxuntos parcialmente ordenados

Dado dous conxuntos parcialmente ordenados Modelo:Math e Modelo:Math, unha función $f:S\to T$ dise que conserva a orde, ou é monótona, ou isotona, se para todos os $x,y\in S,$ $x\le y$ implica Modelo:Math. Se Modelo:Math tamén é un conxunto parcialmente ordenado, e ambas as $f:S\to T$ e $g:T\to U$ preservan a orde, a súa composición $g\circ f:S\to U$ tamén conserva a orde.

Unha función $f:S\to T$ dise que unha reflexión de orde se para todos os $x,y\in S,$ Modelo:Math implica $x\le y.$

Se Modelo:Mvar conserva a orde e tamén reflicte a orde, entón chámase un mergullo de ordes de Modelo:Math en Modelo:Math.

Neste último caso, Modelo:Mvar é necesariamente inxectiva, posto que $f(x)=f(y)$ implica $x\le y\text{ e }y\le x$ e á súa vez $x=y$ segundo a antisimetría de $\le .$

Se un mergullo de orde $f:S\to T$ é bixectivo, chámase un isomorfismo de orde, e as ordes parciais Modelo:Math e Modelo:Math son isomorfas. As ordes isomorfas teñen estruturalmente similares Diagramas de Hasse (ver Fig. 7a).

Pódese demostrar que se existen os mapas $f:S\to T$ e $g:T\to U$ que conservan a orde tal que $g\circ f$ e $f\circ g$ producen a función de identidade en S e T, respectivamente, entón S e T son un isomorfismo de orde.Modelo:Sfnp

Por exemplo, un mapa $f:\mathbb{N}\to \mathbb{P}(\mathbb{N})$ Desde o conxunto de números naturais (ordenados por divisibilidade) ata o conxunto de partes de números naturais (ordenados por inclusión de conxuntos) pódese definir levando cada número ao conxunto dos seus divisores primos. Conserva a orde: se Modelo:Mvar divide Modelo:Mvar, entón cada divisor primo de Modelo:Mvar tamén é un divisor primo de Modelo:Mvar. Porén, non é nin inxectivo (xa que asigna tanto 12 como 6 a $\{2,3\}$ ) nin reflicte a orde (xa que 12 non divide 6).

Polo contrario se definimos o mapa que asigna a cada número o conxunto dos seus divisores con potencia de primo, daquela temos un mapa $g:\mathbb{N}\to \mathbb{P}(\mathbb{N})$ que conserva a orde e máis reflicte a orde e, polo tanto e un mergullo de orde. Non é un isomorfismo de orde (xa que, por exemplo, non asigna ningún número ao conxunto $\{4\}$ ), mais pódese facer un isomorfismo restrinxindo o seu codominio a $g(\mathbb{N}).$ A Fig. 7b mostra un subconxunto de $\mathbb{N}$ e a súa imaxe isomorfa baixo Modelo:Mvar. A construción de tal isomorfismo de orde nun conxunto de partes pódese xeneralizar a unha ampla clase de ordes parciais, chamadas retículas distributivas; ver o teorema de representación de Birkhoff .

Número de ordes parciais

A secuencia A001035 na OEIS dá o número de ordes parciais nun conxunto de n elementos etiquetados:Modelo:Número de relacións

O número de ordes parciais estritas é o mesmo que o de ordes parciais.

Se a conta se fai só ata isomorfismo, obtemos a secuencia 1, 1, 2, 5, 16, 63, 318,... Modelo:OEIS .

Subposets

Un poset $P^{*}=(X^{*},{\le }^{*})$ chámase subposet doutro poset $P=(X,\le )$ sempre que $X^{*}$ é un subconxunto de $X$ e ${\le }^{*}$ é un subconxunto de $\le$. Esta última condición equivale ao requisito de que para calquera $x$ e $y$ en $X^{*}$ (e así tamén en $X$ ), se $x{\le }^{*}y$ entón $x\le y$ .

Se $P^{*}$ é un subconxunto de $P$ e a maiores, para todos os $x$ e $y$ en $X^{*}$, sempre que $x\le y$ tamén temos $x{\le }^{*}y$, entón chamamos a $P^{*}$ o subconxunto de $P$ inducido por $X^{*}$, e escribimos $P^{*}=P[X^{*}]$.

Extensión linear

Unha orde parcial ${\le }^{*}$ nun conxunto $X$ chámase extensión doutra orde parcial $\le$ en $X$ se temos que para todos os elementos $x,y\in X,$ sempre que $x\le y,$ tamén é o caso de que $x{\le }^{*}y.$ Unha extensión linear é unha extensión que tamén é unha orde linear (é dicir, total). Como exemplo clásico, a orde lexicográfica dos conxuntos totalmente ordenados é unha extensión linear da súa orde de produtos. Toda orde parcial pódese estender a unha orde total (principio de extensión da orde).

En informática, os algoritmos para atopar extensións lineares de ordes parciais (representados como as ordes de atinxibilidade dos grafos acíclicos dirixidos) chámanse ordenación topolóxica.

Na teoría de categorías

Cada poset (e cada conxunto preordenado) pode considerarse como unha categoría onde, para os obxectos $x$ e $y,$ hai como máximo un morfismo de $x$ a $y.$ Máis explicitamente, sexa Modelo:Nowrap se Modelo:Nowrap (e noutro caso o conxunto baleiro) e $(y,z)\circ (x,y)=(x,z).$ Esas categorías ás veces chámanse categoría posetal.

Os posets son equivalentes entre si, se e só se son isomorfos. Nun poset, o elemento máis pequeno, se existe, é un obxecto inicial, e o elemento máis grande, se existe, é un obxecto terminal. A maiores, cada conxunto preordenado é equivalente a un poset. Finalmente, cada subcategoría dun poset é un isomorfismo pechado.

Ordes parciais en espazos topolóxicos

Se $P$ é un conxunto parcialmente ordenado ao que tamén se lle deu a estrutura dun espazo topolóxico, entón é habitual asumir que $\{(a,b):a\le b\}$ é un subconxunto pechado do espazo produto topolóxico $P\times P.$ Baixo este suposto as relacións de orde parcial compórtanse ben nos límites no sentido de que se $\underset{i\to \mathrm{\infty }}{\lim }{a}_i=a,$ e $\underset{i\to \mathrm{\infty }}{\lim }{b}_i=b,$ e para todos $i,$$a_i\le b_i,$ entón $a\le b.$

Intervalos

Un conxunto convexo nun poset P é un subconxunto Modelo:Mvar de P coa propiedade de que, para calquera x e y en Modelo:Mvar e calquera z en P, se x ≤ z ≤ y, entón z tamén está en Modelo:Mvar. Esta definición xeneraliza a definición de intervalos de números reais. Cando é posíbel a confusión cos conxuntos convexos de xeometría, úsase orde convexo en lugar de "convexo".

Unha subretícula convexa dunha retícula L é unha subretícula de L que tamén é un conxunto convexo de L. Toda subretícula convexa non baleira pode representarse de forma única como a intersección dun filtro e un ideal de L.

Un intervalo nun poset P é un subconxunto que se pode definir coa notación de intervalo:

• Para a ≤ b, o intervalo pechado [a, b] é o conxunto de elementos x que satisfán Modelo:Nowrap (é dicir, Modelo:Nowrap e Modelo:Nowrap). Contén polo menos os elementos a e b .
• Usando a correspondente relación estrita "<", o intervalo aberto (a, b) é o conxunto de elementos x que satisfán Modelo:Nowrap ( é dicir, Modelo:Nowrap e Modelo:Nowrap). Un intervalo aberto pode estar baleiro aínda que Modelo:Nowrap. Por exemplo, o intervalo aberto (0, 1) nos números enteiros está baleiro xa que non hai ningún número enteiro Modelo:Mvar tal que Modelo:Math.
• Os intervalos semiabertos [a, b) e (a, b] defínense de xeito similar.

Sempre que Modelo:Nowrap non se cumpre, todos estes intervalos están baleiros. Todo intervalo é un conxunto convexo, mais a inversa non se cumpre; por exemplo, no poset dos divisores de 120, ordenados pola divisibilidade (ver Fig. 7b), o conxunto Modelo:Mset é convexo, mais non é un intervalo.

Un intervalo Modelo:Mvar está limitado se existen elementos $a,b\in P$ tal que Modelo:Math. Todo intervalo que se pode representar en notación de intervalos está obviamente limitado, mais a inversa non é verdade. Por exemplo, sexa Modelo:Math como subconxunto dos números reais. O subconxunto (1, 2) é un intervalo limitado, mais non ten ínfimo nin supremo en P, polo que non se pode escribir en notación de intervalos usando elementos de P.

Un poset chámase localmente finito se cada intervalo limitado é finito. Por exemplo, os enteiros son localmente finitos baixo a súa orde natural. A orde lexicográfica sobre o produto cartesiano $\mathbb{N}\times \mathbb{N}$ non é localmente finito, xa que Modelo:Math. Usando a notación de intervalo, a propiedade "a está cuberta por b" pódese reformular de forma equivalente como $[a,b]=\{a,b\}.$

Este concepto de intervalo nunha orde parcial non debe confundirse coa clase particular de ordes parciais coñecidas como ordes de intervalo.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita publicación periódica
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita publicación periódica

Outros artigos

• Retícula (teoría da orde).

Ligazóns externas

• 2.2: Equivalence Relations, and Partial order LibreTexts mathematics.