Interrogaci On2: Instrucciones

Pontificia Universidad Católica de Chile
Departamento de Ciencia de la Computación

IIC1253 - Matemáticas Discretas
Interrogación 2
3 de octubre de 2019
Profesores: Gabriel Diéguez - Fernando Suárez
Instrucciones
Use lápiz pasta. Por el uso de lápiz mina usted pierde el derecho a recorreción.
Rellene sus datos en cada hoja de respuesta que utilice.
Cada pregunta debe responderse en hojas separadas.

Entregue al menos una hoja por pregunta.
• Si entrega la pregunta completamente en blanco, tiene nota mı́nima 1.5 en vez de
1.0 en la pregunta entregada.
Pregunta 1
a) (4 pts) Demuestre que si S es una partición cualquiera de un conjunto A, entonces la
relación
x ∼ y ⇔ ∃X ∈ S tal que {x, y} ⊆ X
es una relación de equivalencia sobre A.
b) (1 pt) Demuestre que existe un único conjunto vacı́o.
c) (1 pt) Demuestre que para todo conjunto A se tiene que ∅ ⊆ A.
Solución
a) Reflexividad: Dado x ∈ A, sabemos que x ∈ X para algún X ∈ S, pues S es una
partición de A. Luego, {x} ⊆ X, y por axioma de extensión {x, x} ⊆ X. Aplicando
la definición de la relación ∼, concluimos que x ∼ x y por lo tanto la relación es
refleja.
Simetrı́a: Dados x, y ∈ A tales que x ∼ y, por definición de ∼ sabemos que existe
X ∈ S tal que {x, y} ⊆ X. Por axioma de extensión, se cumple que {y, x} ⊆ X, y
por definición de ∼ concluimos que y ∼ x. Por lo tanto, la relación es simétrica.
Transitividad: Dados x, y, z ∈ A tales que x ∼ y e y ∼ z, por definición de ∼
sabemos que existen X1 , X2 ∈ S tales que {x, y} ⊆ X1 y {y, z} ⊆ X2 . Notemos
que X1 ∩ X2 6= ∅, y por lo tanto como S es una partición de A, necesariamente
X1 = X2 . Luego, se cumple que {x, y} ⊆ X2 , y entonces {x, z} ⊆ X2 . Finalmente,
aplicando la definición de ∼, tenemos que x ∼ z, con lo que concluimos que la
relación es transitiva.
b) Por contradicción, supongamos que existen dos conjuntos vacı́os distintos: ∅1 6= ∅2 .

Dado que todo conjunto tiene como subconjunto al vacı́o, y como ∅1 y ∅2 son conjuntos,
tenemos que ∅1 ⊆ ∅2 , ya que estamos suponiendo que ∅1 es vacı́o. Recı́procamente, se
tiene que ∅2 ⊆ ∅1 . Entonces, tenemos que ∅1 ⊆ ∅2 y ∅2 ⊆ ∅1 , de donde se concluye
que ∅1 = ∅2 , lo que contradice nuestra suposición incial de que existen dos conjuntos
vacı́os distintos.
c) Aplicando la definición de subconjunto, debemos demostrar que ∀x, x ∈ ∅ ⇒ x ∈ A.

Como no existe ningún elemento que pertenezca al conjunto vacı́o, la propiedad se cumple
trivialmente, y luego ∅ ⊆ A.
Pauta (6 pts.)
a) 1 pto. por caso reflexividad.
1 pto. por simetrı́a.
2 ptos. por transitividad.
b) 1 pto.
c) 1 pto.
Soluciones alternativas y puntajes intermedios a criterio del corrector.
Pregunta 2 [Relaciones de equivalencia]

a) Sea R una relación simétrica y transitiva sobre un conjunto A. Demuestre que si para
cada a ∈ A existe un b ∈ A tal que (a, b) ∈ R, entonces R es una relación de equivalencia.
b) Sea R una relación refleja y transitiva sobre un conjunto A. Sea T una relación sobre A
definida como
(a, b) ∈ T si y sólo si {(a, b), (b, a)} ⊆ R
Demuestre que T es transitiva.
c) Diremos que una relación R sobre un conjunto A es circular si
∀x∀y∀z(xRy ∧ yRz → zRx).
Demuestre que R es una relación de equivalencia si y sólo si es refleja y circular.

