Conjuntos no contables
Jerson Borja
Universidad de Córdoba
Mostraremos la existencia de algunos conjuntos no contables.
Uno de nuestros principales resultados es mostrar que el conjunto
de los números reales R no es contable.
Ejemplo (Un conjunto no contable)
Sea E el conjunto de todas las enumeraciones de {0, 1}.
Es fácil mostrar que E es infinito. Para esto, mostramos que E
contiene un subconjunto numerable. Sea k ∈ N fijo. Consideremos
la enumeración
fk = ⟨0, 0, . . . , 0, 1, 1, . . .⟩
donde los primeros k elementos en la enumeración son ceros, y de
ahı́ en adelante todos son unos.
Es claro que por cada k ∈ N tenemos una enumeración diferente.
El conjunto {fk ∶ k ∈ N} es, por lo tanto, un subconjunto
numerable de E . Ası́ hemos mostrado que E es infinito.
En realidad queremos mostrar que E no es contable. Haremos
esto por reducción al absurdo.
Supongamos que E es contable y sea f ∶ N → E una enumeración
de E , digamos que
f = ⟨f1 , f2 , f3 , . . . , fn , . . .⟩.
Cada fi es una enumeración de {0, 1}. Representamos estas
enumeraciones en el siguiente diagrama:
f1 = ⟨a11 , a12 , a13 , . . . , a1n , . . .⟩
f2 = ⟨a21 , a22 , a23 , . . . , a2n , . . .⟩
f3 = ⟨a31 , a32 , a33 , . . . , a3n , . . .⟩
⋮
fn = ⟨an1 , an2 , an3 , . . . , ann , . . .⟩
⋮
En la enumeración f = ⟨f1 , f2 , f3 , . . . , fn , . . .⟩, cada elemento de E ,
es decir, cada enumeración de {0, 1}, debe aparecer por lo menos
una vez.
Para llegar a una contradicción, vamos a construir una enumeración
de {0, 1} que no aparece listada en la lista ⟨f1 , f2 , f3 , . . . , fn , . . .⟩.
Definamos g ∶ N → {0, 1} de la siguiente manera:
1, si fn (n) = 0;
g (n) = {
0, si fn (n) = 1.
Ası́, el valor de g (n) es diferente del valor de fn (n) (marcado en
negrilla en el diagrama) para todo n ∈ N.
Ahora, g es una enumeración de {0, 1}, es decir, g es un elemento
de E .
Luego g debe aparecer al menos una vez en la enumeración
f = ⟨f1 , f2 , f3 , . . . , fn , . . .⟩, lo que quiere decir que existe nk ∈ N tal
que fk = g .
Si vemos a fk y g como funciones de N en {0, 1}, resulta que
fk (n) = g (n) para todo n ∈ N; en particular, fk (k) = g (k), lo cual
es una contradicción.
Esto termina la demostración, por reducción al absurdo, de que E
no es contable.
El método para construir la función g en el ejemplo anterior es
conocido como método de la diagonal de Cantor.
Lema
Si A es un conjunto, entonces no existe ninguna función
sobreyectiva f ∶ A → P(A).
Demostración.
Sea f ∶ A → P(A) una función arbitraria. Veamos que f no es
sobreyectiva.
Para esto exhibiremos un elemento X ∈ P(A) que no tiene
preimagen bajo f .
En efecto, sea
X = {a ∈ A ∶ a ∉ f (a)}.
Afirmamos que X no tiene preimagen bajo f . Para demostrar esto,
por contradicción, supongamos que X sı́ tiene preimagen bajo f , es
decir, que existe a0 ∈ A tal que f (a0 ) = X .
Continuación de la demostración.
Tenemos dos casos, dependiendo de si a0 está en X o no (en cada
caso llegaremos a una contradicción).
Caso 1. a0 ∈ X . En este caso, como a0 ∈ X , tenemos que
a0 ∉ f (a0 ), esto es, a0 ∉ X , absurdo.
Caso 2. a0 ∉ X . En este caso, a0 ∈ f (a0 ), esto es, a0 ∈ X ,
absurdo.
Esto termina la prueba de que en realidad X no tiene preimagen
bajo f y ası́, f no es sobreyectiva.
Teorema
Si A es infinito, entonces P(A) no es contable.
Demostración.
Sea a0 ∈ A fijo y definamos f ∶ P(A) → A como sigue:
a, si X = {a}, donde a ∈ A;
f (X ) = {
a0 , otro caso.
Esta función f es sobreyectiva.
Supongamos que P(A) es contable.
Entonces existe una función sobreyectiva g ∶ N → P(A). Luego, la
función compuesta f ◦ g ∶ N → A es sobreyectiva.
Ası́, A es contable, y como A es infinito, A es numerable. Por lo
tanto existe una función biyectiva h ∶ A → N.
Se sigue que la función h∗ ∶ P(A) → P(N) dada por
h∗ (X ) = h(X ) para todo X ∈ P(A), es biyectiva (verificarlo).
Continuación de la demostración.
Resulta luego que la función compuesta h∗ ◦ g ∶ N → P(N) es
sobreyectiva, lo que contradice el lema anterior.
Nuestro siguiente objetivo es demostrar que R no es contable.
Para eso usaremos una propiedad importante de R llamada la
propiedad de los intervalos encajados de Cantor.
Teorema (Propiedad de los intervalos encajados de Cantor)
Sea {In }n∈N una colección de intervalos cerrados no vacı́os en R tal
que
I1 ⊇ I2 ⊇ I3 ⊇ ⋯ ⊇ In ⊇ In+1 ⊇ ⋯
∞
Entonces ⋂n=1 In ≠ ∅.
Demostración.
Para cada n ∈ N sea In = [an , bn ], donde an ≤ bn .
La condición In+1 ⊆ In implica que
an ≤ an+1 ≤ bn+1 ≤ bn
para todo n ∈ N.
Usando la desigualdad anterior e inducción se puede probar lo
siguiente (verificarlo):
am ≤ bn
para todo n, m ∈ N.
Continuación de la demostración.
Ahora consideremos el conjunto A = {am ∶ m ∈ N}.
Tomando n = 1 en la desigualdad anterior, obtenemos que am ≤ b1 ,
para todo m ∈ N, lo que muestra que b1 es cota superior para A.
Por el axioma de completez, existe a = sup A.
∞
Afirmamos que a ∈ ⋂n=1 In . En efecto, sea n ∈ N fijo.
Entonces am ≤ bn para todo m ∈ N, es decir, bn es cota superior
de A, por lo que se sigue que a ≤ bn . Además, an ≤ a, ası́ que
a ∈ In = [an , bn ].
Esto muestra que a ∈ In para todo n ∈ N, lo que termina la
prueba.
Lema
Sean a, b ∈ R con a < b y x ∈ R. Entonces existe un intervalo
cerrado [c, d] ⊆ [a, b] con c < d tal que x ∉ [c, d]
Demostración.
Tenemos tres casos.
Caso 1. x ∉ [a, b].
x a b
En este caso podemos tomar c = a y d = b.
Continuación de la demostración.
Caso 2. x = b.
a d x =b
En este caso podemos tomar c = a y d = (a + b)/2.
Caso 3. a ≤ x < b.
a x c d b
En este caso podemos tomar c = (x + b)/2 y d = (c + b)/2.
Teorema
El intervalo [0, 1] no es contable. En consecuencia, R no es
contable.
Demostración.
Supongamos que [0, 1] es contable.
Como [0, 1] es infinito, [0, 1] es numerable, ası́ que podemos
representar [0, 1] en la forma
[0, 1] = {a1 , a2 , a3 , . . . , an , . . .}
donde cada elemento de [0, 1] aparece exactamente una vez en la
lista de la derecha.
Usamos el lema anterior para construir una sucesión de intervalos
cerrados encajados {In }n∈N , inductivamente, como sigue:
Continuación de la demostración.
1. Tomamos I1 = [0, 1].
2. Suponiendo que In ha sido definido, aplicando el lema
anterior, existe un intervalo cerrado que llamaremos In+1 tal
que In+1 ⊆ In y an ∉ In+1 .
Ası́, por el principio de inducción matemática, tenemos definida
una colección de intervalos cerrados no vacı́os {In }n∈N tales que
In+1 ⊆ In para todo n ∈ N.
Por la propiedad de los intervalos encajados de Cantor, existe
∞
a ∈ ⋂n=1 In .
Ahora, como a ∈ [0, 1], resulta que a = ak para algún k ∈ N; pero
por la forma en que se construyeron los intervalos In , se tiene que
∞
a = ak ∉ Ik+1 , pero esto significa que a ∉ ⋂n=1 In , una
contradicción.
Continuación de la demostración.
Hemos probado que [0, 1] no es contable. Como R ∼ [0, 1],
resulta que R no es contable.
El conjunto de los números irracionales I = R \ Q no es contable,
pues de lo contrario, R = I ∪ Q serı́a contable.
