RELACIONES 4 - Jair García

Vista previa del material en texto

Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 118 
 
3.4 RELACIONES DE EQUIVALENCIA 
 
Definición 3.4.1 (Relación de equivalencia) 
Sea A un conjunto y R una relación definida sobre A. Diremos que R es una relación de 
equivalencia si y sólo si R es reflexiva, simétrica y transitiva; es decir, si R cumple las 
condiciones.siguientes: 
 
i) (x,x)∈R ∀ x∈A. 
ii) Si (x,y)∈R entonces (y,x)∈R. 
iii) Si (x,y)∈R y (y,z)∈R, entonces (x,z)∈R. 
 
Ejemplo 3.4.1 
a) Sea A=conjunto de todos los triángulos y R la relación en A determinada por la semejanza 
de triángulos, esto es, si t1 y t2 son triángulos en A, entonces (t1, t2)∈R si y sólo si t1 es 
semejante a t2. Determine las propiedades que cumple la relación. 
Solución 
Recordemos que dos triángulos son semejantes, si: 
Los 3 lados son proporcionales. 
Dos lados son proporcionales y el ángulo que sustentan igual. 
Los tres ángulos son iguales. 
 
R es reflexiva, por que los ángulos de t1 son iguales a los ángulos de t1. 
R no es ireflexiva, porque los ángulos de t1 son iguales a los ángulos de t1. 
R es simétrica, por que si los ángulos del triángulo t1 son iguales a los ángulos del 
triángulo t2, entonces los ángulos del triángulo t2 son iguales a los 
ángulos del triángulo t1. 
R no es antisimétrica, por que si los ángulos del triángulo t1 son iguales a los ángulos del 
triángulo t2, entonces los ángulos del triángulo t2 son iguales a los 
ángulos del triángulo t1. 
R es transitiva, porque si los ángulos del triángulo t1 son iguales a los ángulos del 
triángulo t2, y si los ángulos del triángulo t2 son iguales a los 
ángulos del triángulo t3, entonces los ángulos del triángulo t1 son 
iguales a los ángulos del triángulo t3. 
Como R es reflexiva, simétrica y transitiva, R es una relación es de equivalencia. 
 
b) Sea R={(1,1), (1,3), (1,5), (2,2), (2,4), (3,1), (3,3), (3,5), (4,2), (4,4), (5,1), (5,3), (5,5)} 
definida sobre X={1,2,3,4,5}. 
Determinemos las propiedades que cumple la relación. 
Solución 
R es reflexiva, por que (1,1), (2,2), (3,3), (4,4), (5,5)∈R. 
R no es irreflexiva, porque (1,1)∈R. 
R es simétrica, porque (1,3)∈R y (3,1)∈R, (1,5)∈R y (5,1)∈R. 
(2,4)∈R y (4,2)∈R (3,1)∈R y (1,3)∈R. 
(3,5)∈R y (5,3)∈R (4,2)∈R y (2,4)∈R. 
(5,1)∈R y (1, 5)∈R (5,3)∈R y (3,5)∈R. 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 119 
 
R no es simétrica, por que (1,3)∈R y (3,1)∈R. 
R es transitiva, porque (1,3)∈R y (3,1)∈R→(1,1)∈R. 
(1,3)∈R y (3,5)∈R→(1,5)∈R. 
(1,5)∈R y (5,1)∈R→(1,1)∈R. 
(1,5)∈R y (5,3)∈R→(1,3)∈R. 
(2,4)∈R y (4,2)∈R→(2,2)∈R. 
(3,1)∈R y (1,3)∈R→(3,3)∈R. 
(3,1)∈R y (1,5)∈R→(3,5)∈R. 
(3,5)∈R y (5,1)∈R→(3,1)∈R. 
(3,5)∈R y (5,3)∈R→(3,3)∈R. 
(4,2)∈R y (2,4)∈R→(4,4)∈R. 
(5,1)∈R y (1,3)∈R→(5,3)∈R. 
(5,1)∈R y (1,5)∈R→(5,5)∈R. 
(5,3)∈R y (3,1)∈R→(5,1)∈R. 
(5,3)∈R y (3,5)∈R→(5,5)∈R. 
Como la relación es reflexiva, simétrica y transitiva, R es una relación de equivalencia. 
 
