Conjunto preordenado

Considere algún conjunto P y una relación binaria R en P. Entonces R es un preorden, o un cuasiorden, si es reflexiva y transitiva, es decir, para todo a, b y c en P, tenemos que:

${\displaystyle R=\{(a,b)\in \;P^{2}:\quad R(a,b)\}}$

Es un conjunto preordenado, si cumple:

1.- La relación R es reflexiva si todo elemento a de P está relacionado consigo mismo.

${\displaystyle \forall a\in P:\;(a,a)\in R}$

2.- La relación R es transitiva si un elemento a está relacionado con otro b, y este b con otro c, entonces el elemento a esta también relacionado con el c.

${\displaystyle \forall a,b,c\in P:\;{\Big (}(a,b)\in R\quad \land \quad (b,c)\in R{\Big )}\longrightarrow \quad (a,c)\in R}$

Entonces en una relación binaria de preorden.

Si un preorden cumple también la propiedad simétrica para todo a, b de P, si a R b entonces b R a, (P, R) es una relación de equivalencia

Si un preorden cumple también la propiedad antisimétrica, es decir, a R b y b R a implica a = b, entonces (P, R) es un orden parcial.

Es importante diferenciar las siguientes tres propiedades:

• La relación R es simétrica si un elemento a está relacionado con otro b, entonces el b también está relacionado con el a.

${\displaystyle \forall a,b\in P:\;(a,b)\in R\longrightarrow \quad (b,a)\in R}$

Para todo a, b de P, si se cumple que a esta relacionada con b entonces b esta relacionada con a.

• La relación R es antisimétrica si un elemento a está relacionado con otro b, entonces el b no está relacionado con el a.

${\displaystyle \forall a,b\in P:\;(a,b)\in R\longrightarrow \quad (b,a)\notin R}$

Para todo a, b de P, si se cumple que a esta relacionada con b entonces b no esta relacionada con a.

• La relación R es asimétrica si no cumple ninguna de las dos condiciones anteriores.

Un grafo dirigido, que tiene al menos un ciclo, es preordenado dado que cumple la propiedad reflexiva y transitiva, y no es ni simétrico ni antisimétrico.

Dado un preorden ${\displaystyle \lesssim }$ en un conjunto ${\displaystyle A}$, se puede definir la relación de equivalencia ${\displaystyle x\sim y\iff x\lesssim y\land y\lesssim x}$ para ${\displaystyle x,y\in A}$. El preorden genera una relación de orden en el conjunto cociente dada por ${\displaystyle [x]\leq [y]\iff x\lesssim y}$ para ${\displaystyle x,y\in A}$, que está bien definida (${\displaystyle [x]}$ denota la clase de ${\displaystyle x}$ para ${\displaystyle \sim }$).

También se puede hacer el proceso inverso: dada una partición de ${\displaystyle A}$, un orden parcial en el ella determina un preorden en ${\displaystyle A}$.