Matemáticas | Cierre de Relaciones y Relaciones de Equivalencia

Prerrequisito: Introducción a las Relaciones , Representación de Relaciones

Relaciones combinadas:

Como sabemos que las relaciones son solo conjuntos de pares ordenados, todas las operaciones con conjuntos se aplican a ellos también. Dos relaciones se pueden combinar de varias maneras, tales como:

Unión: $R_{1} \copa R_{2}$ consiste en todos los pares ordenados de ambas relaciones. Pares ordenados duplicados eliminados de Union.
Intersección: $R_{1} \cap R_{2}$ consiste en pares ordenados que están en ambas relaciones.
Diferencia: $R_{1} - R_{2}$ consta de todos los pares ordenados solo en $R_{1}$ , pero no en $R_{2}$ .
Diferencia simétrica: $R_{1} \oplus R_{2}$ consiste en todos los pares ordenados que están en $R_{1}$ o $R_{2}$ pero no en ambos.

Hay otra manera de combinar dos relaciones que es análoga a la composición de funciones.

Composición – Sea $R$ una relación de $A$ a $B$ y $S$ una relación de $B$ a $C$ , entonces el compuesto de $R$ y $S$ , denotado por $S \ círculo R$ , es la relación que consta de pares ordenados $(C.A)$ donde $a \en A, c \en C$ y para los cuales existe un elemento $b \ en B$ tal que $(a, b) \en R$ y $(b, c) \en S$ .

Ejemplo: ¿Cuál es el compuesto de las relaciones $R$ y $S$ dónde $R$ es una relación de $\{1, 2, 3\}$ a $\{1, 2, 3, 4\}$ con $R = \{(1,1), (1,4), (2,3), (3,1), (3,4)\}$ y $S$ es una relación de $\{1, 2, 3, 4\}$ a $\{0, 1, 2\}$ con $S = \{(1,0), (2,0), (3,1), (3,2), (4,1)\}$ ?
Solución: al calcular todos los pares ordenados a los que pertenece el primer elemento $R$ y el segundo elemento $S$ , obtenemos:
$S\circ R = \{(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)\}$

Composición de la Relación sobre sí misma:

Una relación se puede componer consigo misma para obtener un grado de separación entre los elementos del conjunto sobre el que $R$ se define.

Let  be a relation on the set .
The powers  where  are defined recursively by -
 and .

Teorema – Sea $R$ una relación sobre el conjunto A, representada por un dígrafo. Existe un camino de longitud $norte$ , donde $norte$ es un entero positivo, desde $a$ hasta $b$ si y solo si $(a,b) \en R^n$ .

Nota importante: una relación $R$ en conjunto $A$ es transitiva si y solo si $R^n \subconjunto R$ para $n = 1, 2, 3,....$

Cierre de Relaciones :

Considere una relación $R$ en el set $A$ . $R$ puede o no tener una propiedad $PAGS$ , como reflexividad, simetría o transitividad.

Si hay una relación $S$ con propiedad $PAGS$ que contiene $R$ tal que $S$ es el subconjunto
de toda relación con propiedad $PAGS$ que contiene $R$ , entonces $S$ se llama cierre de
$R$ con respecto a $PAGS$ .

Podemos obtener cierres de relaciones con respecto a la propiedad $PAGS$ de las siguientes maneras:

Cierre reflexivo: $\Delta = \{(a,a)\:|\:a\en A\}$ es la relación diagonal en el conjunto $A$ . El cierre reflexivo de la relación $R$ en el set $A$ es $R\copa \Delta$ .
Cierre simétrico: sea $R$ una relación en conjunto $A$ y $R^{-1}$ sea la inversa de $R$ . El cierre simétrico de la relación $R$ en conjunto $A$ es $R\taza R^{-1}$ .
Cierre transitivo: sea $R$ una relación en conjunto $A$ . La relación de conectividad se define como – $R^* = \bigcup\limits_{n=1}^{\infty} R^n$ . La clausura transitiva de $R$ es $R^*$ .

Ejemplo – Sea $R$ una relación en conjunto $\{1, 2, 3, 4\}$ con $R = \{(1,1), (1,4), (2,3), (3,1), (3,4)\}$ . Encuentre el cierre reflexivo, simétrico y transitivo de R.

Solución –
Para el conjunto dado, $\Delta = \{(1, 1), (2, 2), (3, 3), (4, 4)\}$ . Entonces el cierre reflexivo de $R$ es $R \cup \Delta = \{(1,1), (1,4), (2,2), (2,3), (3,1), (3,3), (3,4), (4,4)\}$

Para el cierre simétrico necesitamos el inverso de $R$ , que es
$R^{-1} = \{(1,1), (1,3), (3,2), (4,1), (4,3)\}$ .
El cierre simétrico de $R$ is-
$\{(1,1), (1,3), (1,4), (2,3), (3,1), (3,2), (3,4), (4,1), (4,3)\}$

