Tema 3

Relaciones.

Recordemos que si A y B son conjuntos, una relación binaria de A en B es cualquier subcon-

junto del producto cartesiano A × B. Una relación binaria en A es un subconjunto de A × A.
Si R es una relación binaria de A en B, escribiremos aRb para denotar que (a, b) ∈ R. La
notación aRb se lee “a está R-relacionado con b”.
En ocasiones puede ser conveniente una representación gráfica del tipo

pues es visualmente muy simple y directa.

3.1 Operaciones con relaciones.

Puesto que las relaciones son subconjuntos de un producto cartesiano, las nociones de inter-
sección, unión y diferencia de dos relaciones se obtienen directamente a partir de las correspon-
dientes para conjuntos.

Definición 1. Dada R una relación de A en B, la relación inversa de R, que denotaremos

por R−1 , es la relación de B en A definida por

R−1 = {(b, a) ∈ B × A : (a, b) ∈ R}

Definición 2. Dadas dos relaciones R1 de A en B y R2 de B en C, la relación compuesta,

R1 ◦ R2 (o simplemente R1 R2 ) es una relación de A en C definida por

R1 ◦ R2 = {(a, c) ∈ A × C : ∃ b ∈ B con (a, b) ∈ R1 y (b, c) ∈ R2 }

La composición de relaciones es asociativa. Es decir, si R1 ⊆ A × B, R2 ⊆ B × C y

R3 ⊆ C × D, entonces R1 ◦ (R2 ◦ R3 ) = (R1 ◦ R2 ) ◦ R3 .
Pero en general, la composición de relaciones no es conmutativa.

Definición 3. Dados un conjunto A y una relación R en A se definen las potencias de R en

forma recursiva por:
a) R1 = R;
b) Rn+1 = R ◦ Rn para n ∈ ZZ+ .

Definición 4. Si R es una relación en A y B ⊆ A entonces, (B × B) ∩ R es una relación en B

que se denomina restricción de R a B, y se denota por R|B .

59
3.2 Propiedades de las relaciones binarias en A.
Definición 5. Sea R una relación en A. Decimos que:
a) R es reflexiva si: ∀ x ∈ A, (x, x) ∈ R
b) R es antirreflexiva si: ∀ x ∈ A, (x, x) ∈
/R
c) R es simétrica si: ∀ x, y ∈ A, (x, y) ∈ R =⇒ (y, x) ∈ R
d) R es antisimétrica si: ∀ x, y ∈ A, (x, y) ∈ R y (y, x) ∈ R =⇒ x = y
e) R es transitiva si: ∀ x, y, z ∈ A, (x, y) ∈ R y (y, z) ∈ R =⇒ (x, z) ∈ R

Cuidado con pensar que antirreflexiva es sinónimo de “no reflexiva”, o que antisimétrica
es sinónimo de “no simétrica”. Los siguientes ejemplos de relaciones binarias no vacı́as en
A = {1, 2, 3} muestran que estos conceptos no son coincidentes.

Reflexiva No reflexiva
Antirreflexiva No hay {(1, 2)}
No antirreflexiva {(1, 1), (2, 2), (3, 3)} {(1, 1)}

Simétrica No simétrica
Antisimétrica {(1, 1), (2, 2)} {(1, 1), (1, 2)}
No antisimétrica {(1, 2), (2, 1)} {(1, 2), (2, 1), (2, 3)}

Definición 6. Diremos que una relación R en un conjunto A es un orden parcial si R es

reflexiva, antisimétrica y transitiva. Un orden parcial estricto en A es una relación que
satisface las propiedades antirreflexiva y transitiva (por lo que la antisimétrica es verdadera por
vacuidad).

Ejemplo 1. Relaciones de orden:

a) En IR, la relación ≤ es un orden parcial y la relación < es un orden parcial estricto.

b) En P(U), la relación ⊆ es una relación de orden parcial.

c) En Z + , la relación de divisibilidad es un orden parcial. 4

Usualmente cuando se dice que una relación es un orden nos referimos a que es un orden parcial.
Si nos referimos a un orden parcial estricto, se especifica siempre.

Definición 7. Diremos que una relación R en un conjunto A es de equivalencia si R es

reflexiva, simétrica y transitiva.

Ejemplo 2. Relaciones de equivalencia:

a) La equivalencia lógica de proposiciones es una relación de equivalencia en el conjunto de

las proposiciones lógicas.

60
 b) Si U es una familia de conjuntos, la relación de equipotencia entre los elementos de U
(A ' B si y solo si existe f : A −→ B biyectiva) es de equivalencia.

c) La relación de congruencia módulo m es una relación de equivalencia en ZZ. Si m ∈ ZZ+

y a, b ∈ ZZ se dice que a es congruente con b módulo m, y se escribe a ≡ b mod m ó
también a ≡m b, si (a − b) es un múltiplo de m, es decir si ∃k ∈ ZZ tal que a − b = km.
4
Teorema 8. Sea R una relación en A y sea ∆ = {(x, x) : x ∈ A}. Entonces,
(1) R es reflexiva ⇐⇒ ∆ ⊆ R
(2) R es antirreflexiva ⇐⇒ R ∩ ∆ = ∅
(3) R es simétrica ⇐⇒ R = R−1
(4) R es antisimétrica ⇐⇒ R ∩ R−1 ⊆ ∆
(5) R es transitiva ⇐⇒ R2 ⊆ R.

3.3 Matrices y relaciones.

Muchas veces cuando trabajamos con relaciones definidas sobre un conjunto finito debemos
realizar cálculos tediosos a la hora de comprobar si verifica alguna de las propiedades. El uso del
ordenador nos evitará esto. Las matrices booleanas (matrices cuyos elementos son 0 o 1) nos
proporcionan una forma de representar una relación binaria, y es una herramienta adecuada para
su manipulación en un ordenador. Las operaciones boolenas, suma y producto, se definen en
las siguientes tablas:
+ 0 1 · 0 1
0 0 1 0 0 0
1 1 1 1 0 1
En esta sección solo consideramos relaciones definidas sobre conjuntos finitos.

