Soluciones a los ejercicios

Nota importante: es imprescindible intentar realizar los ejercicios antes de mirar

sus soluciones.

PROBLEMA 1:
Sea el conjunto A = {2, 3, 4, 6, 12, 15, 24, 90, 180, 360} y la relación de divisibilidad
aRb ⇐⇒ a | b .
Teniendo en cuenta que el diagrama de Hasse del conjunto ordenado (A, | ) que se muestra en
la figura.
(a) Encontrar (si existen) los elementos maximales, minimales, máximo y mínimo de A.
(b) Dado el subconjunto B = {2, 3, 4, 6, 12}, encontrar (si existen) los conjuntos mayorante y
minorante y el supremo e ínfimo de B.

Solución:
a) El único elemento maximal de A es 360, luego, al tratarse de un conjunto finito, máx(A) =
360. Los elementos minimales de A son {2, 3} y por tanto no existe mı́n(A).
b) El conjunto mayorante de B es mayor(B) = {12, 24, 180, 360}, luego sup(B) = 12. El
conjunto minorante de B es minor(B) = ∅, luego no existe ı́nf(B).

PROBLEMA 2:
Considérese la relación de orden parcial ⪯ definida en el conjunto D de los divisores positivos
de 84, excluyendo el 1, mediante
a ⪯ b ⇔ a divide a b .
1
 1. Dibujar el diagrama de Hasse del orden parcial (D, ⪯).
2. Dar, si existen, los elementos maximales y minimales, así como el máximo y mínimo de
(D, ⪯).
3. Dar, si existen, el conjunto de cotas superiores, cotas inferiores, supremo e ínfimo en
(D, ⪯) del conjunto B = {2, 3, 6, 28} ⊂ D.
Solución:
1) Es trivial enumerar los elementos que forman parte del conjunto D. En concreto
D = {2, 3, 7, 4, 6, 14, 21, 12, 28, 42, 84} .
El diagrama de Hasse asociado al conjunto parcialmente ordenado (D, ⪯) es

2) Trivialmente 84 es maximal y máximo; 2, 3, 7 son minimales y no hay mínimo.

3) El conjunto de las cotas superiores de B es {84} por lo que 84 es el supremo. El conjunto
de las cotas inferiores de B es vacío por lo que no hay ínfimo.
PROBLEMA 3:
Considérese la relación de orden parcial ⪯ definida en el conjunto D de los divisores positivos
de 36 , excluyendo el 1, mediante
a ⪯ b ⇔ a divide a b .
1. Dibujar el diagrama de Hasse del orden parcial (D, ⪯).
2. Dar, si existen, los elementos maximales y minimales, así como el máximo y mínimo de
(D, ⪯).
Solución:

Maximales: 36. Mimales: 2 y 3. Máximo: 36.

No existe mínimo.
PROBLEMA 4:
Considérese la relación de orden parcial ⪯ definida en el conjunto D de los divisores positivos
de 24 , excluyendo el 1, mediante

a ⪯ b ⇔ a divide a b .

1. Dibujar el diagrama de Hasse del orden parcial (D, ⪯).

2. Dar, si existen, los elementos maximales y minimales, así como el máximo y mínimo de
(D, ⪯).

Solución:

Maximales: 24. Minimales; 2 y 3. Máximo: 24.

No existe mínimo.

PROBLEMA 5:
Considérese la relación de orden parcial ⪯ definida en el conjunto D de los divisores positivos
de 40 , excluyendo el 1, mediante

a ⪯ b ⇔ a divide a b .

1. Dibujar el diagrama de Hasse del orden parcial (D, ⪯).

2. Dar, si existen, los elementos maximales y minimales, así como el máximo y mínimo de
(D, ⪯).

Solución:

Maximales: 40. Minimales 2 y 5. Máximo: 40.

No existe mínimo.
PROBLEMA 6:
Sea R la relación en R3 definida como

(a1 , a2 , a3 ) R (b1 , b2 , b3 ) ⇔ a21 + a22 + a23 = b21 + b22 + b23 .

