Relaciones de equivalencia

Apuntes de Matem´tica Discreta
a
8. Relaciones de Equivalencia

Francisco Jos´ Gonz´lez Guti´rrez
e
a
e
C´diz, Octubre de 2004
a

Universidad de C´diz
a

Departamento de Matem´ticas
a

ii

Lecci´n 8
o

Relaciones de Equivalencia
Contenido
8.1

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

. . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
Relaci´n de Equivalencia
o
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
.. . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

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

199
200
201
201
201
202
203
203
204
208

La verdad no es un objeto que se encuentre al cabo de una
cadena l´gica r´
o
ıgida; tampoco est´ indeterminada en todas las
a
direcciones del discurso. En una regi´n limitada por contornos
o
excepcionales: descubrir estoscontornos es iluminar esa regi´n,
o
es explorar lo posible y precisar lo probable, es aplicar a las
cosas la potencia de la claridad y de orden del esp´
ı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´n definidas.
a
Muchasveces trataremos a los elementos de un conjunto m´s por sus propiedades que como objetos
a
individuales. En tales situaciones, podremos ignorar todas las propiedades que no sean de inter´s y
e
tratar elementos diferentes como “equivalentes” o indistinguibles, a menos que puedan diferenciarse
utilizando unicamente las propiedades que nos interesen.
´
La noci´n de “equivalencia” tiene trescaracter´
o
ı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´diz
a

Departamento de Matem´ticas
a

(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 claseimportante de relaciones binarias sobre un conjunto.

8.1.1

Definici´n
o

Una relaci´n binaria R definida sobre un conjunto A se dice que es de equivalencia cuando es reflexiva,
o
sim´trica y transitiva.
e
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´n
o
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´ En efecto,
ıa.

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

luego,
∀x, y ∈ A [(x, y) ∈ R =⇒ (y, x) ∈ R]
es decir, la relaci´n propuesta es sim´trica.
o
e
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]...