Matriz de una relación

Sean A = {a1 , a2 , . . . , am } y B = {b1 , b2 , . . . , bn } y R una relación de A en B. La matriz
de R es una matriz booleana M de tamaño m × n donde

 1 si (ai , bj ) ∈ R
mij =
 0 si (ai , bj ) ∈
/R

Observar que si R es una relación en A y M es la matriz de R,entonces:

a) M = 0 si, y sólo si, R = ∅
b) M = I si, y sólo si, R = ∆
c) M = 1 (matriz con todos sus elementos iguales a 1) si, y sólo si, R = A × A

Operaciones con matrices booleanas

Si S y T son matrices booleanas m × n, las matrices S • T y S + T son matrices del mismo
tamaño m × n, definidas por

61
 (S • T )ij = sij · tij (· es el producto booleano)
(S + T )ij = sij + tij (+ es la suma boolena)
Si S y T son matrices booleanas de tamaño m × p y p × n respectivamente, el producto
booleano ST es una matriz de tamaño m × n tal que para cada i, j
p
X
(ST )ij = sik · tkj
k=1
Es decir, ST se define igual que el producto de matrices de números reales pero reemplazando
las operaciones suma y producto de números reales por la suma y producto lógico.

Matriz de la ∪, ∩, inversa y composición de relaciones

Si R1 y R2 son relaciones de A en B de matriz M1 y M2 respectivamente entonces,
- la matriz de la relación R1 ∪ R2 es M1 + M2 ,
- la matriz de la relación R1 ∩ R2 es M1 • M2 y
- la matriz de la relación R−1 es M t .
Si R1 ⊆ A × B y R2 ⊆ B × C y M1 y M2 son las matrices de R1 y R2 respectivamente
entonces, la matriz de la relación compuesta R1 ◦ R2 es M1 M2 .
Utilizando inducción es fácil probar que si M es la matriz de R, una relación binaria en A,
entonces, M n es la matriz de Rn para todo n ∈ ZZ+ .
Si S y T son matrices booleanas m × n diremos que S precede a T (o S es menor que
T ) y se escribe S  T, si, sij ≤ tij para todo 1 ≤ i ≤ m, 1 ≤ j ≤ n. Es evidente que si R1 y
R2 son relaciones de A en B con matrices M1 y M2 respectivamente, entonces R1 ⊆ R2 si, y
sólo si M1  M2 .
El siguiente resultado nos dice cómo reconocer las propiedades de una relación a través de
su matriz.

Proposición 9. Dados un conjunto A con |A| = n y una relación R en A, si M es la matriz

de R, se tiene:
(1) R es reflexiva ⇐⇒ In  M
(2) R es antirreflexiva ⇐⇒ M • In = 0
(3) R es simétrica ⇐⇒ M = M t
(4) R es antisimétrica ⇐⇒ M • M t  In
(5) R es transitiva ⇐⇒ M 2  M.

Observar: R es reflexiva si y sólo si las entradas en la diagonal de M (matriz de R) son todas

1; R es antirreflexiva si y sólo si las entradas en la diagonal de M son todas 0; y R es simétrica
si y sólo si su matriz es simétrica.

3.4 Relaciones de orden.

Si R es una relación de orden parcial en un conjunto A, se dice que el par (A, R) es un conjunto
parcialmente ordenado (c.p.o.).

62
Ejemplo 3.

a) La relación ≤, “ es menor o igual que”, en el conjunto IN, ZZ, Q o IR, hace que estos
conjuntos estén ordenados.

b) Para un universo dado U, la relación R en P(U) dada por (A, B) ∈ R si A ⊆ B para

cualesquiera A, B ⊆ U hace que (P(U), ⊆) sea un c.p.o. (Observar que en un c.p.o. existe
la posibilidad de que dos elementos no sean comparables.) 4

Cada orden parcial en A induce un orden parcial estricto y recı́procamente. Piénsese en ⊆ y

⊂ . Esto es:
- Si R es un orden parcial en A, la relación Re definida por (a, b) ∈ Re si y sólo si (a, b) ∈ R
y a 6= b, es un orden parcial estricto.
- Si Re es un orden parcial estricto en A, la relación R definida por aRb si y sólo si aRe b o
a = b, es un orden parcial en A.

Diagrama de Hasse
Es posible dibujar una diagrama que muestre de un vistazo una relación de orden en un
conjunto finito. Dado un orden parcial R en A, un diagrama de Hasse para R en A es
una figura que consta de puntos etiquetados por los elementos de A y de segmentos de recta
(aristas) uniendo dos puntos x e y, x 6= y, si xRy y no hay otro elemento z ∈ A tal que xRz
y zRy. Si se adopta el convenio de leer el diagrama de abajo arriba, no es necesario dirigir las
aristas.

Ejemplo 4. A continuación se muestra el diagrama de Hasse para el conjunto parcialmente

ordenado ({1, 2, 3, 4, 5, 6}, “divide a”):

4 r r6



r 3 r 5 r

2 
QQ 

Q 
r
Q 
Q
1

Elementos notables de un c.p.o.

4
Definición 10. Si (A, R) es un c.p.o. y B ⊆ A, se dice que x ∈ B es minimal de B si para
todo b ∈ B, b 6= x =⇒ b R
6 x, es decir si no existe b ∈ B (b 6= x) tal que bRx.
Un elemento y ∈ B es maximal de B si para todo b ∈ B, b 6= y =⇒ y R
6 b, es decir si no existe
b ∈ B (b 6= y) tal que yRb.

Definición 11. Si (A, R) es un c.p.o.y B ⊆ A, se dice que x ∈ B es un mı́nimo de B si xRb,

para todo b ∈ B. El elemento y ∈ B es un máximo de B si bRy para todo b ∈ B.

63
Definición 12. Sean (A, R) un c.p.o. y B ⊆ A. Un elemento x ∈ A es una cota inferior de
B si xRb para todo b ∈ B.
Decimos que y ∈ A es una cota superior de B si bRy, para todo b ∈ B.
Un elemento x ∈ A es un ı́nfimo de B (o extremo inferior), si es una cota inferior de B
y si para el resto de las cotas inferiores x0 de B, x0 Rx. De manera análoga, y ∈ A es un
supremo de B (o extremo superior), si es una cota superior de B y si para el resto de las
cotas superiores y 0 de B, yRy 0 . Esto es,