Solución
a) Dado que la relación es simétrica y transitiva, basta con demostrar que es refleja.
Suponemos que para cada a ∈ A existe un b ∈ B tal que (a, b) ∈ R. Sea a ∈ A, por
hipótesis existe b ∈ A tal que (a, b) ∈ R. Como R es simétrica, se tiene que (b, a) ∈ R.
Además, como R es transitiva y (a, b) ∈ R y (b, a) ∈ R, obtenemos que (a, a) ∈ R.
Finalmente podemos concluir que (a, a) ∈ R, ∀a ∈ A.
b) Sea (a, b) ∈ T y (b, c) ∈ T . Por definición, sabemos que (a, b) ∈ R, (b, a) ∈ R y
(b, c) ∈ R, (c, b) ∈ R. Como R es transitiva, obtenemos que (a, c) ∈ R y (c, a) ∈ R.
Luego, por definición de T obtenemos que (a, c) ∈ T . Finalmente, como a, b y c son
arbitrarios, podemos concluir que T es transitiva.
c) (⇒) Sea R una relación de equivalencia. Dado que R es refleja, sólo debemos mostrar
que es circular. Sean (a, b) ∈ R y (b, c) ∈ R. Como R es transitiva obtenemos que
(a, c) ∈ R. Luego, como R es simétrica se tiene que (c, a) ∈ R. Finalmente, como
a, b y c son arbitrarios, concluimos que R es circular.
(⇐) Sea R una relación refleja y circular. Mostraremos que es simétrica y transitiva.
• Simetrı́a: Sea (a, b) ∈ R. Como R es refleja sabemos que (b, b) ∈ R. Además,
como es circular obtenemos que (b, a) ∈ R. Por lo tanto, podemos concluir
que R es simétrica.
• Transitividad: Sea (a, b) ∈ R y (b, c) ∈ R. Como R es circular, obtenemos
que (c, a) ∈ R. Luego, dado que R es simétrica tenemos que (a, c) ∈ R.
Finalmente, como a, b y c son arbitrarios concluimos que R es transitiva.
Pauta (6 pts.)
a) 2 ptos.
b) 2 ptos.
c) 1 pto. por (⇒).
1 pto. por (⇐).
Puntajes intermedios y soluciones alternativas a criterio del corrector.
Pregunta 3 [Relaciones de orden]

a) Sea (A, ) un orden total, y S ⊆ A tal que S es finito y no vacı́o. Demuestre que sup(S)
e inf (S) existen y pertenecen a S.
Hint: use inducción.
b) Sea (A, ) un orden total, y S1 ⊆ A tal que tiene supremo. Suponga ahora que existe
S2 ( S1 tal que para todo x ∈ S1 existe y ∈ S2 tal que x y. Demuestre que S2 tiene
supremo, y que sup(S2 ) = sup(S1 ).
Solución
a) Sea S ⊆ A con n elementos. Mostraremos que sup(S) e inf (S) existen y pertenecen a
S por inducción simple sobre n.
BI: Sea n = 1. En este caso S = {s}, con s ∈ A. Por un lado, dado que (A, ) es un
orden total, obtenemos que s s, y como s es el único elemento de S, se tiene que
es cota inferior y superior. Por otro lado, dada una cota superior c, como s ∈ S se
tiene que s c y por lo tanto s = sup(S). De manera análoga podemos concluir
que s = inf (S).
HI: Suponemos que para todo S ⊆ A con n elementos, tanto sup(S) como inf (S)
existen y pertenecen a S.
TI: Sea S ⊆ A con n + 1 elementos: A = {s1 , . . . , sn , sn+1 }. Sea A0 = {s1 , . . . , sn },
el cual tiene n elementos. Por HI A0 está acotado y sup(A0 ), inf (A0 ) ∈ A0 . Sin
pérdida de generalidad, asumimos que inf (A0 ) = s1 y sup(A0 ) = sn . Tenemos 2
casos:
i) Si sn sn+1 entonces si sn+1 para todo i ∈ 1 . . . n (dado que sn = sup(A0 )).
Además, como sn+1 sn+1 obtenemos que sn+1 es cota superior de A. Por
otro lado, como sn+1 ∈ A concluimos que sn+1 = sup(A).
ii) Si sn+1 sn entonces si sn para todo i ∈ 1 . . . n + 1. Por lo tanto, sn es
cota superior de A y como sn ∈ A se tiene que sn = sup(A).
De manera análoga se puede mostrar el resultado para el ı́nfimo de A.
b) Debemos mostrar que el supremo de S1 es también supremo de S2 . Para esto mostraremos

