Conxunto parcialmente ordenado

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  composto por un conxunto  (chamado conxunto base de ) e unha orde parcial  sobre . 

 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  que é reflexiva, antisimétrica e transitiva. É dicir, para todos  debe satisfacer:

 Reflexividade: , é dicir, cada elemento está relacionado consigo mesmo.
 Antisimetría: se  e  entón .
 Transitividade  se  e  entón  .

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  que é irreflexiva, asimétrica e transitivoa; é dicir, cumpre as seguintes condicións para todos 

 Irreflexividade : , é dicir, ningún elemento está relacionado consigo mesmo (tamén chamada antirreflexivo).
 Asimetría : se  entón non .
 Transitividade : se  e  entón .

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). This source refers to asymmetric relations as "strictly antisymmetric". 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  están estreitamente relacionados. Unha orde parcial non estrita  pódese converter nunha orde parcial estrita eliminando todas as relacións da forma  é dicir, a orde parcial estrita é o conxunto  onde  é a relación de identidade sobre  e  indica a resta de conxuntos. No outro sentido, unha orde parcial estrita < sobre  pódese converter nunha orde parcial non estrita agregando todas as relacións desa forma; é dicir,  é unha orde parcial non estrita. Así, se  é unha orde parcial non estrita, entón a orde parcial estrita correspondente < é o kernel irreflexivo dado por  Pola contra, se < é unha orde parcial estrita, entón a orde parcial non estrita correspondente  é o peche reflexivo dado por: 

 Orde dual 
A dual (ou oposta)  dunha relación de orde parcial  defínese por  sendo a relación inversa de , é dicir  se e só se . A dual dunha orde parcial non estrita é tamén non estrita,  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  e unha relación de orde parcial, normalmente a orde parcial non estrita , podemos estender de forma única a nosa notación para definir catro relacións de orde parcial  e , onde  é unha relación de orde parcial non estrita sobre ,  é a relación de orde parcial estrita asociada en  (o kernel irreflexivo de  ),  é o dual de , 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,  ou , ou, en casos raros, as relacións non estritas e estritas entre si, .

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

 Exemplos 
alt=Division Relationship Up to 4|miniatura| 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:  se  ou (  e  );
 a orde do produto: (a, b) ≤ (c, d) se a ≤ c e b ≤ d;
 o peche reflexivo do produto directo das correspondentes ordes estritas:  se ( e ) ou ( e ).

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),  , definida na unión dos conxuntos subxacentes X e Y pola orde  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  constituído polo conxunto de todos os subconxuntos dun conxunto de tres elementos  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,  está relacionado con  mais non ao revés.
 a e b son comparábeis se  ou . Se non se dá ningunha delas son non comparábeis. Por exemplo,  e  son comparábeis, mentres que  e  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,  é unha cadea.
 Unha anticadea é un subconxunto dun poset no que non hai dous elementos distintos comparábeis. Por exemplo, o conxunto de conxuntos unitarios 
 Dise que un elemento a é estritamente menor que un elemento b, se a ≤ b e  Por exemplo,  é estritamente menor que 
 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  son verdadeiras, e a ≤ c ≤ b é falsa para cada c con  Usando a orde estrita <, a relación a ⋖ b pódese reformular de forma equivalente como " mais non  para calquera c". Por exemplo,  está cuberto por  mais non está cuberto por 

 Extrema 
miniatura| Figura 5 A figura anterior cos elementos maiores e menores eliminados. Neste poset reducido, a fila superior de elementos son todos elementos  e a fila inferior son todos elementos , mais non hai ningún elemento  nen .
Hai varias nocións de elemento "maior" e "menor" nun poset  en particular:

 Elemento maior e menor : Un elemento  é un  se  para todo elemento  Un elemento  é un  se  para todo elemento  Un poset só pode ter un elemento maior e un menor. No noso exemplo, o conxunto  é o elemento maior e  é o elemento menor.
 Elementos maximais e minimais: Un elemento  é maximal se non hai ningún elemento  tal que  Similarmente, un elemento  é minimal se non hai ningún elemento  tal que  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,  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  é un  para a colección de elementos 

miniatura| 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  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  e , unha función  dise que conserva a orde, ou é  monótona, ou isotona, se para todos os   implica .
Se  tamén é un conxunto parcialmente ordenado, e ambas as  e  preservan a orde, a súa composición  tamén conserva a orde.

Unha función  dise que unha reflexión de orde se para todos os   implica 

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

Neste último caso,  é necesariamente inxectiva, posto que  implica  e á súa vez  segundo a antisimetría de  

Se un mergullo de orde  é bixectivo, chámase un isomorfismo de orde, e as ordes parciais  e  son isomorfas. As ordes isomorfas teñen estruturalmente similares Diagramas de Hasse (ver Fig. 7a). 

Pódese demostrar que se existen os mapas  e  que conservan a orde tal que  e  producen a función de identidade en S e T, respectivamente, entón S e T son un isomorfismo de orde.

Por exemplo, un mapa  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  divide , entón cada divisor primo de  tamén é un divisor primo de . Porén, non é nin inxectivo (xa que asigna tanto 12 como 6 a  ) 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  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  ), mais pódese facer un isomorfismo restrinxindo o seu codominio a  A Fig. 7b mostra un subconxunto de  e a súa imaxe isomorfa baixo . 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: 

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

 Subposets 
Un poset  chámase subposet doutro poset  sempre que  é un subconxunto de  e  é un subconxunto de . Esta última condición equivale ao requisito de que para calquera  e  en  (e así tamén en  ), se  entón  .

Se  é un subconxunto de  e a maiores, para todos os  e  en , sempre que  tamén temos , entón chamamos a  o subconxunto de  inducido por , e escribimos .

 Extensión linear 
Unha orde parcial  nun conxunto  chámase extensión doutra orde parcial  en  se temos que para todos os elementos  sempre que  tamén é o caso de que  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  e  hai como máximo un morfismo de  a  Máis explicitamente, sexa  se  (e noutro caso o conxunto baleiro) e  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  é un conxunto parcialmente ordenado ao que tamén se lle deu a estrutura dun espazo topolóxico, entón é habitual asumir que  é un subconxunto pechado do espazo produto topolóxico  Baixo este suposto as relacións de orde parcial compórtanse ben nos límites no sentido de que se  e  e para todos  entón 

 Intervalos 
Un conxunto convexo nun poset P é un subconxunto  de P coa propiedade de que, para calquera x e y en  e calquera z en P, se x ≤ z ≤ y, entón z tamén está en . 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  (é dicir,  e ). 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  ( é dicir,  e ). Un intervalo aberto pode estar baleiro aínda que . Por exemplo, o intervalo aberto (0, 1) nos números enteiros está baleiro xa que non hai ningún número enteiro  tal que .
 Os intervalos semiabertos [a, b) e (a, b] defínense de xeito similar.

Sempre que  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  é convexo, mais non é un intervalo.

Un intervalo  está limitado se existen elementos  tal que . Todo intervalo que se pode representar en notación de intervalos está obviamente limitado, mais a inversa non é verdade. Por exemplo, sexa  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  non é localmente finito, xa que . Usando a notación de intervalo, a propiedade "a está cuberta por b" pódese reformular de forma equivalente como 

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

 Notas 


 Véxase tamén 

 Bibliografía 








 Outros artigos 
 Retícula (teoría da orde).
 Ligazóns externas 
  2.2: Equivalence Relations, and Partial order LibreTexts mathematics.

Categoría:Teoría da orde
Categoría:Wikipedia:Páxinas con traducións non revisadas