inf (B) = máximo (cotas inferiores(B))

sup(B) = mı́nimo (cotas superiores(B))

Ejemplo 5.

a) Elementos notables del c.p.o. ({1, 2, 3, 4, 5, 6}, “divide a”):

minimales = {1}, maximales = {4, 5, 6}, mı́nimo=1, no tiene máximo.

b) Con la relación de orden usual en IR, ≤:

i) Si A = IR y B = (0, 1], entonces B tiene ı́nfimo 0 y supremo 1. El máximo de B es 1,
pero no tiene mı́nimo. Observar que 0 ∈
/ B y 1 ∈ B.
√ √
ii) Si A = IR y B = {q ∈ Q : q 2 < 2}. Entonces B tiene ı́nfimo − 2 y supremo 2. No
tiene ni máximo, ni mı́nimo.
iii) Si A = Q y B = {q ∈ Q : q 2 < 2}. Entonces B no tiene ni ı́nfimo ni supremo.
Tampoco tiene máximo ni mı́nimo. 4

Teorema 13. Si (A, R) es un c.p.o. y B ⊆ A es finito, entonces B tiene elementos maximal y

minimal.

Para un c.p.o. es posible tener varios maximales y/o varios minimales. Sin embargo, no ocurre lo
mismo con los elementos máximo, mı́nimo, ı́nfimo y supremo como se recoge en los dos siguientes
teoremas.

Teorema 14. Sean (A, R) es un c.p.o. y B ⊆ A. Si B tiene máximo (o mı́nimo), éste es único.

Teorema 15. Sean (A, R) es un c.p.o. y B ⊆ A. Si B tiene supremo (o ı́nfimo), éste es único.

Definición 16. Un c.p.o. (A, R) es un retı́culo (o red o latix) si para cualesquiera x, y ∈ A

existen inf{x, y} y el sup{x, y}.

Ejemplo 6.

a) Si U =
6 ∅, (P(U), ⊆) es un retı́culo. Para cualesquiera A, B ⊆ U, inf(A, B) = A ∩ B y
sup(A, B) = A ∪ B.

b) (ZZ+ , “divide a”) es un retı́culo. Para cualesquiera a, b ∈ ZZ+ , inf{a, b} = m.c.d.(a, b) y

sup{a, b} = m.c.m.(a, b).

64
 c) ({1, 2, 3, 4, 5, 6}, “divide a”) no es un retı́culo.

d) (D ={divisores enteros positivos de 12}, “divide a”) es un retı́culo. 4

Teorema 17. Si (A, R) es un retı́culo con A finito, entonces (A, R) tiene máximo y mı́nimo.

Conjuntos totalmente ordenados

Definición 18. Si (A, R) es un c.p.o., se dice que (A, R) está totalmente ordenado o que es
una cadena, si para cualesquiera x, y ∈ A se cumple xRy o yRx. En este caso se dice que R
es un orden total en A.

Observar que si A es un orden total, dos elementos cualesquiera de A son comparables. En un

retı́culo esto no se cumple necesariamente. De hecho todo orden total es un retı́culo pero el
recı́proco no es cierto.

Ejemplo 7.

a) IR con el orden usual ≤ es una cadena. También lo son (IN, ≤) y (ZZ, ≤).

b) (P(U), ⊆) no es una cadena. Tampoco (ZZ+ , “divide a”).

c) Sean (A, R1 ) y (B, R2 ) dos c.p.o.s. Se define en A × B el orden producto, R, por

(a, b)R(a0 , b0 ) ⇐⇒ aR1 a0 y bR2 b0 .
Se define en A × B el orden lexicográfico (o de archivo), R, por
(a, b)R(a0 , b0 ) ⇐⇒ [a = a0 y bR2 b0 ] o [a 6= a0 y aR1 a0 ].
IN2 con el orden producto no es una cadena mientras que con el orden lexicográfico sı́ es
una cadena. En general, si (A, R1 ) y (B, R2 ) son cadenas y Rp es el orden producto
en A × B, entonces (A × B, Rp ) no es una cadena. Pero si Rd es el orden lexicográfico
entonces (A × B, Rd ) sı́ es una cadena.

d) Las listas de nombres en la guı́a telefónica o de palabras en un diccionario son cadenas con
el orden lexicográfico. 4

Clasificación topológica
Dado un orden parcial R en un conjunto finito A, siempre existe un orden total T en A tal
que R ⊆ T . El algoritmo que se da a continuación describe la forma de encontrarlo. La salida
del algoritmo será una sucesión (lista ordenada) de los elementos de A. Observar que si |A| = n,
cualquier sucesión (ai1 , ai2 , ai3 , . . . , ain ) con los n elementos de A, determina sin ambigüedad
un orden total en A.

Algoritmo de clasificación topológica:

Sea R un orden parcial sobre A con |A| = n y sea H su diagrama de Hasse.
Paso 1: Comenzar con T = () y con k = 1.

65
 Paso 2: Seleccionar un elemento minimal ak de la relación cuyo diagrama de Hasse es
H (el vértice ak de H es minimal si ninguna arista (implı́citamente dirigida)
de H termina en ak .)
Paso 3: Si k = n, el proceso termina con el orden total T que contiene a R.
Si k < n, añadir ak a la sucesión T ; eliminar de H el vértice ak y todas
las aristas que comiencen en ak ; llamar de nuevo H a este diagrama; hacer
k = k + 1 y regresar al Paso 2.

Definición 19. Se dice que el orden R en A no vacı́o es un buen orden, o que (A, R) está
bien ordenado, si cualquier subconjunto de A no vacı́o, con el orden inducido, admite mı́nimo.

Por ejemplo, IN y ZZ+ con el orden usual ≤ están bien ordenados. También lo está IN2 con el
orden lexicográfico. Sin embargo, (ZZ, ≤) no está bien ordenado. Tampoco están bien ordenados
Q, Q+ ni IR con el orden usual.