Ejemplo 3.4.2 
a) Sea el conjunto A={a,b,c,d,e} y R=Ax(A-{a}), Determinar si R es: reflexiva, simétrica, 
asimétrica, antisimétrica, transitiva, de equivalencia, de orden parcial o de orden total. 
Solución 
R no es reflexiva, a∈A y (a,a)∉R. 
R no es simétrica, (a,b)∈R y (b,a)∉R. 
R no es asimétrica, (b,c)∈R y (c,b)∈R. 
R no es antisimétrica, (b,c)∈R y (c,b)∈R pero b≠c. 
R es transitiva, si (a,b) ∈R y (b,c)∈ se tiene que (a,c)∈R. 
R no es de equivalencia, R no es reflexiva ni es simétrica. 
R no es de orden parcial, R no es reflexiva. 
La relación no es de orden parcial R no es reflexiva ni antisimétrica. 
 
b) Sea el conjunto A={1,2,3,4,5,6,7,8,9}, P(A) el conjunto potencia de A, y R la relación 
definida en P(A)xP(A) dada por R={(x,y)| x∩y≠∅}. Determine si R es reflexiva, simétrica, 
asimétrica, antisimétrica, transitiva, de equivalencia, de orden parcial o de orden total. 
Solución 
R no es reflexiva, ∅∈P(A) y ∅∩∅=∅. 
R es simétrica, la intersección de conjuntos es conmutativa así, si x∩y≠∅ entonces, 
y∩x≠∅. 
R no es asimétrica, por que es simétrica. 
R no es antisimétrica, por que si x∩y≠∅ se tiene que y∩x≠∅ y x≠y. 
R no es transitiva, por que si x∩y≠∅ y y∩z≠∅ no implica que x∩z≠∅. 
Contraejemplo: sean x={1,2,3}, y={2,3,4,5} y z={5,6,7} 
 
x∩y={2,3}≠∅, y∩z={5}≠∅ pero x∩z≠∅, de lo anterior se concluye 
que (x,y)∈R, (x,z)∈R pero (x,z)∉R. 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 120 
 
De lo anterior concluimos que: 
R no es de equivalencia por que no es reflexiva ni transitiva. 
R no es de orden parcial por que R no es transitiva, no es reflexiva y no es antisimétrica. 
R no es de orden total por que no es reflexiva ni transitiva. 
R no es de cuasiorden por que no es reflexiva ni transitiva. 
 
Ejemplo 3.4.3 
a) Determinar las propiedades que cumple la relación. 
R={(x,y)|3 divide a x–y} 
Definida sobre el conjunto de los enteros. 
Solución 
Reflexiva. 
La relación es reflexiva, si para todo x entero se cumple que (x,x)∈R. 
Por la definición de la relación (x,x)∈R, si 3 divide a x–x. 
Por la definición de divisibilidad 3|x–x si existe q∈Z tal que x–x=3q. 
Como x–x=0, entonces 0=3q y el entero que cumple con esta condición es 0. 
Así 3|x–x y (x,x)∈R. 
Por lo tanto, la relación R es reflexiva. 
 
Irreflexiva 
La relación es irreflexiva, si se cumple que (x,x)∉R. 
Sin embargo mostramos que (x,x)∈R para todo número entero. 
Por lo tanto, la relación no es irreflexiva. 
 
Simétrica 
La relación es simétrica, si para todo (x,y)∈R se cumple (y,x)∈R. 
Lo que nos señala que hay que mostrar que la proposición condicional es válida. 
Por hipótesis se tiene que (x,y)∈R, lo que implica que 3|x–y, esto es, que existe un entero q1 
tal que x–y=3q1. 
Hay que mostrar que (y,x)∈R, esto es, que existe un entero q tal que y–x=3q. 
Ahora bien y–x=–(x–y)=–3q1=3(–q1) 
Así es posible representar a y–x como el producto de 3 y de –q1, y este es el entero que se 
buscaba. 
Por lo tanto, la relación es simétrica. 
 
