Universidad Nacional de Colombia, Medellı́n – Escuela de Matemáticas

Conjuntos y Combinatoria – Junio 6, 2011

Taller 4 – Soluciones

1. Cardinalidad finita.

a) Pruebe que si f : In → In es una función inyectiva, entonces es

también una función sobreyectiva. La prueba debe ser directa usando
inducción, sin hacer referencia a resultados conocidos similares, o
haciendo uso de resultados acerca de cardinalidad. Recuerde que
In = {1, 2, 3, . . . , n}.
Solución: (De las notas sobre cardinalidad finita) La prueba es por
inducción sobre n. En el caso base n = 0, I0 = ∅, la unica función
f : I0 → I0 es trivialmente biyectiva. Ahora asumimos el enunciado
es cierto para un n ≥ 0 y lo probamos para n+1. Sea f : In+1 → In+1
una función inyectiva. Consideramos dos casos:
1. f(In ) ⊆ In : Entonces la restricción f|In : In → In es también
inyectiva, y entonces por hipótesis de inducción, es sobreyectiva.
Pero entonces se debe tener que f(n + 1) = n + 1 y por lo tanto
f también es sobreyectiva, lo que querı́amos probar.
2. f(In ) 6⊆ In : Entonces existe j ∈ In tal que f(j) = n + 1, y puesto
que f es inyectiva, f(n + 1) ∈ In . Definimos entonces la función
g : In+1 → In+1 como

 f(i) si i ∈ In − {j}
g(i) = f(n + 1) si i = j

n+1 si i = n + 1

Esta función g es claramente inyectiva y satisface g(In ) ⊆ In , por lo

que se puede aplicar el primer caso para concluir que g es sobreyec-
tiva. Por construcción f también es sobreyectiva.
b) Use (a) para deducir que no existe n ∈ N tal que N ∼ In .
Solución: Supongamos que existe n ∈ N tal que N ∼ In . Es decir,
existe una biyección f : N → In . Entonces su restricción

f|In+1 : In+1 → In

1
 a In+1 es una función inyectiva. Sea f^ esta misma función, pero con el
codominio extendido a In+1 . Entonces f^ : In+1 → In+1 es inyectiva y
por la parte (a) debe ser también sobreyectiva. Pero esto es absurdo
porque el rango de f^ es el mismo de f|In+1 , y por lo tanto es un
subconjunto de In . De aquı́ se concluye que no existe n ∈ N tal que
N ∼ In .
c) Use (a) para deducir el principio del palomar: Sea f : Im → In una
función. Si m > n entonces f no es inyectiva.
Solución: Sea f : Im → In una función y supongamos que m > n y
f es inyectiva. Como en la solución de (b), consideremos f^ igual a f
pero con el codomino extendido a Im . Entonces, por (a), f^ es sobre-
yectiva, lo que es absurdo porque el rango de f^ es un subconjunto
de In .

2. Pruebe que J : N × N → N dada por

1
J(m, n) = (1 + 2 + 3 + · · · + (m + n)) + m = ((m + n)2 + 3m + n)
2
es una biyección, que corresponde a “recorrer” N × N diagonal por dia-
gonal:

5 15
4 10 16
3 6 11 17
n
2 3 7 12 18
1 1 4 8 13 19
0 0 2 5 9 14 20
0 1 2 3 4 5
m

Solución: Primero verificamos la inyectidad. Sean m, n y m 0 , n 0 tal

que J(m, n) = J(m 0 , n 0 ). Queremos probar que m = m 0 y n = n 0 . Si
m + n = m 0 + n 0 + k, con k ≥ 0 (sin pérdida de generalidad), entonces

1
J(m, n) = ((m + n)2 + 3m + n)
2
1
= ((m + n)2 + m + n) + m
2
1 1
= ((m 0 + n 0 )2 + m 0 + n 0 ) + (m 0 + n 0 )k + (k2 + k) + m
2 2
1
= J(m 0 , n 0 ) + (k − 1)m 0 + kn 0 + (k2 + k) + m,
2

2
 lo cual contradice J(m, n) = J(m 0 , n 0 ) si k ≥ 1. Por lo tanto k = 0 y
