Preorde

[miniatura| [Diagrama de Hasse da preorde *x R y* definida por *x*//4≤*y* //4 sobre os números naturais. As clases de equivalencia (conxuntos de elementos tal que *x R y* e *y R x* ) móstranse xuntos como un único nodo. A relación nas clases de equivalencia é unha orde parcial.]]

En matemáticas, especialmente na teoría da orde, unha **preorde** ou **cuasiorde** é unha relación binaria que é reflexiva e transitiva. O nome de  pretende suxerir que son ordes *case* parciais, mais non de todo, xa que non son necesariamente antisimétricas.

Un exemplo natural de preorde é a relación de división "x divide y" entre números enteiros, polinomios ou elementos dun anel conmutativo. Por exemplo, a relación de división é reflexiva pois cada número enteiro divídese a si mesmo. Mais a relación de división non é antisimétrica, porque 1 divide -1 e -1 divide 1. É a esta preorde  á que "máximo" e "mínimo" se refiren nas frases "máximo común divisor" e "mínimo común múltiplo" (agás que, para os enteiros, o máximo común divisor tamén é o máximo para a orde natural dos enteiros).

As preordes están estreitamente relacionadas coas relacións de equivalencia e as ordes parciais (non estritas). Ambas as dúas son casos especiais dunha preorde: unha preorde antisimétrica é unha orde parcial e unha simétrica unha relación de equivalencia. A maiores, unha preorde nun conxunto X pódese definir equivalentemente como unha relación de equivalencia sobre X, xunto cunha orde parcial sobre o conxunto da clase de equivalencia. Do mesmo xeito que as ordes parciais e as relacións de equivalencia, as preordes (nun conxunto non baleiro) nunca son asimétricas.

Como relación binaria, unha preorde pódese denotar como \,\lesssim\, ou \,\leq\,. En palabras, cando a \lesssim b, pódese dicir que *b*  *a* ou que *a*  *a b*, ou que *b*  *a*. En ocasións, tamén se usa a notación ← ou →.

## Definición 
Sexa \,\lesssim\, unha relación binaria nun conxunto P, polo que, por definición, \,\lesssim\, é algún subconxunto de P \times P. Entón \,\lesssim\, chámase '*** ou **** se é reflexiva e transitiva; é dicir, se cumpre:

# Reflexividade : a \lesssim a para todos os a \in P, e
# Transitividade : se a \lesssim b \text{ e } b \lesssim c \text{ then } a \lesssim c para tódolos a, b, c \in P.

Un conxunto que está equipado cunha preorde chámase **conxunto preordenado** (ou **proset*' en inglés).

## Preordes como ordes parciais en particións 
Dada unha preorde \,\lesssim\, en S pódese definir unha relación de equivalencia \,\sim\, en S tal que a \sim b \quad \text{ se e só se } \quad a \lesssim b \; \text{ e } \; b \lesssim a.A relación resultante \,\sim\, é reflexiva posto que a preorde \,\lesssim\, é reflexiva; transitiva aplicando a transitividade de \,\lesssim\, dúas veces; e simétrica por definición.

Usando esta relación, é posíbel construír unha orde parcial sobre o conxunto cociente da equivalencia, S / \sim, que é o conxunto de todas as clases de equivalencia de \,\sim. Se a preorde está indicada por R^{+=}, entón S / \sim é o conxunto de R-ciclo clases de equivalencia: x \in [y] se e só se x = y ou x está nun R-ciclo con y. En todo caso, en S / \sim é posíbel definir [x] \leq [y] se e só se x \lesssim y. Que este está ben definido, é dicir, que a súa condición definitoria non depende dos representantes [x] e [y] que son escollidos, despréndese da definición de \,\sim.\, Verifícase facilmente que isto dá un conxunto parcialmente ordenado.

E viceversa, desde calquera orde parcial nunha partición dun conxunto S, é posíbel construír unha preorde en S. Hai unha correspondencia un a un entre as preordes e os pares (partición, orde parcial).

: Sexa S unha teoría lóxica formal, que é un conxunto de  proposicións con certas propiedades (os detalles pódense atopar no artigo sobre o tema). Por exemplo, S podería ser unha Teoría de primeira orde (como a  Teoría de conxuntos de Zermelo–Fraenkel) ou unha teoría máis sinxela como a teoría de orde cero. Unha das moitas propiedades de S é que está pechada baixo conectivas lóxicas, polo que, por exemplo, se unha proposición A \in S implica loxicamente algunha proposición B , que se escribirá como A \Rightarrow B e tamén como B \Leftarrow A, entón necesariamente B \in S (por *modus ponens*).
A relación \,\Leftarrow\, é unha preorde en S porque A \Leftarrow A sempre se cumpre e sempre que A \Leftarrow B  e B \Leftarrow C mantéñense, entón tamén o fai A \Leftarrow C.
Alén diso, para calquera A, B \in S, A \sim B se e só se A \Leftarrow B \text{ e } B \Leftarrow A; é dicir, dúas proposcións son equivalentes con respecto a \,\Leftarrow\, se e só se son loxicamente equivalentes. Esta relación de equivalencia particular A \sim B denótase habitualmente co seu propio símbolo especial A \iff B,, polo que este símbolo  \iff  pódese usar en lugar de \sim. A clase de equivalencia dunha proposición A, denotada por [A], consta de todas as proposicións B \in S que son loxicamente equivalentes a A (é dicir, todas B \in S tal que A \iff B ).
A orde parcial en S/\sim inducida por \,\Leftarrow,\, que tamén se denotará co mesmo símbolo \,\Leftarrow,\,  caracterízase por [A] \Leftarrow [B] se e só se A \Leftarrow B, onde a condición do lado dereito é independente da elección de representantes A \in [A] e B \in [B] das clases de equivalencia.
Todo o que se dixo de \,\Leftarrow\, ata agora tamén se pode dicir da súa relación inversa \,\Rightarrow.\,
O conxunto preordenado (S, \Leftarrow) é un conxunto dirixido porque se A, B \in S e se C := A \wedge B denota a proposición formada pola conxunción lóxica  \wedge,  entón A \Leftarrow C e B \Leftarrow C onde C \in S. O conxunto parcialmente ordenado \left(S / \sim, \Leftarrow\right) é, en consecuencia, tamén un conxunto dirixido.
Consulte Álxebra Lindenbaum–Tarski para obter un exemplo relacionado.

## Relación con ordes parciais estritas 
Se a reflexividade substitúese pola irreflexividade (mentres se mantén a transitividade), obtemos a definición dunha orde parcial estrita sobre P. Por este motivo, o termo ''''* úsase ás veces para unha orde parcial estrita. É dicir, esta é unha relación binaria \, sobre P que satisfai:

# Irreflexividade ou antireflexividade:  a  para todos os a \in P; é dicir, \,a  é  para todos os a \in P, e
# Transitividade: se a  para todos os a, b, c \in P.

### Orde parcial estrita inducida por unha orde previa 
Calquera preorde \,\lesssim\, dá lugar a unha orde parcial estrita definida por a  se e só se a \lesssim b e non b \lesssim a.
Usando a relación de equivalencia \,\sim\, introducida anteriormente, a  se e só se a \lesssim b \text{ e non } a \sim b;
e así cúmprese o seguinte
:a \lesssim b \quad \text{ se e só se } \quad a 

### Preordes inducidas por unha orde parcial estrita 
Usando a construción anterior, varios preordes non estritas poden producir a mesma preorde  estrita \, así que sen máis información sobre como \, foi construída (tal coñecemento da relación de equivalencia \,\sim\, por exemplo), quizais non sexa posíbel reconstruír a preorde orixinal non estrita a partir de \, 

## Exemplos 
### Teoría de grafos 
* A relación de accesibilidade en calquera grafo dirixido (que pode conter ciclos) dá lugar a unha preorde, onde x \lesssim y na preorde se e só se existe un camiño de *x* a *y* no grafo dirixido. Viceversa, cada preorde é a relación de accesibilidade dun grafo dirixido (por exemplo, o grafo que ten unha aresta de *x* a *y* para cada par  con x \lesssim y). Non obstante, moitos grafos diferentes poden ter a mesma orde de accesibilidade entre si. Do mesmo xeito, a accesibilidade dos grafos acíclicos dirixidos, grafos dirixidos sen ciclos, dá lugar a conxuntos parcialmente ordenados (preordes que satisfán unha propiedade de antisimetría adicional).
* A relación grafo menor tamén é unha orde previa.

### Teoría de categorías 
* Unha categoría con como máximo un morfismo desde calquera obxecto *x* a calquera outro obxecto *y* é unha preorde. Esas categorías chámanse delgadas. Aquí os obxectos corresponden aos elementos de P, e hai un morfismo para os obxectos que están relacionados, cero en caso contrario. Neste sentido, as categorías "xeneralizan" as preordes permitindo máis dunha relación entre obxectos: cada morfismo é unha relación de preorde distinta.
* Alternativamente, un conxunto preordenado pódese entender como unha categoría enriquecida, enriquecida sobre a categoría 2 = (0 \to 1).

### Outros 
* Todo espazo topolóxico finito dá lugar a unha preorde nos seus puntos mediante a definición x \lesssim y se e só se *x* pertence a todas as veciñanzas de *y*. Toda preorde finita pódese formar deste xeito como a preorde de especialización dun espazo topolóxico. É dicir, hai unha correspondencia un a un entre topoloxías finitas e preordes finitas. No entanto, a relación entre espazos topolóxicos infinitos e as súas preordes de especialización non é un a un.

* Unha rede é unha preorde dirixida, é dicir, cada par de elementos ten un límite superior. A definición de converxencia a través de redes é importante na topoloxía, onde as preordes  non se poden substituír por conxuntos parcialmente ordenados sen perder características importantes.

* A relación definida por x \lesssim y se f(x) \lesssim f(y), onde *f* é unha función nalgunha preorde.
* A relación definida por x \lesssim y se existe algunha inxección de *x* a *y*. A inxección pode substituírse por sobrexección ou por calquera tipo de función de conservación da estrutura, como un homomorfismo de anel ou unha permutación.
* A relación de mergullo para ordes totais contábeis.

Exemplo de preorde total:

* Preferencia, segundo modelos comúns.

## Construcións 
Toda relación binaria R nun conxunto S pódese ampliar a unha preorde en S tomando o peche transitivo e o peche reflexivo, R^{+=}. O peche transitivo indica a conexión do camiño R : x R^+ y se e só se hai un R-camiño dende x a y.

**Preorde residual pola esquerda inducida por unha relación binaria**

Dada unha relación binaria R, a composición complementada R \backslash R = \overline{R^\textsf{T} \circ \overline{R}} forma unha preorde chamada residual pola  esquerda, (onde a barra "\backslash" non significa o "conxunto diferenza"), onde R^\textsf{T} denota a relación inversa de R, e \overline{R} denota a relación complementaria de R, mentres \circ denota composición de relacións.

## Definicións relacionadas 
Se unha preorde tamén é antisimétrica, é dicir, a \lesssim b e b \lesssim a implica a = b, entón é unha orde parcial.

Por outra banda, se é simétrica, é dicir, se a \lesssim b implica b \lesssim a, entón é unha relación de equivalencia.

Unha preorde é total se a \lesssim b ou b \lesssim a para todos os a, b \in P.

Unha clase reservada é unha clase equipada cunha preorde. Todo conxunto é unha clase e, polo tanto, todo conxunto preordenado é unha clase preordenada.

## Intervalo 
Para a \lesssim b, o intervalo [a, b] é o conxunto de puntos *x* que satisfán a \lesssim x e x \lesssim b, tamén escrito a \lesssim x \lesssim b. Contén polo menos os puntos *a* e *b*. Pódese optar por estender a definición a todos os pares (a, b). Os intervalos adicionais están todos baleiros.

Usando a relación estrita correspondente "", tamén se pode definir o intervalo (a, b) como o conxunto de puntos *x'' que satisfán a  e x  tamén escrito a  Un intervalo aberto pode estar baleiro aínda que a 

Tamén [a, b) e (a, b] poden definirse de xeito similar.

## Notas 
## Véxase tamén 
### Bibliografía 
* Schmidt, Gunther, "Relational Mathematics", Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press, 2011, 
* 
### Outros artigos 
* Conxunto parcialmente ordenado
* Relación de equivalencia
* Preorde total
* Orde total 
* Conxunto dirixido

### Ligazóns externas 
* Preorder MathWorld.