Proposición 20.
a) Todo conjunto bien ordenado es una cadena.
b) Toda cadena finita, está bien ordenada.

3.5 Relaciones de equivalencia.

El objetivo de esta sección es ver el papel que representan las particiones respecto a las relaciones
de equivalencia. Recordemos que si A es un conjunto, I un conjunto de ı́ndices y {Ai }i∈I una
familia de conjuntos con ı́ndices en I , decimos que P = {Ai : i ∈ I} es una partición de A si:
[
1) A = Ai , 2) Ai 6= ∅ para todo i ∈ I y 3) Ai ∩ Aj = ∅, para cualesquiera i, j ∈ I con i 6= j.
i∈I
Es decir, una partición de A es una colección de subconjuntos no vacı́os de A, disjuntos dos a
dos y cuya unión es A. A cada Ai se le llama bloque o celda de la partición P.

Definición 21. Sea R una relación de equivalencia en un conjunto A. Para cada x ∈ A defini-
mos la clase de equivalencia de x, denotada por [x], como
[x] = {y ∈ A : (y, x) ∈ R}.
Denotaremos por A/R al conjunto de todas las clases de equivalencia de A, es decir
A/R = {[x] : x ∈ A}.
A este conjunto se le llama conjunto cociente de A por R.

Proposición 22. Sea R una relación de equivalencia en A. Para x, y ∈ A se verifica:

a) x ∈ [x]
b) (x, y) ∈ R ⇐⇒ [x] = [y]
c) [x] ∩ [y] = ∅ o [x] = [y]

Teorema 23. Sea A un conjunto no vacı́o. Entonces,

a) Cualquier relación de equivalencia en A induce una partición en A.
b) Cualquier partición en A induce una relación de equivalencia en A.

66
 Una consecuencia que se obtiene de este teorema es que puede establecerse una función
biyectiva entre el conjunto de todas las relaciones de equivalencia en A, E(A), y el conjunto
(A). La función biyectiva es f : E(A) −→
Q Q
de todas las particiones de A, (A) dada por
f (R) = A/R = {[x] : x ∈ A}. Por este motivo se dice que E(A) y
Q
(A) son isomorfos.

Ahora estamos en condiciones de resolver la siguiente cuestión: Si A es un conjunto con

|A| = n, ¿cuántas relaciones en A son de equivalencia? Sabemos que el número de relaciones de
equivalencia en A debe coincidir con el de las particiones de A, puesto que ambos conjuntos son
isomorfos. Por otro lado observamos que una partición de A es una distribución de n objetos
distintos (los n elementos de A) en recipientes idénticos sin dejar ninguno vacı́o. Ası́, S(n, 1) =
n ¯o de particiones de A en 1 bloque, S(n, 2) = n ¯o de particiones de A en 2 bloques, etc. En
general para k = 1 . . . n
S(n, k) = n ¯o de particiones de A en k bloques.
n
X
Por tanto, el número de relaciones de equivalencia en A es S(n, k).
k=1

3.6 Cierres de relaciones.

En esta sección veremos que si R es una relación cualquiera en un conjunto A, siempre hay
relaciones reflexiva, simétrica o transitiva mı́nimas que contienen a R. Concluiremos que existe
la mı́nima relación de equivalencia que contiene a R y se especificará cómo encontrarla.

Definición 24. Llamaremos cierre reflexivo de una relación R, y lo denotaremos por r(R), a
la mı́nima relación reflexiva que contiene a R. Del mismo modo llamaremos cierre simétrico y
cierre transitivo de R y los denotaremos por s(R) y t(R) a las mı́nimas relaciones simétrica
y transitiva respectivamente que contiene a R.

Ejemplo 8. Hallemos los cierres reflexivo, simétrico y transitivo de la relación R en {1, 2, 3, 4}

dada por
R = {(1, 3), (1, 4), (2, 2), (3, 3), (4, 1)}.
- R no es reflexiva pero si añadimos los pares (1,1) y (4,4) obtenemos una relación reflexiva que
contiene a R. Es decir, r(R) = R ∪ {(1, 1), (4, 4)}.
- R no es simétrica. Añadiendo el par (3, 1) a R obtenemos s(R).
- R no es transitiva. t(R) = R ∪ {(1, 1), (4, 3), (4, 4)}
¿Alguna de las relaciones obtenidas, r(R), s(R) o t(R), es de equivalencia? 4

Proposición 25. Sea R una relación en A. Entonces

a) R es reflexiva ⇐⇒ r(R) = R
b) R es simétrica ⇐⇒ s(R) = R
c) R es transitiva ⇐⇒ t(R) = R
d) rr(R) = r(R), ss(R) = s(R) y tt(R) = t(R)

67
 El siguiente teorema garantiza la existencia de los cierres reflexivo, simétrico y transitivo al
dar descripciones explı́citas para ellos.

Teorema 26. Si R es una relación en A y ∆ = {(a, a) : a ∈ A}, como es usual, entonces

∞
[
1) r(R) = R ∪ ∆; 2) s(R) = R ∪ R−1 3) t(R) = Rk
k=1

n
[
Teorema 27. Si R es una relación en A y |A| = n, entonces t(R) = Rk
k=1

Si R es una relación en A con |A| = n y si M es la matriz de R entonces, las matrices de

r(R), s(R) y t(R) que denotaremos por r(M ), s(M ) y t(M ) respectivamente, son:
n
X
r(M ) = M + I; s(M ) = M + M t t(M ) = Mk
k=1
Estas igualdades nos dan algoritmos para calcular los cierres de una relación. En el tema de
Grafos, se verán algoritmos más eficientes para calcular el cierre transitivo.

Proposición 28.
a) Si R es reflexiva, también lo son s(R) y t(R).
b) Si R es simétrica, también lo son r(R) y t(R).
c) Si R es transitiva, también lo es r(R).