Antisimétrica 
La relación es antisimétrica, si para todo (x,y)∈R con x≠y se cumple que (y,x)∉R. 
La proposición condicional, tiene por hipótesis (x,y)∈R, lo que implica que 3|x–y, esto es, 
existe un entero q1≠0 tal que x–y=3q1. 
Hay que mostrar (y,x)∉R, esto es, que no existe un entero q tal que y–x=3q o, de manera 
equivalente que y–x=3q donde q∉Z. 
 
Se tiene que, y–x=–(x–y)=–3q1=3(–q1) y –q1∈Z, por lo tanto no se cumple la proposición 
condicional y la relación no es antisimétrica. 
 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 121 
 
Transitiva 
La relación es transitiva, si para todo (x,y)∈R y para todo (y,z)∈R se cumple (x,z)∈R. 
Por hipótesis se tiene que (x,y)∈R y (y,z)∈R lo que implica que 3|x–y,3|y–z esto es, que 
existen enteros q1 y q2 tales que x–y=3q1 y y–z =3q2. 
Se debe mostrar que (x,z)∈R, esto es, que existe un entero q tal que x–z=3q. 
Sumando las dos igualdades de la hipótesis, se tiene: 
(x–y)+(y–z)=3q1 + 3q2 
x–z=3(q1+q2) 
así, es posible representar a x–z como el producto de 3 y de un número entero q=q1+q2, 
(q1+q2 es entero porque tanto q1 como q2 lo son) 
Por lo tanto, la relación es transitiva. 
 
Ley de Tricotomía 
La relación no cumple la ley de tricotomía, porque para x y x en Z, se tiene que x=x y que 
(x,x)∈R; cumpliéndose más de una de las condiciones para la ley de tricotomía. 
 
De lo anterior concluimos que: 
R es de equivalencia por que es reflexiva, simétrica y transitiva. 
R no es de orden por que no es antisimétrica. 
R no es de orden parcial por que no es antisimétrica. 
R no es de orden total no cumple la ley de tricotomia. 
R es de cuasiorden por que es reflexiva y transitiva. 
 
b) Determinar las propiedades que cumple la relación R={(x,y)|x≤y}, definida sobre el 
conjunto de los enteros. 
Solución 
Reflexiva. 
La relación es reflexiva, si para todo x entero se cumple que (x,x)∈R. 
Por la definición de la relación (x,x)∈R,si x≤x, como x=x, se cumple la igualdad y (x,x)∈R. 
Por lo tanto, la relación R es reflexiva. 
 
Irreflexiva 
La relación es irreflexiva, si se cumple que (x,x)∉R. 
Sin embargo mostramos que (x,x)∈R para todo número entero. 
Por lo tanto, la relación no es irreflexiva. 
 
Simétrica 
La relación es simétrica, si para todo (x,y)∈R se cumple (y,x)∈R. 
Lo que nos señala que hay que mostrar que la proposición condicional es válida. 
Tiene por hipótesis (x,y)∈R, lo que implica que x≤y. 
Hay que mostrar (y,x) ∈ R, esto es, que y≤x. 
 
Por hipótesis x≤y, así x no es mayor que y y (y,x)∉R 
Por lo tanto, la relación no es simétrica. 
 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 122 
 
Antisimétrica 
La relación es antisimétrica, si para todo (x,y)∈R con x≠y se cumple que (y,x)∉R 
Tiene por hipótesis (x,y)∈R, lo que implica que x<y. 
Hay que mostrar (y,x)∈R, esto es, que y<x. 
Por hipótesis x<y, así x no es mayor que y y (y, x)∉R. 
Por lo tanto, la relación es antisimétrica. 
 
Transitiva 
La relación es transitiva, si para todo (x,y)∈R y para todo (y,z)∈R se cumple (x,z)∈R. 
Por hipótesis se tiene que Hipótesis (x,y)∈R y (y,z)∈R lo que implica que x≤y y y≤z. 
Se debe mostrar que (x,z)∈R, esto es, x≤z. 
Se tiene que x≤y≤z por lo tanto x≤z. 
Por lo tanto la relación es transitiva. 
 
Ley de Tricotomía 
La relación no cumple la ley de tricotomía, porque para x y x en Z, se tiene que x=x y 
(x,x)∈R; cumpliéndose más de una de las condiciones para la ley de tricotomía. 
 