Demostrar que R es de equivalencia y encontrar las clases de equivalencia y el conjunto cociente.

Solución:
Para demostrar que R es una relación de equivalencia hay que demostrar que es reflexiva,
simétrica y transitiva. Definamos la función f (⃗x) = f (x1 , x2 , x3 ) = x21 + x22 + x23 , entonces
⃗a R ⃗b ⇔ f (⃗a) = f (a1 , a2 , a3 ) = f (b1 , b2 , b3 ) = f (⃗b). Esta observación simplifica el razonamien-
to:

Reflexiva: f (⃗a) = f (⃗a), luego ⃗aR⃗a.

Simétrica: Si ⃗aR⃗b, entonces f (⃗a) = f (⃗b), y por tanto f (⃗b) = f (⃗a) ⇒ ⃗bR⃗a.

Transitiva: Si ⃗aR⃗b y ⃗bR⃗c, entonces f (⃗a) = f (⃗b) = f (⃗c). Luego, ⃗aR⃗c.

Dado un cierto ⃗a ∈ R3 se tiene que

f (a1 , a2 , a3 ) = a21 + a22 + a23 = A2 ≥ 0 .

La clase de equivalencia que contiene al vector ⃗a estará formada por todos aquellos puntos ⃗b ∈ R3
que satisfagan f (⃗b) = A2 . Resulta entonces evidente que las clases de equivalencia vienen dadas
por superficies esféricas en R3 parametrizadas por el valor de su radio A ≥ 0. Obviamente, la
intersección de dos esferas de distinto radio es vacía. Además, es posible representar cada una
de las clases de equivalencia usando el único punto en el que el semi-eje positivo x ≥ 0 corta a
la correspondiente esfera. De este modo, los elementos del conjunto cociente son de la forma

[(A, 0, 0)]R = {(a1 , a2 , a3 ) ∈ R3 | a21 + a22 + a23 = A2 } .

y se tiene que
R3 /R = {[(A, 0, 0)]R | A ∈ R+ } .

PROBLEMA 7:
Sea el conjunto V = {x | 1 ≤ x ≤ 20} ⊂ N. Sea el producto cartesiano V × V y sobre él
definimos la siguiente relación

(x, y) R (a, b) ⇔ x + b = y + a .

1. Demostrar que es una relación de equivalencia.

2. Calcular las clases de equivalencia. ¿Cuál es la clase que tiene mayor número de elementos?
¿Cuál es la clase que tiene menor número de elementos?

3. Calcular el conjunto cociente (V × V )/R y decir su número de elementos.

Solución:
1) R es una relación de equivalencia porque es de la forma (x, y)R(a, b) si y sólo si f (x, y) =
f (a, b) con f (x, y) = x−y. La demostración detallada de este punto se encuentra en el problema
1 de este documento.
2) Las clases de equivalencia son de la forma x − y = constante. La constante etiqueta las clases
de equivalencia y puede tomar valores entre −19 y 19. Por ejemplo la clase de equivalencia del
(1, 1) corresponde a tomar dicha constante igual a cero y contiene a los elementos

[(1, 1)]R = {(x, x) | 1 ≤ x ≤ 20} .

En general podemos escribir las 19 · 2 + 1 = 39 clases de equivalencia de la siguiente manera:

[(x, 1)]R = {(x + a, 1 + a) | 0 ≤ a ≤ 20 − x} , 1 ≤ x ≤ 20 ,

[(1, x)]R = {(1 + a, x + a) | 0 ≤ a ≤ 20 − x} , 2 ≤ x ≤ 20 .

En la segunda línea hemos suprimido el caso x = 1, al haberlo tenido en cuenta en la primera

línea.
El número de elementos de cada clase es

|[(x, 1)]R | = 21 − x , 1 ≤ x ≤ 20 ,
|[(1, x)]R | = 21 − x , 2 ≤ x ≤ 20 .