De esta proposición se deduce que el cierre reflexivo es conmutativo con cualquiera de los otros
dos. Esto es sr(R) = rs(R) y tr(R) = rt(R).
Sin embargo, esto no se cumple para los cierres simétrico y transitivo. Es cierto que al
aplicar el cierre transitivo a una relación simétrica no se destruye la simetrı́a, por lo que siempre
se verifica que st(R) ⊆ ts(R). Pero al aplicar el cierre simétrico a una relación transitiva sı́
puede destruirse la transitividad. Ası́ ocurre para la relación R = {(1, 1), (2, 1), (3, 1), (3, 3)}
definida sobre {1, 2, 3}.

Con todo lo anterior, estamos en condiciones de concluir con el resultado principal de esta
sección.

Teorema 29. Para cualquier relación R en A, tsr(R) es la mı́nima relación de equivalencia

que contiene a R.

3.7 El retı́culo de las particiones.

Consideremos E(A), el conjunto de todas las relaciones de equivalencia en un conjunto A.
E(A), está parcialmente ordenado por la relación de inclusión ¿Tiene mı́nimo y máximo? ¿Es
un retı́culo? Para responder a la primera pregunta basta observar que A × A y ∆ son relaciones
de equivalencia en A. Además ∆ ⊆ R ⊆ A×A para cualquier relación R de E(A). Por tanto, las

68
relaciones A × A y ∆ son respectivamente el máximo y el mı́nimo de E(A). De hecho (E(A), ⊆)
es un retı́culo pues para cualesquiera R1 , R2 de E(A),
inf(R1 , R2 ) = R1 ∩ R2
sup(R1 , R2 ) = t(R1 ∪ R2 )
Efectivamente, R1 ∩ R2 es el mayor conjunto contenido en R1 y en R2 ; además si R1
y R2 son relaciones de equivalencia R1 ∩ R2 también lo es; por tanto la máxima relación de
equivalencia contenida en R1 y en R2 es precisamente R1 ∩ R2 .
Para obtener el supremo de R1 y R2 , sabemos que R1 ∪ R2 es el menor conjunto que
contiene a ambas, sin embargo aunque R1 y R2 sean de equivalencia, R1 ∪ R2 no tiene por
qué serlo. Pero según se ha visto en la sección anterior, la mı́nima relación de equivalencia que
contiene a R1 ∪ R2 es tsr(R1 ∪ R2 ). Es más, como la unión conserva las propiedades reflexiva
y simétrica se tiene que tsr(R1 ∪ R2 ) = t(R1 ∪ R2 ).

(A), el conjunto de todas las particiones de A. Puesto que E(A) y

Q
Consideremos ahora
Q
(A) son isomorfos se tiene que afirmaciones sobre relaciones de equivalencia en A corresponden
a afirmaciones sobre particiones en A y, recı́procamente, podemos traducir afirmaciones sobre
particiones a afirmaciones sobre relaciones. Ası́ pues, hay una estructura correspondiente de
Q Q
retı́culo en (A). Pero, ¿cuál es la relación de orden que hace que (A) sea un retı́culo? Se
describe a continuación.
Sean P1 y P2 particiones de A correspondientes a las relaciones R1 y R2 . Decimos que P1
es un refinamiento de P2 (o que P1 es más fina que P2 ) y escribimos P1 ≤ P2 si y sólo si
R1 ⊆ R2 .
Nótese que: R1 ⊆ R2 ⇐⇒ cada dos elementos relacionados por R1 están relacionados por
R2 ⇐⇒ cada dos elementos en una clase de R1 están en la misma clase de R2 ⇐⇒ cada bloque
de P1 es un subconjunto de algún bloque de P2 .
Q
La relación de refinamiento que se acaba de definir sobre (A) es un orden parcial. Es más
el c.p.o. ( (A), ≤) es un retı́culo y se tiene que:
Q

inf(P1 , P2 ) = partición correspondiente a la relación de equivalencia R1 ∩ R2

sup(P1 , P2 ) = partición correspondiente a la relación de equivalencia t(R1 ∪ R2 ).
El máximo de ( (A), ≤) es la partición con un único bloque que es el conjunto A y el mı́nimo
Q

es la partición con bloques de un sólo elemento para cada elemento de A.

3.8 Problemas.
3.8.1 Sean A, B ⊆ U, R1 y R2 relaciones de A en B probar que:

a) (R1 ∪ R2 )−1 = R−1 −1

1 ∪ R2

b) (R1 ∩ R2 )−1 = R−1 −1

1 ∩ R2

c) (R−1
1 )
−1 = R
1

d) R1 ⊆ R2 =⇒ R−1 −1
1 ⊆ R2

69
3.8.2 Para conjuntos A, B y C y dadas las relaciones R1 , R2 ⊆ A × B y R3 , R4 ⊆ B × C,
probar que:

a) R1 ◦ (R3 ∪ R4 ) = (R1 ◦ R3 ) ∪ (R1 ◦ R4 )

b) R1 ◦ (R3 ∩ R4 ) ⊆ (R1 ◦ R3 ) ∩ (R1 ◦ R4 )
c) Dar un ejemplo en que R1 ◦ (R3 ∩ R4 ) 6= (R1 ◦ R3 ) ∩ (R1 ◦ R4 )
d) R1 ⊆ R2 y R3 ⊆ R4 =⇒ R1 ◦ R3 ⊆ R2 ◦ R4

3.8.3 Demostrar que si R1 ⊆ A × B y R2 ⊆ B × C entonces, (R1 ◦ R2 )−1 = R−1 −1

2 ◦ R1

3.8.4 Si R1 = {(1, 1), (2, 1), (3, 3), (3, 4)} y R2 = {(1, 3), (1, 4), (3, 4), (4, 4)} son relaciones
binarias sobre A = {1, 2, 3, 4}, hallar la relación compuesta R1 ◦ R2 ¿Qué propiedades
verifica R1 ◦ R2 ? ¿Cuáles de estas propiedades no las verifican ni R1 ni R2 ?

3.8.5 Para cada una de las relaciones siguientes determinar si la relación es reflexiva, simétrica,
antisimétrica o transitiva. ¿Hay alguna relación de equivalencia? ¿y algún orden parcial?

