Conxunto parcialmente ordenado

[dereita|miniatura| **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 \emptyset 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,\leq) composto por un conxunto X (chamado *conxunto base* de P) e unha orde parcial \leq 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**, 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:

# Reflexividade: a \leq a, é dicir, cada elemento está relacionado consigo mesmo.
# Antisimetría: se a \leq b e b \leq a entón a = b.
# Transitividade  se a \leq b  e b \leq c entón a \leq 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 P que é irreflexiva, asimétrica e transitivoa; é dicir, cumpre as seguintes condicións para todos a, b, c \in P:

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

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). 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 \leq pódese converter nunha orde parcial estrita eliminando todas as relacións da forma a \leq a; é dicir, a orde parcial estrita é o conxunto  onde \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 P pódese converter nunha orde parcial non estrita agregando todas as relacións desa forma; é dicir, \leq\; := \;\Delta_P\; \cup \; é unha orde parcial non estrita. Así, se \leq é unha orde parcial non estrita, entón a orde parcial estrita correspondente a  Pola contra, se \leq é o peche reflexivo dado por: a \leq b \text{ if } a 

### 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 y R x. 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 P e unha relación de orde parcial, normalmente a orde parcial non estrita \leq, podemos estender de forma única a nosa notación para definir catro relacións de orde parcial \leq,\geq, e >, onde \leq é unha relación de orde parcial non estrita sobre P,   é a relación de orde parcial estrita asociada en P (o kernel irreflexivo de \leq ), \geq é o dual de \leq, 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,\leq) ou (P,, ou, en casos raros, as relacións non estritas e estritas entre si, (P,\leq,.

Cando se refire a ordes parciais, \leq non debe tomarse como complemento de  > . A relación  >  é a inversa do kernel irreflexivo de \leq, que sempre é un subconxunto do complemento de \leq, mais  >  é igual ao complemento de \leq se, e só se, \leq é 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 \mathbb{R}, a relación usual menor que  en \R.
* 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.&nbsp;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.&nbsp;3 e Fig.&nbsp;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:&nbsp; se  ou (  e  );
* a orde do produto:&nbsp;(*a*, *b*) ≤ (*c*, *d*) se *a* ≤ *c* e *b* ≤ *d*;
* o peche reflexivo do produto directo das correspondentes ordes estritas:&nbsp; 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 (\mathcal{P}(\{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.&nbsp;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  ou . 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 \neq 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* a \neq b son verdadeiras, e *a* ≤ *c* ≤ *b* é falsa para cada *c* con a \neq c \neq b. Usando a orde estrita \{x\} está cuberto por \{x, z\}, mais non está cuberto por \{x, y, z\}.

### 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 P, en particular:

* Elemento maior e menor : Un elemento g \in P é un  se a \leq g para todo elemento a \in P. Un elemento m \in P é un  se m \leq 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  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  para a colección de elementos \{\{x\}, \{y\}\}.

[miniatura| **Fig. 6** [Número natural|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 2*g*, 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.&nbsp;6).

## Mapas entre conxuntos parcialmente ordenados 
Dado dous conxuntos parcialmente ordenados  e , 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 \leq y implica .
Se  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,  implica x \leq y.

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 f(x) = f(y) implica x \leq y \text{ e } y \leq x e á súa vez x = y segundo a antisimetría de \leq. 

Se un mergullo de orde f : S \to T é 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.&nbsp;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.

Por exemplo, un mapa f : \N \to \mathbb{P}(\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  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 \{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 : \N \to \mathbb{P}(\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(\N). A Fig.&nbsp;7b mostra un subconxunto de \N 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 P^*=(X^*, \leq^*) chámase **subposet** doutro poset P=(X, \leq) sempre que X^* é un subconxunto de X e \leq^* é un subconxunto de \leq. Esta última condición equivale ao requisito de que para calquera x e y en X^* (e así tamén en X ), se x \leq^* y entón x \leq y .

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

## Extensión linear 
Unha orde parcial \leq^* nun conxunto X chámase **extensión** doutra orde parcial \leq en X se temos que para todos os elementos x, y \in X, sempre que x \leq y, tamén é o caso de que x \leq^* 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  se  (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 \lim_{i \to \infty} a_i = a, e \lim_{i \to \infty} b_i = b, e para todos i,a_i \leq b_i, entón a \leq b.

## 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 "a, b \in P 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&nbsp;*P*, polo que non se pode escribir en notación de intervalos usando elementos de&nbsp;*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 \N \times \N 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 [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.

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