Luego la clase con mayor número de elementos será la [(1, 1)]R que tiene 20 elementos. Las
clases con menor número de elementos serán [(1, 20)]R y [(20, 1)]R con un sólo elemento.
3) El conjunto cociente (V × V )/R tendrá 39 elementos y será igual a

(V × V )/R = {[(x, 1)]R | 1 ≤ x ≤ 20} ∪ {[(1, x)]R | 2 ≤ x ≤ 20} .

PROBLEMA 8:
Considera la siguiente relación definida en N:

xRy ⇔ ∃ k ∈ Z+ : y = 2k x .

(a) Demuestra que (N, R) es un conjunto parcialmente ordenado.

(b) Sea X = {2, 3, 4, 5, 6, 8, 10}. Dibuja el diagrama de Hasse de (X, R).

(c) Encuentra, si existen, el máximo, el mínimo, los elementos maximales y minimales y las
cotas superiores e inferiores del conjunto X ⊂ N.

Solución:
a) La relación será una relación de orden si es reflexiva, antisimétrica y transitiva. La reflexividad
de R se sigue directamente de la igualdad x = 2k x, valida para k = 0 ∈ Z+ .
Para demostrar que la relación satisface la propiedad antisimétrica debemos comprobar que si
se cumple que xRy e yRx entonces necesariamente se sigue que x = y. En este punto es crucial
darse cuenta de que la antisimetría de la relación es consecuencia de que únicamente estamos
considerando enteros no negativos en los exponentes de 2k . Si no fuera así, aun en el caso en
que x ̸= y, dado un k tal que x = 2k y, bastaría tomar −k para tener y = 2−k x.
Para demostrar que R satisface la propiedad transitiva debemos demostrar que, si x = 2ℓ y
e y = 2m z, entonces necesariamente x = 2k z para algún k ∈ Z+ . Sustituyendo la segunda
ecuación en la primera tenemos que, en efecto, x = 2ℓ 2m z = 2ℓ+m z = 2k z, con k = ℓ + m ∈ Z+ .
b) El diagrama de Hasse pedido es el siguiente:
c) El conjunto de los elementos maximales de (X, R) es {8, 6, 10}. Por su parte, {2, 3, 5} es el
conjunto de los elementos minimales. Obviamente no hay ni máximo ni mínimo en (X, R).
Finalmente, tanto el conjunto de las cotas inferiores como el de las cotas superiores de X ⊂ N
son vacíos.
PROBLEMA 9:
Para cada j ∈ N definimos el conjunto Vj ⊂ Z+ de la manera siguiente:
Vj = {x ∈ Z+ | 0 ≤ x ≤ j − 1 y x es inversible en Zj } .
Sea ahora el conjunto V = V10 ∪ V12 ∪ V15 ⊂ Z+ . Sobre V definimos la relación de orden parcial
aRb ⇔ a | b.
1. Encontrar los elementos de V .
2. Encontrar el diagrama de Hasse de (V, |).
3. Sea el subconjunto B ⊆ V definido por
B = V10 △V12 ,
donde A△B es la diferencia simétrica de los conjuntos A y B. Encontrar sup(B) e ı́nf(B).

Solución:
1) Los conjuntos Vj estarán formados por los elementos:
V10 = {1, 3, 7, 9} ,
V12 = {1, 5, 7, 11} ,
V15 = {1, 2, 4, 7, 8, 11, 13, 14} .
Por tanto, el conjunto V se obtiene sin mas que unir los anteriores conjuntos:
V = {1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 14} .

2) El diagrama de Hasse de (V, |) puede representarse en la forma:

3) El conjunto B es igual a B = V12 △V10 = {3, 5, 9, 11}. Del diagrama de Hasse se sigue
directamente que

mayor(B) = ∅ , sup(B) no existe

minor(B) = {1} , ı́nf(B) = 1 . (1)