que sup(S1 ) es cota superior de S2 (I) y que para toda cota superior c de S2 se tiene
que sup(S1 ) c (II).
i) Sea c una cota superior de S1 . Para todo x ∈ S1 se cumple que x c. Como

S2 ( S1 , si x0 ∈ S2 entonces x ∈ S1 , y por lo tanto x0 c. Luego, toda cota
superior de S1 es también una cota superior de S2 . En particular, sup(S1 ) es una
cota superior de S1 , y por ende también lo debe ser para S2 .
ii) Por contradicción, sea c una cota superior de S2 tal que c sup(S1 ). Luego, c no
puede ser cota superior de S1 ya que es menor que su supremo. Entonces, debe
existir un x ∈ S1 tal que c x. Luego, por la propiedad del conjunto S2 , debe
existir un y ∈ S2 tal que x y. Finalmente, por transitividad obtenemos que
c y lo que contradice el hecho de que c es cota superior de S2 . Concluimos que
sup(S2 ) = sup(S1 ).
Pauta (6 pts.)
a) 1 pto por BI.
0.5 ptos por HI.
1.5 ptos por TI.
b) 1 pto por i).

2 ptos por ii).
Pregunta 4 [Funciones y cardinalidad]

a) Sean A y B conjuntos. Demuestre que si A ≈ B entonces P(A) ≈ P(B).
b) Sean a, b, c, d ∈ R tales que a < b y c < d. Demuestre que [a, b] ≈ [c, d].
Solución
a) Como A ≈ B, sabemos que existe f : A → B biyectiva. Considere la función
g : P(A) → P(B) definida como
g(X) = {b ∈ B | ∃a ∈ X tal que f (a) = b}, ∀X ∈ P(A).

Es decir, la función g asigna a cada subconjunto X de A el conjunto de las imágenes de
los elementos de X bajo la función f . Demostraremos que g es una función biyectiva
entre P(A) y P(B), con lo que quedará demostrado que P(A) ≈ P(B).
Inyectiva: Sean X1 , X2 ∈ P(A) tales que g(X1 ) = g(X2 ). Queremos demostrar

que X1 = X2 , y lo haremos usando la definición de igualdad de conjuntos.
• X1 ⊆ X2 : Sea a ∈ X1 . Por definición de g, sabemos que f (a) ∈ g(X1 ). Como
g(X1 ) = g(X2 ), se tiene que f (a) ∈ g(X2 ), y entonces por definición de g
sabemos que existe a0 ∈ X2 tal que f (a) = f (a0 ). Ahora, como f es biyectiva,
es inyectiva, y por lo tanto a = a0 , de donde obtenemos que a ∈ X2 .
• X2 ⊆ X1 : Sea a ∈ X2 . Por definición de g, sabemos que f (a) ∈ g(X2 ). Como
g(X1 ) = g(X2 ), se tiene que f (a) ∈ g(X1 ), y entonces por definición de g
sabemos que existe a0 ∈ X1 tal que f (a) = f (a0 ). Ahora, como f es biyectiva,
es inyectiva, y por lo tanto a = a0 , de donde obtenemos que a ∈ X1 .
Sobreyectiva: Sea Y ∈ P(B). Como f es biyectiva, es invertible, y por lo tanto
podemos tomar el conjunto
X = {a ∈ A | ∃b ∈ Y tal que f −1 (b) = a}.
Es decir, X es el conjunto de las preimágenes de los elementos en Y bajo f .

