Propiedades y Representación de Relaciones Binarias en Conjuntos

Relaciones

Sea X un conjunto y R ⊆ X × X una relación en X.

• Se dice que R es reflexiva si (x, x) ∈ R para todo x ∈ X.
• Se dice que R es simétrica si siempre que (x, y) ∈ R se verifica que (y, x) ∈ R.
• Se dice que R es antisimétrica si cuando (x, y) ∈ R y (y, x) ∈ R, entonces x = y.
• Se dice que R es transitiva si siempre que (x, y) ∈ R y (y, z) ∈ R, se tiene que (x, z) ∈ R.

Sea X un conjunto y R ⊆ X × X una relación en X.

• Se dice que R es una relación de equivalencia si R verifica las propiedades reflexiva, simétrica y transitiva.
• Se dice que R es una relación de orden si R verifica las propiedades reflexiva, antisimétrica y transitiva.

Representación de Relaciones Binarias

Puesto que una relación binaria en un conjunto X es un subconjunto R ⊆ X × X, esta se puede visualizar como los puntos del plano cartesiano cuyos ejes son el conjunto X. Es decir, mediante una tabla o gráfica.

• La propiedad reflexiva implica que el conjunto diagonal Δ = { (x, x) | x ∈ X } es un subconjunto de la relación (Δ ⊆ R).
• La propiedad simétrica se refleja en la gráfica haciéndola simétrica respecto de la diagonal Δ.
• La propiedad antisimétrica se ve comprobando que no existen puntos pertenecientes a la relación que sean simétricos respecto de dicha diagonal (excepto los de la propia diagonal).
• Para observar si R disfruta de la propiedad transitiva, a menudo es útil hacer uso de la representación matricial de las relaciones binarias.

Matriz de Adyacencias

Sea X = { x1, ..., xn } un conjunto finito y R ⊆ X × X una relación en X. Se define la matriz de adyacencias asociada a la relación R como la matriz M = (mij), donde mij = 1 si xi R xj (es decir, (xi, xj) ∈ R) y mij = 0 en caso contrario.

• Si la relación R verifica la propiedad reflexiva, la matriz M de adyacencias tendrá en la diagonal principal todos unos.
• Si es una relación simétrica, la matriz M será simétrica (M = MT).
• Si R es una relación antisimétrica, la matriz de adyacencias cumple que si mij = 1 con i ≠ j, entonces mji = 0.
• Para la propiedad transitiva se verifica la siguiente proposición: Sea X = { x1, ..., xn } un conjunto finito, R ⊆ X × X una relación en X, M la matriz de adyacencias de R y M2 = M · M = (nij) la matriz producto de M por sí misma. Entonces R es transitiva si y solo si para todo i, j, siempre que nij > 0 se cumple que mij = 1. (Alternativamente, si mij = 0, entonces nij debe ser 0, o visto de otra forma, si existe un camino de longitud 2 de xi a xj, debe existir un camino de longitud 1).

Relaciones de Equivalencia

Sea X un conjunto y R ⊆ X × X una relación de equivalencia en X. Sea x ∈ X, se define la clase de equivalencia de x por la relación R al conjunto:

[x] = { y ∈ X | y R x }

Propiedades

Sea X un conjunto y R ⊆ X × X una relación de equivalencia en X.

1. Para todo x ∈ X, la clase de equivalencia [x] es distinta del conjunto vacío ([x] ≠ ∅), ya que por reflexividad, x ∈ [x].
2. Si x R y, entonces [x] = [y].
3. Si [x] ≠ [y], entonces [x] ∩ [y] = ∅. (Dos clases de equivalencia son o iguales o disjuntas).
4. El conjunto X es la unión disjunta de sus clases de equivalencia: X = ⋃x∈X [x], donde la unión es sobre un conjunto de representantes de las clases distintas.

Sea X un conjunto y R ⊆ X × X una relación de equivalencia en X. Se define el conjunto cociente X/R por la relación R al conjunto de todas las clases de equivalencia:

X/R = { [x] | x ∈ X }