dereita|miniatura| Fig. 1 O diagrama de Hasse do conxunto de todos os subconxuntos dun conxunto de tres elementos ordenado por inclusión. Os conxuntos ligados por un camiño ascendente, como e , son comparábeis, mentres que. por exemplo, e 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 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.