a) La relación de divisibilidad en ZZ∗ definida por: a|b ⇐⇒ ∃k ∈ ZZ, b = ak. (a|b se

lee “a divide a b”).
b) R ⊆ ZZ+ × ZZ+ , donde aRb ⇐⇒ a|b.
c) Dados un universo U y un conjunto fijo F ⊆ U, se define R en P(U) por:
ARB ⇐⇒ A ∩ F = B ∩ F, para cualesquiera A, B ⊆ U.
d) En el conjunto A de todas las rectas de IR2 , se define la relación R de perpendi-
cularidad (paralelismo) por: r1 Rr2 ⇐⇒ r1 es perpendicular (paralela) a r2 .
e) R es la relación en ZZ, donde xRy ⇐⇒ x + y es par (impar).
f) R es la relación en ZZ, donde xRy ⇐⇒ x − y es par (impar).
g) R es la relación en ZZ × ZZ, donde (a, b) R (c, d) ⇐⇒ a ≤ c.

3.8.6 Sean R1 , R2 relaciones en un conjunto A. Demostrar o refutar:

a) R1 , R2 reflexivas =⇒ R1 ∩ R2 reflexiva.
b) Responder al apartado a) pero sustituyendo reflexiva por
1: simétrica; 2: antisimétrica y 3: transitiva.
c) Repetir los apartados anteriores sustituyendo ∩ por ∪.

3.8.7 Sean A un conjunto e I un conjunto de ı́ndices, donde para cada i ∈ I, Ri es una

relación en A. Demostrar o refutar las siguientes afirmaciones:
[
a) Ri es reflexiva ⇐⇒ cada Ri es reflexiva.
i∈I

70
 \
b) Ri es reflexiva ⇐⇒ cada Ri es reflexiva.
i∈I
c) Responder a los apartados anteriores sustituyendo reflexiva por 1: simétrica; 2:
antisimétrica y 3: transitiva.

3.8.8 Sean R1 y R2 relaciones en A. Demostrar o refutar que:

a) Si R1 y R2 son reflexivas, entonces R1 ◦ R2 es reflexiva.

b) Si R1 y R2 son simétricas, entonces R1 ◦ R2 es simétrica.
c) Si R1 y R2 son transitivas, entonces R1 ◦ R2 es transitiva.

3.8.9 Determinar cuáles de las siguientes proposiciones son verdaderas y cuáles falsas. Si es
falsa, dar un contraejemplo.

a) Si R1 y R2 son relaciones en A y R1 ⊆ R2 , entonces

R1 es reflexiva (simétrica), (antisimétrica), (transitiva) =⇒
R2 es reflexiva (simétrica), (antisimétrica), (transitiva).
b) Si R1 y R2 son relaciones en A y R1 ⊆ R2 , entonces
R2 es reflexiva (simétrica), (antisimétrica), (transitiva) =⇒
R1 es reflexiva (simétrica), (antisimétrica), (transitiva).

3.8.10 ¿Cuál es el fallo en el siguiente argumento?

Si R es una relación en A simétrica y transitiva, entonces R es reflexiva.

Demostración: Sea (x, y) ∈ R. Por la propiedad simétrica (y, x) ∈ R. En-
tonces como (x, y), (y, x) ∈ R resulta, por la propiedad transitiva, que
(x, x) ∈ R. Por tanto R es reflexiva.

3.8.11 Si R es una relación de A en B,

a) Demostrar que R ◦ R−1 y R−1 ◦ R son relaciones simétricas en A y en B respec-

tivamente.
b) ¿Cuándo será R ◦ R−1 reflexiva?

3.8.12 Para las siguientes afirmaciones sobre relaciones en un conjunto A, donde |A| = n,
razonar si la proposición es verdadera o falsa.

a) Si R es una relación reflexiva en A, entonces |R| ≥ n.

b) Si R es una relación en A y |R| ≥ n, entonces R es reflexiva.
c) Si R es una relación de equivalencia en A, entonces n ≤ |R| ≤ n2 .

71
3.8.13 Si A es un conjunto finito con |A| = n, demostrar que:
2
- el número de relaciones binarias en A es 2n .
2 −n
- el número de relaciones binarias en A reflexivas es 2n .
2
- el número de relaciones binarias en A simétricas es 2n 2(n −n)/2 .
2 −n)/2
- el número de relaciones binarias en A antisimétricas es 2n 3(n .
 
1 0 1 1
 
 0 1 0 1  ¿Cuántas matrices booleanas T cumplen S ≤ T ?
3.8.14 Si S =  

1 0 0 0

3.8.15 Dibujar los diagramas de Hasse de los c.p.o.s (A, R) siguientes:

a) A = {1, 2, 3, 4, 5, 6}, R = “divide a”
b) A = P ({a, b, c}), R = “⊆”
c) A = {2, 3, 5, 7}, R = “divide a”.

3.8.16 Dibuja el diagrama de Hasse de la relación de orden sobre A = {1, 2, 3, 4, 5, 6} dada por
R = {(1, 2), (1, 4), (1, 5), (1, 6), (2, 5), (4, 5), (6, 2), (6, 4), (6, 5} ∪ ∆

3.8.17 Para A = {a, b, c, d, e, v, w, x, y, z} considerar el conjunto parcialmente ordenado (A, R),

cuyo diagrama de Hasse es
z
q
@
@
xq wq @q y
@
@
vq
@ q e
@
@
cq bq @q d
@
@
@q
a

Determinar el ı́nfimo y el supremo de los siguientes conjuntos:

a) {b, c} b) {b, w} c) {e, x} d) {c, b}
e) {d, x} f) {c, e} g) {a, v}
¿Es (A, R) un retı́culo? ¿Hay elementos maximal, minimal, máximo o mı́nimo?

3.8.18 Sea R una relación en A y B ⊆ A. Si (A, R) es un conjunto parcialmente ordenado,

pero R no es un orden total, y ∅ 6= B 6= A, ¿se concluye que (B, R|B ) es un conjunto
parcialmente ordenado, pero no totalmente ordenado?