entonces m + n = m 0 + n 0 , y también m = m 0 (de donde n = n 0 ).
Para verificar la sobreyectividad, sea ` ∈ N y sea
1 2
k = máx {d ∈ N : (d + d) ≤ `}.
2
Tomemos
1
m = ` − (k2 + k), n = k − m
2
y veamos que m, n ≥ 0 y J(m, n) = `: Es claro que m ≥ 0 porque
1
2
(k2 + k) ≤ `. Y n ≥ 0 porque k ≥ m, y esto porque si m > k entonces
m ≥ k + 1 y entonces
1 1 1
` = (k2 + k) + m ≥ (k2 + k) + (k + 1) = ((k + 1)2 + (k + 1))
2 2 2
lo que contradice la definición de k. Finalmente
1 1
J(m, n) = ((m + n)2 + m + n) + m = (k2 + k) + m = `.
2 2

3. (Teorema de Cantor) Pruebe que para todo conjunto A, A y P(A) (con-

junto de partes) no tienen la misma cardinalidad. El argumento debe ser
claro y completo.
4. Pruebe directamente que para cualquier conjunto S se tiene que S ≺ 2S
(sin usar el terorema de Cantor para P(S)), de la siguiente manera: Si
F : S → 2S es una biyección, considere la función g ∈ 2S , dada por
g(x) = 1 − F(x)(x)
(aquı́, F(x)(x) es (F(x))(x)). Deduzca una contradicción.

Solución: Es fácil deducir que S  2S (a partir de la función inyectiva

G : S → 2S dada por G(x) = χ{x} , donde χ{x} : S → {0, 1} es la función
caracterı́stica de {x}), ası́ que sólo queda verificar que S 6∼ 2S , lo cual se
hace por contradicción. Suponemos que F : S → 2S es una biyección, y
consideramos la función g ∈ 2S , dada por
g(x) = 1 − F(x)(x).
Puesto que F es una biyección, existe d ∈ S tal que F(d) = g. Pero
entonces
g(d) = 1 − F(d)(d) = 1 − g(d),
lo cual es absurdo, ya que g(d) ∈ {0, 1}.

3
 P∞C se define
5. El conjunto de Cantor como el conjunto de todos los números
reales de la forma n=1 an 3 donde an ∈ {0, 2}. Use el método de la
−n

diagonal para probar que C no es contable.

Solución: En otras palabras, C consiste de los números en [0, 1] cuya

representación fraccional base 3 sólo tiene dı́gitos 0 y 2 (no tiene el dı́gito
1). Como en el caso de la representación base 10, el mismo número puede
tener dos representaciones distintas. En el caso base 3, esto se debe a que
X
∞
2 X −n 2
∞
1
−n
2·3 = · 3 = · = 1.
n=1
3 n=0 3 1 − 1/3

Ası́ que, en general, los números que tienen una representación que ter-
mina en 0’s también tienen otra que termina en 2’s. A pesar de esto,
los números que nos interesan, los que pertenecen a C, sólo tienen una
representación que los hace miembros de C (porque la otra representación
tiene un 1): Por ejemplo,

0,022222 · · · = 0,10000 · · · y 0,200000 · · · = 0,1222222 · · · .

Con esto aclarado, supongamos que C es contable. Es decir, que existe

una biyección f : N+ → C. Para m ∈ N+ , puesto que f(m) ∈ C, f(m)
tiene la forma
X∞
am,n 3−n
n=1
P∞
donde am,n ∈ {0, 2}. Definimos un número β con representación n=1 bn 3−n
definida por 
2 si an,n = 0
bn =
0 si an,n = 2
Por definición, β ∈ C y por nuestra hipótesis, existe N ∈ N+ tal que
f(N) = β. Pero entonces

bN = 2 sii aN,N = 0

lo que es absurdo porque los bn y los aN,n deben ser los dı́gitos (ternarios)
en la única representación de β = f(N). Por lo tanto C no es contable.

6. El siguiente argumento es una variante de una primera prueba de Cantor

para la incontabilidad de los reales (obtenida por Cantor unos 15 años
antes del argumento de la diagonal):
Supongamos que el conjunto [0, 1] es contable, es decir existe una biyec-
ción f : N+ → [0, 1]. Sea [a0 , b0 ] = [0, 1].

4
 a) Justifique que para n ≥ 1, dado el intervalo cerrado [an−1 , bn−1 ], se
puede escoger un intervalo [an , bn ] tal que

an > an−1 , bn < bn−1 y f(n) 6∈ [an , bn ].

Solución: Dividimos el intervalo [an−1 , bn−1 ] en cinco subinterva-

los cerrados de igual longitud. Al menos uno de los tres intervalos no
extremos no contiene f(n). Escogemos este intervalo como [an , bn ].

b) Justifique que esto lleva a una contradicción. Sugerencia: Aplique la

propiedad de la mı́nima cota superior (si un subconjunto no vacı́o
es acotado superiormente, entonces tiene una mı́nima cota supe-
rior) y la propiedad de la máxima cota inferior a los conjuntos
{a0 , a1 , a2 , . . .} y {b0 , b1 , b2 , . . .} respectivamente. Esa mı́nima cota
superior y esa máxima cota inferior deben ser iguales, etc.
Solución: Sean A = {a0 , a1 , a2 , . . .} y B = {b0 , b1 , b2 , . . .}. Por
la construcción, para todo i, j, ai < bj . En particular A tiene cotas
superiores y B cotas inferiores, y por lo tanto existen una mı́nima
cota superior α de A y una máxima cota inferior β de B. Para todo
i, ai < β porque ai+1 es también una cota inferior de B y ai+1 > ai .
Es decir, β es también una cota superior de A y por lo tanto α ≤ β.
Pero [α, β] 6= ∅ (aún para α = β), y por construcción cualquier
x ∈ [α, β] no es igual a algún f(n) (porque [α, β] ⊆ [an , bn ]). Esto
es una contradicción porque habı́amos asumido que f era una bi-
yección. (Cantor usó este tipo de argumento también para probar
que existen números trascendentales; en ese caso α = β porque si
α < β entonces existe un q ∈ (α, β) racional y por tanto algebraico.
Entonces x = α = β es trascendental porque es diferente de todos
los algebraicos f(1), f(2), f(3), . . .)

7. Pruebe que el conjunto

S = {x ∈ (0, 1) : la expansión decimal de x tiene sólo dı́gitos impares}.

es no contable. (Asuma que se usa la expansión decimal que no termina

en 9’s.)

8. Pruebe que no existe un conjunto A (de conjuntos) con la propiedad de

que para todo conjunto X existe Y ∈ A tal que X  Y (el sı́mbolo 
denota la relación “dominado por”).

5
 S
Solución: Supongamos que tal A existe. Sea entonces A la unión de
los elementos de A, es decir
[ [
A= Z
Z∈A
S
y consideramos
S su conjunto de partes S A). Por hipótesis, existe Y ∈ A
P(
S P( A)  Y. Además Y  A porque Y ∈ A y por lo tanto
tal que
Y ⊆ A. Pero entonces
[ [
P( A)  Y  A
S
S es absurdo porque por el teorema de Cantor se tiene que A ≺
lo que
P( A).
9. Sea A 6= ∅. Pruebe que las siguientes afirmaciones son equivalentes:
a) A es inifinito
b) Para todo a ∈ A, A ∼ A − {a}
c) Para todo b 6∈ A, A ∼ A ∪ {b}
Sugerencia: Pruebe (a) ⇒ (b) ⇒ (c) ⇒ (a)
Solución: (a) ⇒ (b) Sea a ∈ A arbitrario. Entonces A − {a} es infinito,
y por lo tanto existe B ⊆ A − {a} enumerable (esto usa el axioma de elec-
ción). Sea f : N → B una biyección correspondiente. Entonces definimos
la función g : A → A − {a} como

 x si x ∈ A − B − {a}
g(x) = f(0) si x = a

f(1 + f−1 (x)) si x ∈ B
y esta g es una biyección.
(b) ⇒ (c) Sea b 6∈ A y escogemos a ∈ A arbitrario. Entonces, por hipóte-
sis A ∼ A − {a}, y sea f : A − {a} → A una biyección correspondiente.
Entonces definimos la función g : A → A ∪ {b} como

f(x) si x ∈ A − {a}
g(x) =
b si x = a
y esta g es una biyección.
(c) ⇒ (a) Si A es finito entonces existe n tal que A ∼ In . Por hipótesis,
para b 6∈ A, A ∼ A ∪ {b}. Pero entonces
In ∼ A ∼ A ∪ {b} ∼ In ∪ {b} ∼ In+1
lo que contradice el principio del palomar.

6
10. Determine las cardinalidades de las colecciones de funciones:
C1 = {f | ∃n ∈ N, f : N → In es una función}
C2 = {f | f : N → {0, 1} es una función y ∃n ∈ N, f(i) = 0 si i > n}

Justifique claramente su respuesta.

Solución: Solución 1 para C1 : Tenemos que

[
C1 = C1,n
n≥1

donde
C1,n = {f | f : N → In es una función}
Por definición, |C1,n | = nℵ0 . Si n = 1, esto es 1, y si n ≥ 2 entonces
nℵ0 = 2ℵ0 porque

2ℵ0 ≤ nℵ0 ≤ ℵℵ ℵ0 ℵ0
0 ≤ (2 )
0
= 2ℵ0 ·ℵ0 = 2ℵ0 .

Entonces para n ≥ 2, C1,n ∼ R y por lo tanto

C1 ∼ C1 − C1,1 ∼ N × R

(donde la primera equipotencia es porque C1 es infinito y |C1,1 | = 1). Pero

N × R ∼ R y por lo tanto

|C1 | = 2ℵ0 .

Solución 2 para C1 : Podemos establecer C1  [0, 1] directamente con una

función inyectiva Ψ : C1 → [0, 1]. Para f ∈ C1 , sea hf(m)i, el valor f(m)
en representación binaria. Definimos, usando representación decimal

Ψ(f) = 0.hf(0)i 5 hf(1)i 5 hf(2)i 5 hf(3)i 5 · · ·

donde el uso de repersentación binaria en cada hf(m)i y del 5 como

separador permite identificar f a partir de Ψ(f). Por lo tanto |C1 | ≤ 2ℵ0 .
Por otra parte C1,2 = 2N y por lo tanto, de

2N = C1,2 ⊆ C1

se obtiene que 2ℵ0 ≤ |C1 |. Ası́ que 2ℵ0 ≤ |C1 | ≤ 2ℵ0 y por lo tanto
|C1 | = 2ℵ0 .
Solución para C2 : Tenemos que
[
C2 = C2,n
n≥1

7
 donde

C2,n = {f | f : N → {0, 1} es una función y f(i) = 0 si i > n}

Entonces |C2,n | = 2n+1 . Ası́ que C2 es una unión contable de conjuntos

finitos, y por lo tanto contable. Es decir, |C2 | ≤ ℵ0 . Pero C2 no es finito,
por lo tanto |C2 | = ℵ0 .
11. Determine la cardinalidad de las siguientes colecciones de rectángulos en
R2 = R × R:

R1 = {[a, b] × [c, d] | a, b, c, d ∈ N; a < b, c < d}

R2 = {[a, b] × [c, d] | a, c ∈ R; b − a ∈ N+ , d − c ∈ Q+ }

Justifique claramente su respuesta. ( [u, v], con u ≤ v, denota el intervalo

cerrado {x ∈ R | u ≤ x ≤ v} y Q+ = {x ∈ Q | x > 0}.)

12. En R2 , una figura “ocho” consiste de dos circunferencias tangentes del

mismo radio, pero no una dentro de la otra. Pruebe que cualquier conjunto
de figuras “ocho” disjuntas en el plano es contable. (Note que se permite
que una figura “ocho” esté dentro de una de las circunferencias de otra
figura “ocho”.)

Solución: Como en el ejercicio 27, en cada circunferencia de un “ocho”

C se puede encontrar un par de racionales (qC,1 , qC,2 ) y (rC,1 , rC,2 ). La
asociación
C 7→ ((qC,1 , qC,2 ), (rC,1 , rC,2 ))
de tal par de pares a cada “ocho” es inyectiva, por ser estos disjuntos.
Como (Q × Q) × (Q × Q) ∼ N, se conlcuye que cualquier conjunto de
figuras “ocho” disjuntas en el plano es contable.
13. Sean f : A → B y g : B → A funciones inyectivas. La prueba del teorema
de Cantor-Bernstein-Schroeder presentada en clase (atribuı́da a Julius
König) considera para cada a ∈ A la cadena

· · · → g−1 (f−1 (g−1 (a))) → f−1 (g−1 (a)) → g−1 (a) → a → f(a) → g(f(a)) → f(g(f(a))) → · · ·

donde la cadena por la izquierda de a termina si se llega a un elemento

de A − g(B) ó de B − f(A). Llamemos estos casos A-terminación y B-
terminación. Si no hay A- ó B-terminación, se tiene la posibilidad de que
la cadena sea un ciclo finito (donde se repiten los elementos cı́clicamente),
ó una cadena infinita donde se tiene un número infinito de elementos
diferentes. Similarmente se puede formar una cadena para un b ∈ B. La
inyectividad de f y g implica que si x ∈ A ∪ B aparece en la cadena de

8
y ∈ A ∪ B entonces las cadenas de x y y son las mismas. Con lo anterior,
se pueden definir una función biyectiva h : A → B dada por
 −1
g (a) si a está en una cadena con B-terminación
h(a) =
f(a) de lo contrario
(En ciclos y cadenas infinitas cualquiera de las dos funciones podrı́a usarse.)

a) Justifique que h es una función biyectiva.

b) Sean A = [0, 1], B = [0, 1), f(x) = x/2 y g(y) = y. Determine la
función h que resulta de la prueba del teorema de CBS.
Solución: Note que A − g(B) = {1} y B − f(A) = (1/2, 1). Estos
valores son los puntos de partida de las cadenas con A-terminación
y con B-terminación. En particular, sólo hay una cadena con A-
terminación (los elementos en B aparecen primados para distinguir-
los de los elementos de A):
10 1 10 1 10 1 1 0 1
1→ → → → → → → → → ···
2 2 4 4 8 8 16 16
Cada cadena con B-terminación es de la forma, con α ∈ (1/2, 1):
α0 α α0 α α0 α α0 α
α0 → α → → → → → → → → → ···
2 2 4 4 8 8 16 16
Es fácil ver que estas cadenas cubren todos los elementos de A y B
excepto 0 en ambos conjuntos. Estos justamente forman un ciclo:
· · · → 0 → 00 → 0 → 00 → · · ·
La función h : A → B biyectiva que se busca se obtiene de estas
cadenas aparejando de dos en dos comenzando de la izquierda en las
cadenas con A- y B-terminación:
10 1 10 1 10 1 1 0 1
1→ → → → → → → → → ···
| {z 2} |2 {z 4} |4 {z 8} |8 {z16} 16
y
α0 α α0 α α0 α α0 α
α 0
→
| {z }α → → → → → → → → → ···
|2 {z 2} |4 {z 4} |8 {z 8} |16 {z 16}
En este ejemplo, aparte de esto sólo se tiene el aparejamiento de 0
con 0 0 que viene del único ciclo. Ası́ que

x/2 si x = 1/2n para algún n ∈ N
h(x) =
x de lo contrario

9
 c) Sean A = N×N, B = N+ , f(m, n) = 2m 3n y g(`) = (`, 0). Determine
la función h que resulta de la prueba del teorema de CBS.
Solución: Este ya se complica mucho ...

14. Pruebe que el conjunto de todos los subconjuntos finitos de los reales
tiene cardinalidad 2ℵ0 :

a) Directamente, usando una función biyectiva, ó una función inyectiva

(la otra es trivial) y el teorema de Cantor-Bernstein-Schroeder;
Solución: 1a. solución: Puesto que R ∼ [0, 1) podemos trabajar
directamente con [0, 1) en lugar de R.

F = {A ⊆ 2[0,1) : ∃ n ∈ N, |A| = n}

y
Fn = {A ⊆ 2[0,1) : |A| = n}.
Es claro que F = n≥0 Fn . Definimos una función inyectiva f : F →
S
[0, 1] de la siguiente manera. Si A ∈ Fn , sean a1 < a2 < a3 < · · · <
an los elementos de A, y para ai , sea

0.αi,1 αi,2 αi,3 · · ·

la representación binaria de ai (tomando la que termina en 0’s cuan-

do no es única; esa es la razón para trabajar con [0, 1), excluyendo
1 porque no tiene tal representación). Entonces f(A) tiene la repre-
sentación decimal

0.α1,1 α2,1 · · · αn,1 5 α1,2 α2,2 · · · αn,2 5 α1,3 α2,3 · · · αn,3 5 · · ·

donde el dı́gito 5 (el cual no aparece en las representaciones binarias)

se usa como “separador” de los grupos de j-ésimos dı́gitos de todos
los ai . Las representacines binarias de los ai se pueden reconstruir
de f(A) en forma única, por lo tanto f es inyectiva.
2da. solución: Primero, es claro que F1 ∼ [0, 1). También

F2  [0, 1) × [0, 1)  [0, 1],

donde la primera dominación es por la función {a1 < a2 } 7→ (a1 , a2 )

(donde {a1 < a2 } denota que a1 < a2 en el conjunto {a1 , a2 }), y la
segunda dominación es precisamente por la función que intercala las
representaciones decimales. Inductivamente, se tiene entonces

Fn  Fn−1 × [0, 1)  [0, 1) × [0, 1)  [0, 1).

10
 Con un desplazamiento de estas funciones se obtiene para todo n ≥ 0
que
Fn  [n, n + 1)
(note que también F0 = {∅}  [0, 1)), y entonces podemos obtener
F  R uniendo estas funciones.
b) Usando propiedades de los cardinales.
Solución:

Esta prueba no debe requerir el Axioma de Elección.

15. Pruebe que el conjunto de todos los subconjuntos contables de los reales
también tiene cardinalidad 2ℵ0 . En este caso puede hacer uso del Axioma
de Elección. Si el uso no es directo, indique en que resultado de los que
usa en la prueba se necesita el Axioma de Elección.

Solución: Sea FC el conjunto de subconjuntos contables de los reales.

Para todo A ∈ FC existe una función fA : N → A sobreyectiva. Extendien-
do el codominio de fA a R obtenemos una función fA0 : N → R. Si A 6= B
entonces fA0 6= fB0 . Con esto hemos establecido una función inyectiva de
FC a RN , y por lo tanto
FC  RN
Pero
|RN | = (2ℵ0 )ℵ0 = 2ℵ0 ·ℵ0 = 2ℵ0 .
Puesto que tambień R  FC , concluı́mos que |FC | = 2ℵ0 .

El axioma de elección se ha usado en la elección de funcions fA para

A ∈ FC .

16. Pruebe que si el conjunto A tiene cardinalidad 2ℵ0 y B ⊆ A es contable,

entonces la cardinalidad de A − B es 2ℵ0 (note que esto es inmediato por
la propiedad de absorción de los cardinales, pero esa propiedad requiere
el axioma de elección, y la idea acá, en (b), es evitarlo):

a) Asumiendo que existe C ⊆ A − B contable. Justifique la existencia

de tal C usando el Axioma de Elección.
Solución: El conjunto C se puede determinar recursivamente, si
tenemos una función de elección e : P(A) → A. Definimos f : N →
P(A − B) recursivamente como f(0) = {e(A − B)} y

f(n + 1) = f(n) ∪ {e(A − B − f(n))}

11
 S
Entonces C = n≥0 f(n). Entonces fácilmente se puede establecer
una biyección ψ : A → A − B: Sean g : N → B y h : N → C
enumeraciones de B y C (es decir, biyecciones), entonces

 x si x 6∈ B ∪ C
ψ(x) = h(2g−1 (x)) si x ∈ B
 −1
h(2h (x) + 1) si x ∈ C

Por lo tanto A ∼ A − B y entonces |A − B| = 2ℵ0 .

b) Sin hacer uso del axioma de elección de la siguiente manera: usando
que A ∼ [0, 1] y [0, 1] ∼ [0, 1] × [0, 1], y entonces analizando la “ima-
gen” de B en [0, 1] × [0, 1]. Concluya que debe existir un segmento
de recta σ = {x} × [0, 1] en Bc . Use σ para probar que A − B ∼ A
(con [0, 1] × [0, 1] como A).
Solución: Puesto que A ∼ [0, 1] y [0, 1] ∼ [0, 1] × [0, 1], existe
una biyección f : A → [0, 1] × [0, 1]. El conjunto f(B) ⊆ [0, 1] ×
[0, 1] es contable. Sea p : [0, 1] × [0, 1] → [0, 1] la proyección sobre
la primera componente. Entonces p(f(B)) es también contable (si
g : N → f(B) es sobreyectiva, entonces p ◦ g : N → p(f(B)) es
también sobreyectiva). Puesto que [0, 1] no es contable, entonces
existe x ∈ [0, 1] − p(f(B)) y por lo tanto existe σ = {x} × [0, 1] en
f(B)c = [0, 1] × [0, 1] − f(B). De aquı́ que

A ∼ [0, 1] ∼ {x} × [0, 1]  [0, 1] × [0, 1] − f(B) ∼ A − B

donde [0, 1] ∼ {x}×[0, 1] porque ambos son intervalos, y {x}×[0, 1] 

[0, 1] × [0, 1] − f(B) por la inclusión. Por lo tanto A  A − B. Por
otra parte, A − B  A por la inclusión. De lo anterior, concluı́mos
que A ∼ A − B por el teorema de Bernstein-Cantor-Schroeder.

17. Sea A ⊆ R contable. Para cada α ∈ [0, 1] sea α + A = {α + x : x ∈ A}.

Pruebe que existe al menos un α ∈ [0, 1] tal que A y α + A son disjuntos.
Sugerencia: Para cuantos valores de α se puede tener A ∩ (α + A) 6= ∅ ?
(Note que el resultado de este ejercicio también se puede usar para evitar
el uso del Axioma de Elección en el problema anterior.)

18. Un conjunto X se dice Dedekind-infinito si existe una biyección f de X

a un subconjunto propio de X. Un conjunto es Dedekind-finito si no es
Dedekind-infinito. Pruebe que:

a) Todo conjunto contablemente infinito es Dedekind-infinito.

b) Si X contiene un conjunto contablemente infinito, entonces X es
Dedekind-infinito.

12
 c) Si X es Dedekind-infinito, entonces X contiene un conjunto conta-
blemente infinito. Sugerencia: Sea z ∈ X − f(X) y defina x0 = z,
x1 = f(x0 ), . . ., xn+1 = f(xn ), . . . (una pregunta del primer parcial
es útil para verificar que {x0 , x1 , x2 , . . .} es infinito).
d ) Si X y Y son Dedekind-finitos, entonces X ∪ Y es Dedekind finito.
Sugerencia: Use (c).

19. Una permutación de K es una función biyectiva K → K. Se puede definir

entonces el factorial de un cardinal κ como

κ! = |{f : f es una permutación de K}|,

donde K es un conjunto de cardinalidad κ. Pruebe que κ! está bien defi-

nida, es decir, κ! es independiente de la selección de K.

Solución: Sea BK = {f : f es una permutación de K}. Vamos a probar

que si K ∼ K 0 entonces BK ∼ BK 0 . Dada la biyección φ : K → K 0 definimos
la biyección Ψ : BK → BK 0 como

Ψ(f) = φ ◦ f ◦ φ−1 .

Ψ es inyectiva: Si Ψ(f) = Ψ(g) entonces φ ◦ f ◦ φ−1 = φ ◦ g ◦ φ−1 .

Componiendo con φ por la derecha, y con φ−1 por la izquierda, se obtiene
que f = g.
Ψ es sobreyectiva: Dada f 0 ∈ BK 0 , sea f = φ−1 ◦ f 0 ◦ φ. Es claro que f ∈ BK
y entonces

Ψ(f) = φ ◦ f ◦ φ−1 = φ ◦ (φ−1 ◦ f 0 ◦ φ) ◦ φ−1 = f 0 .

Concluı́mos que Ψ es una biyección, y por lo tanto BK ∼ BK 0 .

No se pedı́a en el enunciado, pero veamos que κ! = 2κ . Por una parte,

κ! ≤ κκ ≤ (2κ )κ = 2κ·κ = 2κ

donde la primera desigualdad es válida porque κκ es la cardinalidad de

KK , donde K es tal que |K| = κ (y BK ⊆ KK ). Por otra parte, sabemos que
K ∼ K0 ∪ K1 , donde K0 = K × {0} y K1 = K × {1} son dos copias disjuntas
de K (lo que se puede deducir de K ∼ K×K). Con esto podemos establecer
que
2K  BK0 ∪K1 (∗)

13
 con la función inyectiva F : 2K → BK0 ∪K1 definida de la siguiente manera:
si φ ∈ 2K entonces F(φ) es la permutación fφ de K0 ∪ K1 dada por, donde
k ∈ K y i es 0 ó 1,

(k, i) si φ(k) = 0
fφ ((k, i)) =
(k, 1 − i) si φ(k) = 1

(en palabras, (k, 0) y (k, 1) se intercambian sii φ(k) = 1). De (∗), puesto
que BK ∼ BK0 ∪K1 , se tiene que 2κ ≤ κ! y finalmente 2κ = κ!

20. Justifique la regla de exponentes para cardinales (κλ )µ = κλ·µ .

Solución: Sean K, L, M conjuntos con cardinalidades κ, λ, µ. Debemos

establecer una biyección

F : (KL )M → KL×M

Esta F se define de la siguiente manera: si φ ∈ (KL )M entonces es de la

forma φ : M → KL :

φ : M → KL
m 7→ φ(m)

donde
φ(m) : L → K
Entonces F(φ) es una función dada por

F(φ) : L × M → K
(`, m) 7→ φ(m)(`)

Verifiquemos:
Inyectividad de F: Sean φ, φ 0 ∈ (KL )M con φ 6= φ 0 . Entonces existe
m ∈ M tal que φ(m) 6= φ 0 (m). Y por lo tanto existe ` ∈ L tal que
φ(m)(`) 6= φ 0 (m)(`). Pero por definición esto significa que F(φ)(`, m) 6=
F(φ 0 )(`, m) y por lo tanto F(φ) 6= F(φ 0 ).
Sobreyectividad de F: Sea ψ ∈ KL×M . Definimos φ ∈ (KL )M como

φ(m) = ψ(·, m)

De aquı́ es fácil verificar que F(φ) = ψ:

F(φ)(`, m) = φ(m)(`) = ψ(`, m).

14
21. Use aritmética de cardinales para probar las siguientes igualdades (Nota:
en los tres primeros casos, el resultado es inmediato usando la propiedad
general de absorción κ + λ = κ · λ = máx(κ, λ)). Aquı́ se dan soluciones
alternativas donde el resultado se deduce de una cadena de desigualdades
ó igualdades utilizando ℵ0 · ℵ0 = ℵ0 y ℵ0 ≤ 2ℵ0 y propiedades básicas
de aritmética cardinal.):

a) ℵ0 + ℵ0 = ℵ0
Solución: De la cadena de desigualdades

ℵ0 = 0 + ℵ0 ≤ ℵ0 + ℵ0 = 2 · ℵ0 ≤ ℵ0 · ℵ0 = ℵ0

se tiene que ℵ0 ≤ ℵ0 + ℵ0 y también ℵ0 + ℵ0 ≤ ℵ0 , y por lo tanto

ℵ0 + ℵ0 = ℵ0 .
b) 2ℵ0 · 2ℵ0 = 2ℵ0
Solución: Usando (a),

2ℵ0 · 2ℵ0 = 2ℵ0 +ℵ0 = 2ℵ0

c) ℵ0 · 2ℵ0 = 2ℵ0
Solución: Usando (b),

2ℵ0 = 1 · 2ℵ0 ≤ ℵ0 · 2ℵ0 ≤ 2ℵ0 · 2ℵ0 = 2ℵ0

d ) ℵℵ
0 = 2
0 ℵ0

Solución:

2ℵ0 ≤ ℵℵ ℵ0 ℵ0
0 ≤ (2 )
0
≤ 2ℵ0 ·ℵ0 = 2ℵ0

22. Decida si es cierto para todos los cardinales κ, µ, λ (justifique):

a) si κ < µ entonces κ · λ < µ · λ

b) si κ · λ ≤ µ · λ entonces κ ≤ µ
∞
[
23. Determine la cardinalidad del conjunto C = 2In .
n=1

15
24. a) Pruebe directamente (usando el teorema de CBS) que |NN | = |2N |
(no use aritmética cardinal).
b) Pruebe que para cualquier conjunto A infinito |AA | = |2A | (aquı́ si
puede usar más maquinaria)
Solución: Sea κ el cardinal de A. Entonces
2κ ≤ κκ porque 2 ≤ κ y propiedad de desigualdad
≤ (2κ )κ porque κ < 2κ y propiedad de desigualdad
= 2κ·κ porque propiedad de potencias
= 2κ porque κ · κ = κ.
Por lo tanto 2κ = κκ (para ser más preciso, de las desigualdades
se tiene que 2κ ≤ κκ y también κκ ≤ 2κ , y de aquı́ que 2κ = κκ ,
por la antisimetrı́a de la relación ≤ de cardinales que se deduce del
teorema de Cantor-Berstein-Schroeder).
25. Pruebe que Z[X] = {an Xn + an−1 Xn−1 + · · · + a1 X + a0 | ai ∈ Z, an 6= 0}
es contablemente infinito.
Solución: Ver notas de Johany S.
26. Máximos locales. Sea f : R → R una función. Se dice que f tiene un
máximo local en x, si existe  > 0 tal que para todo y ∈ R tal que
0 < |y − x| <  se satisface f(y) < f(x). Pruebe que para toda f el
conjunto Mf = {x ∈ R : f tiene un máximo local en x} es contable.
Solución: Si f tiene un máximo local en x, entonces existe Nx ∈ N
tal que si y ∈ [x − 1/Nx , x + 1/Nx ] entonces f(y) < f(x) (esto por
propiedad de los reales). Si f tiene máximos locales en x1 y x2 y Nx1 =
Nx2 = N entonces |x1 − x2 | > 1/N porque de lo contrario f(x1 ) < f(x2 )
y f(x2 ) < f(x1 ) porque f tiene máximo local en ambos valores, lo cual es
una contradicción. Entonces para cada n ∈ N+ , el conjunto
Mn = {x ∈ R : f tiene máximo local en x y Nx = n}
es contable (porque para cada intervalo Jm,n = [m/n, (m+1)/n), m ∈ Z,
|Mn ∩ Jm,n | ≤ 1). Entonces
[
M = {x ∈ R : f tiene máximo local en x} = Mn
n≥1

es unión contable de conjuntos contables, y por tanto contable. (Pregunta:

El resultado general que dice que una unión contable de conjuntos con-
tables es contable requiere del axioma de elección. Se necesita realmente
en este caso ?)

16
27. Considere una colección C de cı́rculos disyuntos en R2 , ninguno de los
cuales es un punto. Más precisamente, para cada C ∈ C existe un centro
c ∈ R2 y un radio r ∈ R con r > 0 tal que C = {x ∈ R2 | kx − ck ≤ r}, y
para C, C 0 ∈ C diferentes se tiene C ∩ C 0 = ∅. Probar que C es contable.

Solución: El cı́rculo C = {x ∈ R2 | kx − ck ≤ r}, con c = (c1 , c2 )

contiene el cuadrado
√ √
RC = {x ∈ R2 : x = (x1 , x2 ), |x1 − c1 | ≤ r/ 2, |x2 − c2 | ≤ r/ 2}
√ √
= {x1 ∈ R : |x1 − c1 | ≤ r/ 2} × {x2 ∈ R : |x2 − c2 | ≤ r/ 2}

(Es fácil ver que RC ⊆ C: si x ∈ RC se tiene que

r2 r2
kx − ck2 = (x1 − c1 )2 + (x2 − c2 )2 ≤ + = r2 .)
2 2
Como está expresado arriba, RC es un producto de intervalos. Ya que
cada intervalo contiene un número racional, el producto RC y por tanto
C contiene una pareja (qC,1 , qC,2 ) de números racionales.
Esto nos permite definir una función inyectiva f : C → Q × Q dada por

C 7→ (qC,1 , qC,2 )

(f es inyectiva porque los cı́rculos son disjuntos.) Por lo tanto

C  Q × Q.

Puesto que Q × Q ∼ N, concluı́mos que C es contable.

(Como en el caso de intervalos en R, la selección de una pareja (qC,1 , qC,2 )
en cada cı́rculo C no requiere del axioma de elección. La forma más fácil
de evitarlo es tener en cuenta que Q × Q ∼ N implica la existencia de
una biyección φ : Q × Q → N. Por lo tanto, el conjunto φ(C ∩ (Q × Q))
es un subconjunto no vacı́o de N y por el principio del buen orden existe
un elemento mı́nimo. Ası́, para el cı́rculo C, escogemos el par (q1 , q2 ) ∈
C ∩ (Q × Q) tal que φ(q1 , q2 ) es mı́nimo.)

28. Se dice que un conjunto A es T-finito si para cada familia no vacı́a T ⊆

P(A) existe un B ∈ T tal que no existe un C ∈ T con B ( C (es decir, B
es maximal). Por otra parte, se dice que A es T-infinito si no es T-finito.

(i) Si A es finito entonces es T-finito.

(ii) Si A es infinito entonces A es T-infinito.

17
29. Sea A ⊆ R+ (reales positivos) tal que P
para algún b ∈ R+ y cualquier
subconjunto finito B de A, se cumple a∈B a ≤ b. Pruebe que A es
contable. Sugerencia: Para n ∈ N, cuántos elementos de A pueden ser
mayores que b/n ?

Solución: Sea An = {x ∈ A : x > b/n}. Se tiene que |An | ≤ n, porque

de lo contrario, si |An | > n, entonces la suma de un subconjunto de An
con n + 1 elementos serı́a mayor que b. Pero
[
A= An
n≥1

por propiedad de los reales. Ya que A es una unión contable de conjuntos

finitos, se deduce que A es contable. (Pregunta: El resultado general que
dice que una unión contable de conjuntos contables es contable requiere
del axioma de elección. Se necesita realmente en este caso ?)

30. Sea R una relación sobre R tal que para x, y ∈ R, xRy sii x − y ∈ Q.
R es una relación de equivalencia. Cuántas clases de equivalencia hay ?
Cuántos elementos hay en cada clase ? (aquı́, “cuántos” quiere decir cual
es la cardinalidad del conjunto correspondiente)

Solución: Sea x ∈ R. La clase de equivalencia de x es

Cx = {y ∈ R : x − y ∈ Q} = {x + q : q ∈ Q}

Por lo tanto Cx ∼ Q ∼ N. Puesto que |R| = 2ℵ0 , se concluye que la

cardinalidad del conjunto de clases de equivalencia

C = {Cx : x ∈ R}

es 2ℵ0 . Esto lo podemos justificar con la propiedad de absorción: Sea

κ = |C|. Entonces |R| = 2ℵ0 = κ · ℵ0 . Si κ < 2ℵ0 , entonces

κ · ℵ0 = máx(κ, ℵ0 ) < 2ℵ0

lo que es una contradicción. Por lo tanto se debe tener que κ = 2ℵ0 .

(Pregunta: La propiedad de absorción es un resultado que requiere en
general el axioma de elección. Se puede probar que |C| = 2ℵ0 en forma
más directa ?)

31. En la prueba de que A × A ∼ A, se construye el siguiente conjunto:

H = {φ | B ⊆ A, φ : B × B → B es una biyección}.

18
 Para usar el lema S que dada una cadena C ⊆ H,
S de Zorn, se necesita probar
S C ∈ H. Ya se sabeSque C es una función inyectiva.
se tiene que S Sea
A0 = ran( C). Pruebe que dom( C) = A0 ×A0 (esto implica C ∈ H).

Solución: (Aclaración: En el libro de Enderton se inlcuye explı́citamente

el conjunto vacı́o ∅ en H. Esto se debe a que allá, una cadena puede ser
vacı́a, y por lo tanto su unión es vacı́a. En la versión que nosotros seguimos
(notas de Johany S.), una cadena es no vacı́a por definición.)
S
La verificación de dom( C) = A0 × A0 se hace probando las dos conte-
nencias:
S S
dom( C) ⊆ A0 × A0 : Sea α ∈ dom( C). Entonces, existe f ∈ C tal
que α ∈ dom(f). Pero dom(f) es de la forma B × B para algún B ⊆ A;
por lo tanto, α = (x, y) para x, y ∈ B. Puesto que f : B × B → SB es
una biyección, se tiene que x, y ∈ ran(f) y por lo tanto x, y ∈ ran( C).
Concluı́mos que α = (x, y) ∈ A0 × A0 .
S S
dom( C) ⊇ A0 ×A0 : Sea α = (x, y) ∈ A0 ×A0 . Entonces x, y ∈ ran( C),
y por lo tanto existen f, g ∈ C tal que x ∈ ran(f) y y ∈ ran(g). Puesto que
C es una cadena, f ⊆ g ó g ⊆ f. Sin pérdida de generalidad, suponemos
que f ⊆ g (el otro caso es similar), y por lo tanto x, y ∈ ran(g). Para g
existe B ⊆ A tal que g : B × B → B es una biyección. Ası́ que x, y ∈ B y
por lo tanto (x, y) ∈ dom(g) = B × B. Finalmente, entonces α = (x, y) ∈
dom(C).

32. Pruebe que si A es infinito, entonces (A × {0}) ∪ (A × {1}) ∼ A. Puede

usar que A × A ∼ A, pero no puede usar aritmética cardinal (puede usar,
por ejemplo, el teorema de Cantor-Bernstein-Schroeder).

Solución: Puesto que A es infinito, existen elementos a, b ∈ A diferen-

tes. Entonces

(A × {0}) ∪ (A × {1}) ∼ (A × {a}) ∪ (A × {b})  A × A ∼ A

(donde  se deduce de la inclusión). Por otra parte, es inmediato que

A  (A × {0}) ∪ (A × {1}).

Por lo tanto, por el teorema de CBS, se deduce que (A×{0})∪(A×{1}) ∼ A.

(Serı́a esencialmente lo mismo usando aritmética cardinal.)

33. Conexidad poligonal. Un subconjunto A de R2 se dice poligonalmente

conexo si para todo x, y ∈ A existe una curva poligonal γ en A con
terminales x y y (una curva poligonal es la imagen de una función f :
[0, 1] → R2 tal que existen valores 0 = x0 < x1 < x2 < · · · < xk−1 <

19
 xk = 1 en [0, 1] y puntos p0 , p1 , . . . , pk en R2 tal que f(xi ) = pi y en el
intervalo [xi , xi+1 ] la imagen de f es el segmento de recta entre los puntos
pi y pi+1 ; p0 y pk son los terminales de γ). Pruebe que si B ⊆ R2 es
contable, entonces A = R2 − B es poligonalmente conexo.
Solución: Sin pérdida de generalidad, podemos asumir que (−1, 0), (1, 0) 6∈
B y determinamos una curva poligonal en A = R2 − B con terminales
(−1, 0) y (1, 0) (para cualquier B, y puntos x0 , x1 6∈ B siempre se puede
llegar a la situación asumida con una rotación y una translación). Para
t ∈ [0, 1] sea γt el camino poligonal que consiste de los dos segmentos de
(−1, 0) a (0, t) y de (0, t) a (1, 0). Estos γt son disjuntos excepto por los
terminales, y además el conjunto [0, 1] de posibles ı́ndices t no es contable.
Pero entonces
C = {t ∈ [0, 1] : B ∩ γt 6= ∅}
es contable por ser B contable (si se quiere ser más preciso, si f : B → N
es inyectiva, entonces g : C → N dada por
g(t) = mı́n {n ∈ N : n ∈ ran(f), f−1 (n) ∈ γt }
también lo es; recuerde que la existencia de una tal función inyectiva es
una de las condiciones equivalentes para que un conjunto sea contable).
Por lo tanto existe t ∈ [0, 1] tal que B ∩ γt = ∅.
34. En este ejercicio usamos la representación decimal que termina en 9’s (y
no la que termina en 0’s, cuando ambas existen). Justifique que la función
ilustrada en el siguiente ejemplo es una biyección f : (0, 1]×(0, 1] → (0, 1]:
f(0 · 1 4 003 01 2 3 00001 05 1 1 · · · , 0 · 3 3 00007 9 001 5 9 0005 2 · · ·) =
0 · 1 3 4 3 003 00007 01 9 2 001 3 5 00001 9 05 0005 1 2 1 · · ·
Se intercalan las representaciones decimales, pero agrupando los ceros
con el siguiente dı́gito que no es cero.
Solución: Puesto que por definición de f, todo grupo de 0’s consecuti-
vos se agrupa con el siguiente dı́gito no nulo, entonces la función inversa
g se define en la forma obvia basándose en esos grupos. Siendo un poco
más preciso, dado α ∈ (0, 1] en representación decimal, el primer grupo
de 0’s y un no cero en α es el primer grupo de dı́gitos en la representación
del primer número α1 , el siguiente tal grupo en α es el primer grupo de
dı́gitos en la representación del segundo número α2 ; procediendo ası́ suce-
sivamente en forma alternada se obtienen las representaciones decimales
de α1 y α2 y entonces g(α) = (α1 , α2 ). Por las definiciones es claro que
f(g(α)) = α y g(f(α1 , α2 )) = (α1 , α2 ). Por lo tanto f es una biyección.
(Note que es importante que se trabaja en (0, 1] y se usa la representación
que termina en 9’s.)

20