Ordenes Parciales

Una relación R es de orden parcial o simplemente de si cumple las propiedades Reflexiva, Antisimétrica y Transitiva.

Ver definiciones en 2.2.1 Relaciones sobre un Conjunto

Igual que las relaciones de equivalencia, las relaciones de orden también se utilizan mucho en computación; con una relación de orden se establece , como su nombre lo dice, en los elementos del conjunto. Se llama porque no todos los elementos están necesariamente relacionados. Cuando todos los elementos están relacionados se llama .

Una de las relaciones más importantes en matemáticas en la relación en los números reales, que claramente se ve que es un orden total.

Otra relación de orden muy importante es la relación de entre los subconjuntos de un conjunto dado.

La relación no es de orden porque no cumple la propiedad reflexiva.

Observamos que tomamos la cerradura reflexiva de la relación obtenemos la relación , haciendo una analogía con una relación en general, podemos establecer que si una relación antirreflexiva se convierte en relación de orden al tomar su cerradura reflexiva, entonces se llama relación de orden estricto y en cierta forma se comporta como si fuera en lugar de menor o igual.

Por ejemplo si tomamos la relación de subconjunto propio entre conjuntos, o sea que dos conjuntos están relacionados si el primero es subconjunto del segundo pero no son el mismo conjunto. Claramente cumple las propiedades antisimétrica y transitiva y al tomar la cerradura transitiva la convertimos en una relación de orden.

También se define orden total, cuando dos elementos cualesquiera en una relación de orden siempre están relacionados.

Por ejemplo en cualquier conjunto de números reales la relación es de orden total, pues dado un par cualesquiera de números a y b, a está relacionado con b o b está relacionado con a. Sin embargo, en los conjuntos la relación de no es de orden total pues los conjuntos {a,b} y {a,c} no están relacionados.

Ejemplo.

Considere el conjunto A de los divisores positivos de 40 y definios una relación R en A como x está relacionado con y si x divide a y; o lo que es lo mismo si y es un múltiplo de x.

A = {1,2,4,5,8,10,20,40}

Entonces (2,8) está en la relación pues 2 divide a 8, pero
         (4,10) no está pues 4 no divide a 10.

La relación es reflexiva, pues todo número es divible por sí mimo
no es simétrica, pues 2 divide a 8, pero 8 no divide a 2
es antisimétrica, pues si x divide a y, siendo x distinto de y no podemos tener que y divida a x
finalmente, vemos que es transitiva, pues si se cumple que x divide y, y y divide z entonces y/x , z/x son enteros, pero esto implica que z/x es entero, pues el producto de dos enteros es entero, por lo que obtenemos que x divide a z.

Por lo tanto la relación es una relación de orden. En general la relación de divide a es siempre una relación de orden. En la siguiente sección se vará una forma de representar con un diagrama una relación de orden y se varán ejemplos de cómo quedan representadas las relaciones sobre los divisores. En general se pueden clasificar de acuerdo a su descomposición en factores.