Ciencias Directas

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 unacadena 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 estos contornos 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.1Generalidades

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
Muchas veces 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 elementosdiferentes como “equivalentes” o indistinguibles, a menos que puedan diferenciarse
utilizando unicamente las propiedades que nos interesen.
´
La noci´n de “equivalencia” tiene tres caracter´
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
aDepartamento 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 clase importante 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.1Sea 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 =⇒ xR x)
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 ]
y la relaci´n es, por tanto, transitiva.
o
Ejemplo 8.2
(a) La relaci´n universal sobre cualquier conjunto A es una relaci´n de equivalencia.
o
o
200

Matem´tica Discreta
a

Francisco Jos´ Gonz´lez...