PROBLEMA 10:
Sea T = {a, b, c, d, e, f, g} la lista de tareas para realizar un trabajo, de las que se sabe que
unas preceden inmediatamente a otras de la siguiente forma: f ⩽ a, f ⩽ d, e ⩽ b, c ⩽ f , e ⩽ c,
b ⩽ f , e ⩽ g, g ⩽ f . Hallar el orden parcial correspondiente y dibujar su diagrama de Hasse.
¿Qué tareas se pueden realizar independientemente? Obtener un orden total compatible con
ese orden parcial.
Solución:
El diagrama de Hasse será:

a d

g c b

Las tareas que se pueden realizar independientemente serán las que correspondan a tareas no
comparables. En este caso será el conjunto {b, c, g} y {a, d}. Un orden total compatible con
este orden parcial puede ser. (e, g, c, b, f, a, d)

PROBLEMA 11:
De estas relaciones sobre conjuntos de personas determinar cuáles son de equivalencia y cuales
no dando las razones oportunas. Determinar qué propiedades se cumplen y cuáles no.

1. {(a, b)|a y b tienen la misma edad}

2. {(a, b)|a y b tienen los mismos padres}

3. {(a, b)|a y b comparten un progenitor común}

4. {(a, b)|a y b se conocen}

5. {(a, b)|a y b hablan un mismo idioma}

Solución:

1. Es de equivalencia (reflexiva, simétrica y transitiva).

2. Es de equivalencia (reflexiva, simétrica y transitiva).

 3. No es de equivalencia porque no es transitiva. Si A es hijo de W y X y a su vez B lo es
de X y Y y C lo es de Y y Z, se puede ver que A y B están relacionados, así como B y C,
pero A y C no lo están entre sí.

4. No es de equivalencia porque claramente no es transitiva. Quizás A y B se conozcan entre

sí, al igual que B y C, pero eso no significa que se conozcan A y C.

5. No es de equivalencia porque no es transitiva (igual que en 3).

PROBLEMA 12:
Demostrar que la relación R consistente en todos los pares (x, y) tales que x e y son cadenas
de bits de longitud 3 o mayor que coinciden en sus tres primeros bits (por la izquierda) es una
relación de equivalencia sobre el conjunto de todas las cadenas de bits de longitud 3 o más. ¿A
qué clases de equivalencia pertenecen las cadenas 010, 1011, 11111 y 01010101?
Solución:
Los primeros tres bit de una cadena coinciden consigo mismos, así que se da la propiedad
reflexiva. Si los tres primeros bits de una cadena coinciden con los tres primeros de otra cadena,
entonces los de la segunda cadena necesariamente coinciden con la primera cadena, así que es
simétrica. Si coinciden los tres primeros bits de la cadena A con los tres primeros de la cadena
B y a su vez coinciden con los de C, entonces necesariamente los de A coinciden con los de C,
así que es transitiva. Por tanto es una relación de equivalencia.
Las clases que nos piden son las clases cuyos elementos empiezan por 010, 101, 111 y 010.

PROBLEMA 13:
Considérese la relación de orden parcial ⪯ definida en el conjunto D de los divisores positivos
de 66 , excluyendo el 1, mediante

a ⪯ b ⇔ a divide a b .

1. Dibujar el diagrama de Hasse del orden parcial (D, ⪯).

2. Dar, si existen, los elementos maximales y minimales, así como el máximo y mínimo de
(D, ⪯).

Solución:

66

6 22 33

2 3 11

Minimales son 2, 3 y 11, no hay mínimo. Maximal es el 66 y, por tanto, el máximo es 66.
PROBLEMA 14:
Considérese la relación de orden parcial ⪯ definida en el conjunto D de los divisores positivos
de 48 , excluyendo el 1, mediante

a ⪯ b ⇔ a divide a b .

1. Dibujar el diagrama de Hasse del orden parcial (D, ⪯).

2. Dar, si existen, los elementos maximales y minimales, así como el máximo y mínimo de
(D, ⪯).

Solución:

48

16 24

8 12

4 6

2 3

Minimales son 2 y 3, no hay mínimo. Maximal es el 48 y, por tanto, el máximo es 48.