De lo anterior concluimos que: 
R no es de equivalencia por que no es simétrica. 
R es de orden por que es transitiva y antisimétrica. 
R es de orden parcial por que es reflexiva, transitiva y antisimétrica. 
R no es de orden total no cumple la ley de tricotomía. 
R es de cuasiorden por que es reflexiva y transitiva. 
 
c) Determinar las propiedades que cumple la relación 
R={(x,y)| 2x y− ≤ } 
Definida sobre el conjunto de los enteros. 
Solución 
Reflexiva. 
La relación es reflexiva, si para todo x entero se cumple que (x,x)∈R. 
Por la definición de la relación (x,x) ∈ R, si 2x y− ≤ . 
0 2x x− = ≤ , así (x,x)∈R. 
Por lo tanto, la relación R es reflexiva. 
 
Irreflexiva 
La relación es irreflexiva, si se cumple que (x,x)∉R. 
Sin embargo mostramos que (x,x)∈R para todo número entero. 
Por lo tanto, la relación no es irreflexiva. 
 
Simétrica 
La relación es simétrica, si para todo (x,y)∈R se cumple (y,x)∈R. 
Hipótesis (x,y)∈R, lo que implica que 2x y− ≤ 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 123 
 
Hay que mostrar (y,x)∈R, esto es 2y x− ≤ . 
( 1)( ) 1 2y x x y x y x y x y− = − + = − − = − − = − ≤ . 
luego (y,x)∈R. or lo tanto, la relación es simétrica. 
 
Antisimétrica 
La relación es antisimétrica, si para todo (x,y)∈R con x≠y se cumple que (y,x)∉R. 
Hipótesis (x,y)∈R, lo que implica que 2x y− ≤ 
Hay que mostrar (y,x)∉R, esto es, que 2y x− ≤ o, de manera equivalente que 2y x− > , 
sin embargo encontramos que 2y x− ≤ ; por lo que (y, x)∈R. 
Por lo tanto, la relación no es antisimétrica. 
 
Transitiva 
La relación es transitiva, si para todo (x, y)∈R y para todo (y, z)∈R se cumple (x, z)∈R. 
Hipótesis (x,y)∈R y (y, z)∈R, lo que implica que 2x y− ≤ y 2y z− ≤ 
Hay que mostrar que (x, z) ∈ R, esto es, que 2x z− ≤ . 
( ) ( ) 2 2 4x z x y y z x y y z x y y z− = − + − = − + − ≤ − + − ≤ + = . 
Luego, 4x z− ≤ y (x, z)∉R. 
Por lo tanto, la relación no es transitiva. 
 
Ley de Tricotomía 
La relación no cumple la ley de tricotomía, porque para x y x en Z, se tiene que x=x y que 
(x,x)∈R; cumpliéndose más de una de las condiciones para la ley de tricotomía. 
 
De lo anterior concluimos que: 
R no es de equivalencia por que no es transitiva. 
R no es de orden por que no es ni transitiva ni antisimétrica. 
R no es de orden total por que no es transitiva y no cumple la ley de tricotomía. 
R no es de cuasiorden por que no es transitiva. 
 
Partición de un conjunto 
 
De alguna manera estamos familiarizados con el concepto de partición. En anatomía por 
ejemplo se puede hacer una partición del cuerpo humano en: cabeza, tronco y extremidades. La 
división de un país en estados, etc. En matemáticas se usa también este concepto asociado con las 
relaciones de equivalencia. 
 
Para introducir el concepto consideremos la partición de una casa, está se puede dividir en: 
sala, comedor, cocina, recamara y baño; cada una de las partes de la casa no es vacía no vamos a 
decir que se considera un cuarto que no exista, ninguna de las partes de la casa tiene un fin 
diferente lo que señala que no son iguales; y finalmente si juntamos todas las partes de la casa lo 
 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 124 
 
que se obtiene es precisamente una casa, no algo menos o más. Este ejemplo nos muestra las 
condiciones que se debe tener el conjunto para poder tener lo que llamamos partición, veamos la 
definición del concepto. 
 