3.8.19 Se considera la relación de divisibilidad en A = {2, 3, 4, 5, 6, 7, 10, 20, 42, 84}

a) Dibujar su diagrama de Hasse.

b) Hallar A1 ⊆ A con |A1 | = 5, para que la relación restringida a A1 sea un retı́culo.

72
3.8.20 Sean (A, R1 ) y (B, R2 ) dos conjuntos parcialmente ordenados. Se define en A × B la
relación R por
(a, b) R (a0 , b0 ) si y solo si a R1 a0 y b R2 b0

a) Demostrar que R es una relación de orden.

b) Sea A = B = {a, b, c} y R1 = R2 el orden en A dado por el diagrama de Hasse
q c

q b

q a

Dar el diagrama de Hasse de (A × B, R). ¿Es A × B un retı́culo? ¿Es A × B

totalmente ordenado?

3.8.21 A continuación se muestra el diagrama de Hasse para el conjunto parcialmente ordenado

(A, R) con A = {a, b, c, d, e}
eq

qd
HH
q 
b  HH q c
HH 
HHq 
a
a) Determinar la matriz de la relación asociada a R.
b) Clasificar topológicamente el conjunto parcialmente ordenado (A, R).

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

a) Verificar que (A, R) está parcialmente ordenado y dibujar su diagrama de Hasse.

b) Clasificar topológicamente (A, R).

3.8.23 En el Centro de Cálculo Marı́a tiene que procesar 10 programas que, debido a las priori-
dades, están restringidos por las siguientes condiciones: a) 10 > 8, 3; b) 8 > 7; c) 7 > 5;
d) 3 > 9, 6; e) 6 > 4, 1; f) 9 > 4, 5; g) 4, 5, 1 > 2; donde, por ejemplo, 10 > 8, 3 significa
que el programa número 10 debe ejecutarse antes que los programas 8 y 3.

a) Dibujar el diagrama de Hasse de la relación ”ejecutar antes” en el conjunto de los

10 programas.
b) Determinar un orden para ejecutar secuencialmente los 10 programas cumpliendo
las prioridades.

73
3.8.24 Si M es la matriz de la relación R en A, con |A| = n y (A, R) es un orden total,
¿cuántos 1 aparecen en M ?

3.8.25 Sea f : A −→ IR una función donde A es un conjunto no vacı́o cualquiera. Y sea S la

relación binaria en A definida por aSb ⇐⇒ f (a) ≤ f (b). Demostrar que S es un orden
si y solo si f es inyectiva.

3.8.26 Para cada una de las relaciones siguientes determinar si la relación es reflexiva, simétrica,
antisimétrica o transitiva. ¿Hay alguna relación de equivalencia? ¿Y algún orden parcial?
Para aquellas que sean de equivalencia, describir la partición originada por la relación.

a) R es la relación en ZZ, donde aRb ⇐⇒ 7|(a − b)

b) R es la relación en Q, donde aRb ⇐⇒ |a − b| < 1
c) R es la relación en Q, donde aRb ⇐⇒ (a − b) ∈ ZZ.

3.8.27 Considerar (ZZ, ≡p ), es decir la relación de congruencia módulo p en ZZ. Para p = 3

hallar las clases [0], [1], [2], [3], [4], . . . ¿Quién es el conjunto cociente ZZ/ ≡3 ?
+
Generalizar para cualquier p ∈ ZZ .

3.8.28 Sea R la relación de equivalencia en ZZ, dada por xRy si y sólo si x − y es par. Hallar
las clases de equivalencia [-3] y [2]. Hallar el conjunto cociente ZZ/R.

3.8.29 Dar una partición P = {Ai }i∈{1,2,3,4} del conjunto A = {n ∈ IN : 1 ≤ n ≤ 10} tal
que para cada i 6= j |Ai | =
6 |Aj | y para cada i los elementos de Ai sean de la misma
paridad. Dar la matriz de la relación de equivalencia asociada a la partición P restringida
a B = {1, 3, 5, 7, 9}.

3.8.30 Se define en IR2 la relación R por (x1 , y1 )R(x2 , y2 ) ⇐⇒ x1 = x2 .

a) Verificar que R es una relación de equivalencia en IR2 .

b) Describir geométricamente las clases de equivalencia y la partición de IR2 originada
por R.

3.8.31 Sea A = {1, 2, 3, 4, 5} y R la relación en A × A definida por

(x1 , y1 )R(x2 , y2 ) ⇐⇒ x1 + y1 = x2 + y2

a) Verificar que R es una relación de equivalencia en A × A.

b) Determinar las clases de equivalencia [(1,3)], [(2,4)] y [(1,1)].
c) Determinar la partición de A × A originada por R.

74
3.8.32 Sea f : A −→ B una función. Se considera la relación R definida en A por
aRb ⇐⇒ f (a) = f (b) a, b ∈ A

a) Probar que es de equivalencia.

b) Obtener las clases de equivalencia para cada una de las funciones de IR en IR
siguientes:
i) f (x) = sen x
ii) g(x) = x2
c) ¿Cuál es el cardinal de las clases de equivalencia en ambos casos?
d) ¿Cuál es el cardinal de los conjuntos cociente en ambos casos?

3.8.33 Si |A| = 30 y la relación de equivalencia R en A descompone A en las clases de

equivalencia A1 , A2 , A3 con |A1 | = |A2 | = |A3 |, ¿cuál es el valor de |R|?

3.8.34 Sea la relación R = {(1, 2), (3, 3)} en {1, 2, 3}.

a) Encontrar las matrices de r(R), s(R), rs(R), sr(R) y tsr(R).

b) Dar las clases de equivalencia de tsr(R).

3.8.35 Sea R la relación en ZZ+ dada por mRn si y sólo si m < n. Encontrar o describir r(R),
rs(R), sr(R), tsr(R), t(R) y st(R).

3.8.36 La Orden Fraternal de los Ermitaños Hostiles (O.F.E.H.) es una organización interesante.
Los ermitaños se conocen a sı́ mismos. Cada uno conoce al Gran Ermitaño (GE), pero
ni él ni ninguno de los otros miembros conoce a otro miembro. Definimos la relación R
en la O.F.E.H. por xRy ⇔ x conoce a y . Determinar s(t(R)) y t(s(R)) y comparar.

