Preorde

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 Modelo:Em 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 $\le$. En palabras, cando $a\lesssim b,$ pódese dicir que b Modelo:Em a ou que a Modelo:Em a b, ou que b Modelo:Em 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 Modelo:Em ou Modelo:Em se é reflexiva e transitiva; é dicir, se cumpre:

1. Reflexividade : $a\lesssim a$ para todos os $a\in P,$ e
2. 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\text{ se e só se }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]\le [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).

Modelo:Em: 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⟺B,$, polo que este símbolo $⟺$ 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⟺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 $(S/\sim ,\Leftarrow )$ é, 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 Modelo:Em úsase ás veces para unha orde parcial estrita. É dicir, esta é unha relación binaria $<$ sobre $P$ que satisfai:

1. Irreflexividade ou antireflexividade: Modelo:Em $a<a$ para todos os $a\in P;$ é dicir, $a<a$ é Modelo:Em para todos os $a\in P,$ e
2. Transitividade: se $a<b\text{ e }b<c\text{ daquela }a<c$ 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<b$ se e só se $a\lesssim b$ e non $b\lesssim a$. Usando a relación de equivalencia $\sim$ introducida anteriormente, $a<b$ se e só se $a\lesssim b\text{ e non }a\sim b;$ e así cúmprese o seguinte

$a\lesssim b\text{ se e só se }a<b\text{ ou }a\sim b.$

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 Modelo:Nowrap 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\mathrm{\setminus }R=\stackrel{‾}{R^{\mathsf{\text{T}}}\circ \bar{R}}$ forma unha preorde chamada residual pola esquerda, (onde a barra "$\mathrm{\setminus }$" non significa o "conxunto diferenza"), onde $R^{\mathsf{\text{T}}}$ denota a relación inversa de $R,$ e $\bar{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<x$ e $x<b,$ tamén escrito $a<x<b.$ Un intervalo aberto pode estar baleiro aínda que $a<b.$

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

Véxase tamén

Bibliografía

• Schmidt, Gunther, "Relational Mathematics", Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press, 2011, Modelo:Isbn
• Modelo:Cita libro

Outros artigos

• Conxunto parcialmente ordenado
• Relación de equivalencia
• Preorde total
• Orde total
• Conxunto dirixido

Ligazóns externas

• Preorder MathWorld.

Modelo:Control de autoridades