Definición 3.4.2 (Partición de un conjunto) 
Sea X un conjunto y L(X) un conjunto de subconjuntos de X (que no es el conjunto 
potencia de X). Diremos que L(X) es una partición del conjunto X si y sólo si se cumple las 
siguientes propiedades: 
i) El conjunto vacío no pertenece a L(X); simbólicamente φ∉L(X). 
ii) Todos los elementos de L(X) son ajenos entre sí; en forma simbólica Ai∩Aj=φ, para i≠j y 
Ai, Aj∈L(X). 
iii) La unión de todos los elementos de L(A) es igual a A; simbólicamente A=∪Ai. 
 
Ejemplo 3.4.4 
a) Sea X={1,2,3,4,5,6,7,8,9,10}. 
Una partición de X es L(X)={A1,A2} donde A1={1,3,5,7,9} y A2={2,4,6,8,10} 
Puede verse que: 
i)A1≠φ; A2≠φ. 
ii)A1 ∩A2=φ. 
iii)A1∪A2=A. 
 
Otra partición de X es 
L2(X)={A1,A2,A3,A4}. 
Donde A1={2,3}, A2={1,4,5}, A3={6,7,8,9}, y A4={10}. 
Es posible verificar que se cumplen las condiciones de la definición. 
 
Finalmente otra partición de X la constituye el mismo conjunto X, esto es: 
L3(X)={X}. 
 
b) Dado el conjunto X={1,2,3,4,5,6}, se tiene la partición L(X)={A1,A2,A3} 
donde A1={1,3,5}, A2={2,6} y A3={4}. Es una partición porque: 
i)A1={1,3,5}≠φ. 
A2={2,6}≠φ. 
A3={4}≠φ. 
 
ii)A1 ∩A2=φ, A1 ∩A3=φ y A2 ∩A3=φ. 
 
iii)A1∪A2∪A3={1,2,3,4,5,6}=X. 
 
El siguiente teorema muestra como utilizar una partición para definir una relación de 
equivalencia. 
 
Teorema 3.4.1 
Sea L(X) una partición del conjunto X. Defínase xRy si x y y pertenecen a Ai para algún 
Ai∈ L(X). Entonces R es reflexiva, simétrica y transitiva. 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 125 
 
Demostración 
 Reflexiva 
Sea x∈X. Como X=∪Ai, x∈Ai para algún Ai∈L(X). Entonces xRx y R es reflexiva. 
 Simétrica 
Supóngase que xRy. Entonces x y y pertenecen a algún conjunto Ai∈L(X). Como x y y 
pertenecen a Ai, yRx y R es simétrica. 
 Transitiva 
Supóngase que xRy y yRz. Entonces x y y pertenecen a un conjunto Ai∈L(X); asimismo, y 
y z pertenecen a un conjunto Aj∈L(X). Si Ai≠Aj, se tiene que y pertenecería a Ai y a Al; 
pero como L(X) es una familia disjunta por pares, esto es imposible. Entonces Ai=Ajy 
tanto x como z pertenecen a Ai. Por lo tanto xRz y R es transitiva. 
 
Ejemplo 3.4.5 
a) Considérese la partición L={{1,3,5},{2,6},{4}} de X={1,2,3,4,5,6}. 
Determine la relación R sobre X. 
Solución 
R={(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),(2,2),(2,6),(6,2),(6,6),(4,4)}. 
 
b) Dado el conjunto X={1,3,5,7,9} y la partición L(X)={{1,3}, {5}, {7,9}}, determine la 
relación de equivalencia que corresponda a esta partición. 
Solución 
R={(1,1),(1,3),(3,1),(3,3),(5,5),(7,7),(7,9)(9,7),(9,9)}. 
 
Sean L(X) y R como en el teorema anterior. Si Ai∈L(X) es posible considerar los 
elementos de Ai como equivalentes en el sentido de la relación R. Por esta razón, las relaciones 
que son reflexivas, simétricas y transitivas se llaman relaciones de equivalencia. 
 
3.4.1 Clases de equivalenciaDefinición 3.4.3 (Clases de equivalencia) 
Sea R una relación de equivalencia en un conjunto X. Los conjuntos 
[a]={x∈X│xRa o (x,a)∈R} se denominan clases de equivalencia de X inducidas por la relación 
R. 
 
Ejemplo 3.4.6 
a) Consideremos la relación de equivalencia 
 
{ }(1,1), (1,3), (1,5), (2, 2), (2,6), (3,1), (3,3), (3,5), (4, 4), (5,1), (5,3), (5,5), (6, 2), (6,6)R = 
definida sobre X={1,2,3,4,5,6} 
Las clases de equivalencia son: 
[1]={1,3,5}. 
[2]={2,6}. 
[3]={1,3,5}. 
[4]={4}. 
[5]={1,3,5}. 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 126 
 
[6]={2,6}. 
Observemos que hay clases de equivalencia iguales 
[1]=[3]=[5] 
[2]=[6] 
y que precisamente son iguales las clases de los elementos que la conforman. Así 
observamos que [1]={1, 3, 5} y [1]=[3] =[5]. 
 
b) Consideremos la relación de equivalencia 
R={(1,1), (1,3), (1,5), (2,2), (2,4), (3,1), (3,3), (3,5), (4,2), (4,4), (5,1), (5,3), (5,5)} 
Sobre X={1,2,3,4,5} 
Las clases de equivalencias son: 
[1]={1,3,5}. 
[2]={2,4}. 
[3]={1,3,5}. 
[4]={2,4}. 
[5]={1,3,5}. 
 
c) Sea X={1,2,3,4,5,6,7,8,9,10}. Defínase xRy si 3 divide a 3–y. Esta es una relación de 
equivalencia, (puede verificarse). 
Clase de equivalencia: 
[1] esta formada por todos los x tales que xR1, así 
[1]={x∈X|3 divide a x–1}={1,4,7,10}. 
[2]={x∈X|3 divide a x–2}={2,5,8}. 
[3]={x∈X|3 divide a x–3}={3,6,9}. 
[4]={x∈X|3 divide a x–4}={1,4,7,10}. 
[5]={x∈X|3 divide a x–5}={2,5,8}. 
[6]={x∈X|3 divide a x–6}={3,6,9}. 
[7]={x∈X|3 divide a x–7}={1,4,7,10}. 
[8]={x∈X|3 divide x–8}={2,5,8}. 
[9]={x∈X|3 divide a x–9}={3,6,9}. 
[10]={x∈X|3 divide a x–10}={1,4,7,10}. 
En donde se tiene que: 
[1]=[4]=[7]=[10]. 
[2]=[5]=[8]. 
[3]=[6]=[9]. 
 
La relación de equivalencia que consideramos es semejante a plantear, están en la relación 
las diferencias que tienen el mismo residuo cuando se divide entre 3. 
 
Ejemplo 3.4.7 
Sea A un conjunto cualquiera y sea R la relación de igualdad definida en A. Para cualquier 
x∈A la clase de equivalencia de x es simplemente {x}, esto es [x]={x}. 
 
 
 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 127 
 
Ejemplo 3.4.8 
Sea X = {1,2,3,...10}. Defínase xRy si 3 divide a x-y. Puede verificarse que la relación R es 
reflexiva, simétrica y transitiva. Esto es, que R es una relación de equivalencia sobre X. 
Determinar los elementos de las clases de equivalencia. 
 
Solución 
La clase de equivalencia de [1] está formada por todos los x con xR1. Es decir 
[1]={x∈X|3 divide a x-1}={1,4,7,10}. 
[2]={2,5,8}. 
[3]={3,6,9}. 
Estos tres conjuntos forman una partición de X. Obsérvese que 
[1]=[4]=[7]=[10]. 
[2]=[5]=[8]. 
[3]=[6]=[9]. 
Esta relación equivalencia quiere decir “se tiene el mismo residuo cuando se divide entre 
3”. 
 
Ejemplo 3.4.9 
Sea R={(x,y)|x≡y (mod d), x,y,d ∈ Z y d≠0}= {(x,y)|x–y es divisible por d}, una relación 
de equivalencia. 
Si R={(x,y)|x≡y (mod 4) }. 
[0]={...,-16,-12,-8,-4,0,4,8,12,16,...}={4n|n∈Z}. 
[1]={...–15,-11,-7,-4,1,5,9,13,17,...}={4n+1|n∈Z}. 
[2]={ ...–14,-10,-6,-2, 2,6,10,14,18,...}={4n+2|n∈Z}. 
[n]={ 4n+n|n∈Z}. 
 