Demostraremos que Y = g(X), con lo que se concluye que g es sobreyectiva.
• Y ⊆ g(X): Sea b ∈ Y . Por definición de X, sabemos que f −1 (b) ∈ X.
Entonces, por definición de g, tenemos que f (f −1 (b)) ∈ g(X), y por lo tanto
b ∈ g(X).
• g(X) ⊆ Y : Sea b ∈ g(X). Por definición de g, sabemos que existe a ∈ X tal
que f (a) = b. Ahora, por definición de X, sabemos que existe b0 ∈ Y tal que
f −1 (b0 ) = a. Entonces, tenemos que b = f (a) = f (f −1 (b0 )) = b0 , y por lo tanto
b∈Y.
b) Queremos construir una función f : [a, b] → [c, d] que sea biyectiva. Una posibilidad es
mapear a a c y b a d, y mapear los puntos intermedios linealmente. En otras palabras,
podemos tomar una recta que pase entre los puntos (a, c) y (b, d) del plano real:
d−c
f (x) = · (x − a) + c
b−a
Esta función está bien definida, pues como a < b se tiene que b − a 6= 0. Por otro lado,
como c < d, esta función es claramente biyectiva. Lo demostraremos a continuación:
Inyectiva: Sean x1 , x2 ∈ [a, b] tales que f (x1 ) = f (x2 ). Por definición de f ,
d−c d−c
· (x1 − a) + c = · (x2 − a) + c,
b−a b−a
de donde es evidente que x1 = x2 luego de despejar todas las constantes.
Sobreyectiva: Sea y ∈ [c, d]. Esto quiere decir que
c ≤ y ≤ d
0 ≤ y−c ≤ d−c
0 ≤ (b − a)(y − c) ≤ (b − a)(d − c)
b−a
0 ≤ d−c
(y − c) ≤ b−a
a ≤ b−a
d−c
(y − c) + a ≤ b
Tenemos entonces un x ∈ [a, b] definido como

b−a
x= (y − c) + a.
d−c
Es claro que f (x) = y, con lo que demostramos que f es sobreyectiva.
Pauta (6 pts.)
a) 1 pto. por dar la biyección.
1 pto. por demostrar inyectividad.
1 pto. por demostrar sobreyectividad.
b) 1.5 ptos. por dar la biyección.
0.75 ptos. por demostrar inyectividad.
0.75 ptos. por demostrar sobreyectividad.

Interrogaci On2: Instrucciones

Cargado por

Copyright:

Formatos disponibles

Interrogaci On2: Instrucciones

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Interrogaci On2: Instrucciones

Cargado por

Copyright:

Formatos disponibles

Pontificia Universidad Católica de Chile

Departamento de Ciencia de la Computación

Rellene sus datos en cada hoja de respuesta que utilice.

Cada pregunta debe responderse en hojas separadas.

b) (1 pt) Demuestre que existe un único conjunto vacı́o.

c) (1 pt) Demuestre que para todo conjunto A se tiene que ∅ ⊆ A.

b) Por contradicción, supongamos que existen dos conjuntos vacı́os distintos: ∅1 6= ∅2 .

c) Aplicando la definición de subconjunto, debemos demostrar que ∀x, x ∈ ∅ ⇒ x ∈ A.

Pregunta 2 [Relaciones de equivalencia]

c) Diremos que una relación R sobre un conjunto A es circular si

∀x∀y∀z(xRy ∧ yRz → zRx).

Demuestre que R es una relación de equivalencia si y sólo si es refleja y circular.

Pregunta 3 [Relaciones de orden]

b) Debemos mostrar que el supremo de S1 es también supremo de S2 . Para esto mostraremos

i) Sea c una cota superior de S1 . Para todo x ∈ S1 se cumple que x  c. Como

b) 1 pto por i).

Pregunta 4 [Funciones y cardinalidad]

g : P(A) → P(B) definida como

g(X) = {b ∈ B | ∃a ∈ X tal que f (a) = b}, ∀X ∈ P(A).

Inyectiva: Sean X1 , X2 ∈ P(A) tales que g(X1 ) = g(X2 ). Queremos demostrar

X = {a ∈ A | ∃b ∈ Y tal que f −1 (b) = a}.

Es decir, X es el conjunto de las preimágenes de los elementos en Y bajo f .

Tenemos entonces un x ∈ [a, b] definido como

También podría gustarte

i) Sea c una cota superior de S1 . Para todo x ∈ S1 se cumple que x c. Como