Para el cierre transitivo, necesitamos encontrar $R^*$ .
$\therefore$ tenemos que encontrar $R^1, R^2, ... ,$ hasta $R^{n} = R^{n-1}$ . Nos detenemos cuando se logra esta condición ya que encontrar poderes superiores $R$ sería lo mismo.
$R^{1} = \{(1,1), (1,4), (2,3), (3,1), (3,4)\}$
$R^{2} = \{(1,1), (1,4), (2,1), (2,4), (3,1), (3,4)\}$
$R^{3} = \{(1,1), (1,4), (2,1), (2,4), (3,1), (3,4)\}$
Ya $R^{2} = R^{3}$ que, detenemos el proceso.
Cierre transitivo, $R^* = R^1 \cup R^2$ –
$\{(1,1), (1,4), (2,1), (2,3), (2,4), (3,1), (3,4)\}$

Relaciones de equivalencia:

Sea $R$ una relación en conjunto $A$ . Si $R$ es reflexiva, simétrica y transitiva, se dice que es una relación de equivalencia.
En consecuencia, se dice que dos elementos $a$ y $b$ relacionados por una relación de equivalencia son equivalentes.

Ejemplo: demuestre que la relación
$R = \{(a,b)\:|\: a\equiv b (mod\:m)\}$ es una relación de equivalencia. $a\equiv b (mod\:m)$ es la función módulo de congruencia $m$ . Es verdadero si y sólo si $m$ divide $a-b$ .

Solución – Para mostrar que la relación es una relación de equivalencia debemos probar que la relación es reflexiva, simétrica y transitiva.

Reflexivo: para cualquier elemento $a$ , $a - a = 0$ es divisible por $m$ .
$\therefore a \equiv a (mod\:m)$ . Entonces, el módulo de congruencia $m$ es reflexivo.
Simétrico: para dos elementos cualquiera $a$ y $b$ , si $(a,b)\in R$ o es $a\equiv b (mod\:m)$ divisible $a - b$ por $m$ , entonces $b - a$ también es divisible por $m$ .
$\therefore b\equiv a (mod\:m)$ . Entonces el módulo de congruencia $m$ es simétrico.
Transitiva – Para cualquier tres elementos $a$ , $b$ , y $c$ si $(a,b), (b,c) \in R$ entonces-
$(a-b) mod\:m = 0$
$(b-c) mod\:m = 0$
Sumando ambas ecuaciones,
$\begin{flalign*} &\Rightarrow (a-b) mod\:m + (b-c) mod\:m = 0\\ &\Rightarrow (a-b+b-c) mod\:m = 0\\ &\Rightarrow (a-c) mod\:m = 0 \end{flalign}$

$\therefore a \equiv c (mod\:m)$ . Entonces, $R$ es transitivo.

Como la relación $R$ es reflexiva, simétrica y transitiva, concluimos que $R$ es una relación de equivalencia.

Clases de equivalencia:

Sea $R$ una relación de equivalencia sobre conjunto $A$ .
Sabemos que si $(a,b) \in R$ entonces $a$ y $b$ se dice que son equivalentes con respecto a $R$ .

El conjunto de todos los elementos que están relacionados con un elemento $a$ de $A$ se denomina
clase de equivalencia de $a$ . Se denota por $[a]_{R}$ o simplemente $[a]$ si sólo hay una
relación a considerar.
Formalmente,
$[a]_{R} = \{s\: |\: (a,s) \in R\}$

Se dice que cualquier elemento $b \in [a]_{R}$ es el representante de $[a]_{R}$ .
Nota Importante: Todas las clases de equivalencia de una Relación $R$ en conjunto $A$ son iguales o disjuntas y su unión da el conjunto $A$ .
$\bigcup[a]_{R} = A$
Las clases de equivalencia también se denominan particiones ya que son disjuntas y su unión da el conjunto sobre el que se define la relación.

Ejemplo: ¿Cuáles son las clases de equivalencia de la relación Módulo de Congruencia $m$ ?
Solución: Sean $a$ y $b$ dos números tales que $a \equiv b\:(mod\:m)$ . Esto significa que el resto obtenido al dividir $a$ y $b$ con $m$ es el mismo.
Valores posibles para el resto- $0, 1, 2, ..., m-1$
Por lo tanto, hay $m$ clases de equivalencia- $[0]_{m}, [1]_{m}, ...,[m-1]_{m}$
$[0]_{m} = \{...,-2m, -m, 0, m, 2m,..., \}$
$[1]_{m} = \{...,-2m + 1, -m + 1, 1, m + 1, 2m + 1,..., \}$
$.$
$.$
$[m-1]_{m} = \{...,-2m - 1, -m - 1 , m - 1, 2m - 1,..., \}$

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2013, Pregunta 1
2. GATE CS 2005, Pregunta 42
3. GATE CS 2001, Pregunta 2
4. GATE CS 2000, Pregunta 28

Referencias –
Composición de relaciones – Wikipedia
Matemáticas discretas y sus aplicaciones, por Kenneth H Rosen

Este artículo es una contribución de Chirag Manwani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta