relaciones de euivalencia

Apuntes de Matem´atica Discreta
8. Relaciones de Equivalencia

Francisco Jos´e Gonz´alez Guti´errez
C´adiz, Octubre de 2004

Universidad de C´
adiz

Departamento de Matem´
aticas

ii

Lecci´
on 8

Relaciones de Equivalencia
Contenido
8.1

Generalidades . . . . . . .
8.1.1 Definici´
on . . . . . . .
8.1.2 Digrafo asociado a una
8.2 Clases de Equivalencia .
8.2.1 Definici´
on . . . . . . .
8.2.2Lema . . . . . . . . .
8.3 Conjunto Cociente . . . .
8.3.1 Teorema . . . . . . . .
8.3.2 Definici´
on . . . . . . .
8.3.3 Teorema . . . . . . . .

. . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
Relaci´
on de Equivalencia
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . .. . . . .
. . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

199
200
201
201201
202
203
203
204
208

La verdad no es un objeto que se encuentre al cabo de una
cadena l´
ogica r´ıgida; tampoco est´
a indeterminada en todas las
direcciones del discurso. En una regi´
on limitada por contornos
excepcionales: descubrir estos contornos es iluminar esa regi´
on,
es explorar lo posible y precisar lo probable, es aplicar a las
cosas la potencia de la claridad y de orden delesp´ıritu; en una
palabra es comprender
Jean Ullmo

8.1

Generalidades

Este tipo de relaciones binarias juegan un papel importante en todas las ciencias porque permiten clasificar los elementos del conjunto en el que est´an definidas.
Muchas veces trataremos a los elementos de un conjunto m´as por sus propiedades que como objetos
individuales. En tales situaciones, podremos ignorar todas las propiedadesque no sean de inter´es y
tratar elementos diferentes como “equivalentes” o indistinguibles, a menos que puedan diferenciarse
utilizando u
´nicamente las propiedades que nos interesen.
La noci´on de “equivalencia” tiene tres caracter´ısticas importantes:
(i) Todo elemento es equivalente a s´ı mismo. (Reflexividad ).
(ii) Si a es equivalente a b, entonces b es equivalente a a. (Simetr´ıa).
199Universidad de C´
adiz

Departamento de Matem´
aticas

(iii) Si a es equivalente a b y b es equivalente a c, entonces a es equivalente a c. (Transitividad ).
Estas propiedades son la base para una clase importante de relaciones binarias sobre un conjunto.

8.1.1

Definici´
on

Una relaci´
on binaria R definida sobre un conjunto A se dice que es de equivalencia cuando es reflexiva,
sim´etrica ytransitiva.
Ejemplo 8.1

Sea A = {1, 2, 3, 4} y
R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (3, 3), (4, 4)} .

Ver si R es de equivalencia.
Soluci´on
Reflexividad. En efecto,
(1, 1) ∈ R, (2, 2) ∈ R, (3, 3) ∈ R y (4, 4) ∈ R
luego,
∀x (x ∈ A =⇒ xRx)
es decir, R es reflexiva.
Simetr´ıa. En efecto,

(1, 2) ∈ R y (2, 1) ∈ R
(3, 4) ∈ R y (4, 3) ∈ R

luego,
∀x, y ∈ A [(x, y) ∈ R =⇒ (y, x) ∈ R]
esdecir, la relaci´
on propuesta es sim´etrica.
Transitividad. En efecto,

(1, 1) ∈ R y (1, 2) ∈ R

=⇒ (1, 2) ∈ R

(1, 2) ∈ R y (2, 1) ∈ R

=⇒ (1, 1) ∈ R

(1, 2) ∈ R y (2, 2) ∈ R

=⇒ (1, 2) ∈ R

(2, 1) ∈ R y (1, 1) ∈ R

=⇒ (2, 1) ∈ R

(2, 1) ∈ R y (1, 2) ∈ R

=⇒ (2, 2) ∈ R

(2, 2) ∈ R y (2, 1) ∈ R

=⇒ (2, 1) ∈ R

(3, 4) ∈ R y (4, 4) ∈ R

=⇒ (3, 4) ∈ R

(3, 3) ∈ R y (3, 4) ∈ R

=⇒ (3, 4) ∈ R

(4,3) ∈ R y (3, 3) ∈ R

=⇒ (4, 3) ∈ R

(4, 4) ∈ R y (4, 3) ∈ R

=⇒ (4, 3) ∈ R

luego,
∀x, y, z ∈ A [(x, y) ∈ R ∧ (y, z) ∈ R =⇒ (x, z) ∈ R]
y la relaci´on es, por tanto, transitiva.
Ejemplo 8.2
(a) La relaci´
on universal sobre cualquier conjunto A es una relaci´on de equivalencia.
200

Matem´
atica Discreta

Francisco Jos´e Gonz´
alez Guti´errez

(b) La relaci´
on vac´ıa ∅ es una relaci´
on de...