Teorema 3.4.2 
Sea R una relación de equivalencia sobre un conjunto X, para cada a∈X, sea 
[a]={x∈X|xRa} 
Entonces 
L(X)={[a]|a∈X} 
Es una partición de X. 
De mostración 
Hay dos hechos que deben verificarse con el fin de probar que es una partición de X. 
i) X=∪Ai para todo Ai ∈L(X). 
ii) L(X) es una familia disjunta por pares. 
Sea a∈X. Puesto que aRa, a∈[a]. En consecuencia X=∪Ai lo que verifica i). 
 
Debe demostrarse que L(X) es una familia disjunta por pares. Supóngase que [a] y 
[b]∈L(X) con [a]≠[b]. Se probará que [a]∩[b]=∅. Supóngase por reducción al absurdo, que 
para algún x se tienen que x∈[a]∩[b]. Entonces xRa y xRb. El resultado anterior muestra que 
[x]=[a] y [x]=[b]. Consecuentemente, [a]=[b], lo cual es una contradicción. Por lo tanto, 
[a]∩[b]=∅ y L(X) es una familia disjunta por pares. 
 
 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 128 
 
3.4.2 El conjunto cociente 
 
Definición 3.4.4 (Conjunto cociente) 
La colección de las clases de equivalencia, [x], [y], [z]..., de un conjunto X se denomina 
conjunto cociente o conjunto factor de X por R y se escribe simbólicamente como: 
X
R ={[x], [y], [z]...} 
 
Teorema 3.4.3 
Toda relación de equivalencia R definida sobre un conjunto X, induce en X una partición. 
Esta es X R , así el conjunto cociente es una partición del conjunto A. 
 
Ejemplo 3.4.10 
Sea R={(1,1), (1,3), (1,5), (2,2), (2,4), (3,1), (3,3), (3,5), (4,2), (4,4), (5,1), (5,3), (5,5)} 
definida sobre X={1,2,3,4,5}. 
Las clases de equivalencia son: 
[1]={1,3,5}. 
[2]={2, 4}. 
[3]={1,3,5}. 
[4]={2,4}. 
[5]={1,3,5}. 
Así el conjunto cociente de R es 
{ } { } { } { }{ }[1],[2],[3],[4],[5] [1],[2] 1,3,5 , 2,4X R = = = 
Observe que el conjunto cociente es una partición del conjunto X. 
i) [1]={1,3,5}≠∅ y [2]={2,4}≠∅. 
ii) [1]∩[2]=∅. 
iii) [1]∪[2]={1,3,5,2,4}={1,2,3,4,5}=X. 
Con esto verificamos que el conjunto cociente es una partición de X. 
 
Ejemplo 3.4.11 
Sea A={-4,-3,-2,-1,0,1,2,3,4,} y R={(x,y)|x(x+1)=y(y+1)}. Determinar si R es una relación 
de equivalencia, si la relación es de equivalencia encontrar el conjunto cociente de la relación. 
Solución 
Reflexiva 
R es reflexiva puesto que x(x+1)=x(x+1), por lo que se tiene que (x,x)∈R. 
 
Simétrica 
La relación es simétrica ya que si (x,y)∈R se tiene que x(x+1)=y(y+1) y como 
y(y+1)=x(x+1) se tiene que (y,x)∈R. 
Transitiva 
La relación es transitiva, ya que si x(x+1)=y(y+1) y y(y+1)=z(z+1) se tiene que 
x(x+1)=z(z+1). 
Como la relación es reflexiva, simétrica y transitiva la relación es de equivalencia. 
La relación es: 
 
Unidad III. Relaciones Relaciones de equivalencia 
Una introducción a las matemáticas de la computación 129 
 
R={(0,0), (0,-1), (1,0), (-1,-1), (1,1), (1,-2), (-2,2), (2,2), (2,-3), (-3,2), (-3,-3), (3,3), (3,-4), 
(-4,3), (-4,4), (4,4)}. 
 
Las clases de equivalencia son [0]={0,-1}, [1]={1,-2}, [2]={2,-3}, [3]={3,-4} y [4]={4}. 
 
El conjunto cociente es ]}.4[],3[],2[],1[],0{[=RA 
 
 
	3.4 RELACIONES DE EQUIVALENCIA
	Partición de un conjunto