3.8.37 Sea R una relación binaria en ZZ+ definida por

xRy ⇐⇒ ∃ p ≥ 2 primo tal que p | x ∧ p | y
es decir, dos enteros están R−relacionados si y sólo si tienen algún divisor primo común.

a) ¿Qué propiedades verifica R? Razona tu respuesta.

b) Da la mı́nima relación de equivalencia que contiene a R.
c) Si ahora restringimos la relación R al conjunto A = {2, 3, 4, 5, 6, 7, 8, 9}, obtén la
partición asociada a la mı́nima relación de equivalencia que la contiene.

3.8.38 Sean A = {1, 2, 3, 4, 5, 6, 7, 8} y R1 y R2 relaciones de equivalencia en A dadas por:

xR1 y ⇐⇒ x ≡ y mod 5
R2 la relación originada por la partición {{1, 3, 5}, {4, 6}, {7, 8}, {2}}

75
 Hallar la matriz de R1 ∪ R2 y la matriz de t(R1 ∪ R2 ). ¿Es R1 ∪ R2 una relación de
equivalencia? ¿Y t(R1 ∪ R2 )?

3.8.39 Se tienen 4 canicas amarillas pequeñas, 3 azules medianas, 2 blancas medianas y una
amarilla grande. Dar las matrices asociadas a las relaciones R1 : tener el mismo color ;
R2 : tener el mismo tamaño; R1 ∩ R2 ; R1 ∪ R2 y t(R1 ∪ R2 ).

3.8.40 Se tienen 4 canicas amarillas pequeñas, 3 azules medianas, 2 blancas medianas, 1 amarilla
grande y 1 azul grande. Dar las matrices asociadas a las relaciones R1 : tener el mismo
color ; R2 : tener el mismo tamaño; R1 ∩ R2 ; R1 ∪ R2 y t(R1 ∪ R2 ).

3.8.41 Para A = {1, 2, 3, 4, 5}, se dan las siguientes particiones:

P1 : {{1, 2}, {3, 4, 5}}; P2 : {{1, 2}, {3, 4}, {5}};

P3 : {{1}, {2}, {3, 4, 5}}; P4 : {{1, 2}, {3}, {4}, {5}}

Dibujar el diagrama de Hasse para C = {Pi , 1 ≤ i ≤ 4} donde C está parcialmente

ordenado por la relación de refinamiento.

3.8.42 Considerar el retı́culo de las particiones en el conjunto A = {1, 2, 3, 4}. Hallar el ı́nfimo
y el supremo de las particiones P1 : {{1}, {2, 3}, {4}} y P2 : {{1, 2}, {3}, {4}}.

3.8.43 Sea el conjunto A = {3, 5, 6, 9, 10, 27} parcialmente ordenado por la relación de divisi-
bilidad R. Se pide:

a) Dibujar el diagrama de Hasse de (A, R).

b) Encontrar, si existen, los maximales, minimales, máximo y mı́nimo.
c) ¿Existen máximo, mı́nimo, supremo e ı́nfimo de B={3, 6, 9, 27}?
d) Escribir la matriz de R, de s(R) y de ts(R). Justificar si las relaciones resultantes
son o no relaciones de equivalencia. En caso afirmativo dar la partición asociada.
e) Dadas las particiones P1 y P2 del conjunto A,
P1 : {{3, 6, 9, 27}, {5, 10}} y P2 : {{3}, {6, 9}, {27, 5}, {10}}
hallar las matrices de las relaciones de equivalencia asociadas a las particiones P1 ,
P2 , sup(P1 , P2 ) e inf(P1 , P2 ).

3.8.44 Sea A= {1, 2, 3, 4, 5, 6}

a) Si R1 es la relación de equivalencia en A : xR1 y si, y sólo si, x − y es par, describir

la partición asociada P1 y la matriz de la relación.
b) Dar la relación restringida R1 |{4, 5, 6}.
c) Si R2 es la relación asociada a la partición {{1, 3}, {2, 4}, {5, 6}}, escribir su
matriz.

76
 d) Dar la matriz de la relación inf(R1 , R2 ).
e) Obtener las matrices de las relaciones R1 ∪ R2 y sup(R1 , R2 ).

3.8.45 Considerar el conjunto C de todas las cadenas formadas con los sı́mbolos {0, 1, . . . , 9}
que tienen entre 1 y 5 caracteres. Ejemplos: 1, 09, 8784. Diremos que dos cadenas c1
y c2 están R∗ relacionadas si y sólo si cada una tiene al menos tres sı́mbolos y además
coinciden en sus tres primeros caracteres.

a) Probar que esta relación R∗ no constituye una relación de equivalencia.

b) Dar la mı́nima relación de equivalencia R que contiene a R∗ ¿Qué tipo de cierre
es?
c) Describir [112]R y [8]R y calcular sus cardinales. Calcular, explicándolo, el cardinal
del conjunto cociente.
d) Considerar en C , la relación ∆ = {(c, c) | c ∈ C}. ¿Es una relación de orden?
¿Tiene elementos minimales?
e) Dar una relación de orden en C que tenga todos sus elementos minimales menos
dos y todos sus elementos maximales menos dos. Hacer un esbozo de su diagrama
de Hasse.
f) Tanto si se ha construido la relación pedida en el apartado anterior como si no,
razonar por qué no podrı́a ser esa relación un retı́culo.

Bibliografı́a:

– Grimaldi, Ch.R.B. (1997). “Matemáticas Discretas y Combinatoria”, 3a edición.

Ed. Addison-Wesley Iberoamericana. Capı́tulo 7.

– Rosen, K.H “Matemática Discreta y sus aplicaciones”. Ed. McGraw-Hill, 2004. Capı́tulo 7.

– Ross, K.A.-Wright, R.B. (1990). “Matemáticas Discretas”.

Ed. Prentice-Hall Hispanoamericana. Capı́tulo 7.

77