Conjuntos numerables

La numerabilidad de un conjunto es una especie de equivalente del tamaño de los conjuntos, porque en los conjuntos infinitos no se puede contar el número de elementos, ya que el número de elementos es, sorprendentemente… infinito. Al tamaño de un conjunto lo llamamos también cardinalidad.

Tamaño de un conjunto infinito

Determinar el tamaño de un conjunto finito es sencillo: contamos sus elementos. Así, el conjunto M = {a, b, c, d, e} tiene tamaño 5, y lo escribimos |M| = 5.

En los conjuntos infinitos la situación es bastante más complicada. ¿Cómo podríamos comparar el tamaño de conjuntos infinitos? ¿Es siquiera posible, o todos los conjuntos infinitos son «igual de grandes»?

Como ejemplo, tomemos el conjunto de los números naturales y el conjunto de los números naturales pares. Tenemos así los conjuntos ℕ = {1, 2, 3, 4, 5, 6, …} y S = {2, 4, 6, …}. Nos entran ganas de decir que el conjunto de los números naturales es mayor que el de los pares, porque los naturales contienen todos los números pares y, además, algunos elementos más —los impares—.

Podríamos escribir, entonces, que se cumple S ⊂ ℕ: el conjunto S es un subconjunto propio del conjunto ℕ. Y podríamos decir que, si S ⊂ ℕ, el conjunto ℕ es mayor —contiene, al fin y al cabo, más elementos que el conjunto S—.

Una de las razones por las que no podemos medir los conjuntos con la relación de subconjunto es que los conjuntos pueden tener distinto tamaño aunque ninguno sea subconjunto del otro. Se puede ver incluso con conjuntos finitos: A = {1, 3, 4, 9} y B = {b, u, r, z, m}. Se cumple |A| = 4 y |B| = 5. El conjunto B es mayor que el conjunto A y, sin embargo, no se cumple A ⊂ B. En el caso de los conjuntos infinitos lo vemos con los números pares y los impares: ninguno de los dos conjuntos es subconjunto del otro.

La relación de subconjunto no es, pues, un candidato ideal para decidir si un conjunto es mayor que otro.

Biyección

Probemos otro enfoque. Tenemos dos conjuntos, A y B. Podemos decir que tienen el mismo tamaño si entre ellos existe una aplicación biyectiva. ¿Qué significa esto? Que tomamos un elemento del conjunto A, un elemento del conjunto B y formamos la pareja (a, b). Quitamos esos elementos de los conjuntos y seguimos. Si conseguimos «vaciar» los dos conjuntos, hemos encontrado una aplicación biyectiva.

Un ejemplo con conjuntos finitos: A = {a, b, c} y B = {1, 2, 3}. La primera pareja podría ser (a, 1), la siguiente (b, 2) y por último (c, 3). Hemos agotado todos los elementos de ambos conjuntos, así que hemos encontrado una aplicación biyectiva. Lo importante es que esta no es la única aplicación biyectiva. También esta es una solución válida: (a, 3), (b, 1), (c, 2).

Con los conjuntos infinitos la cosa ya se pone más interesante. Probemos con los números naturales impares y pares. La intuición nos dice que debería haber tantos de unos como de otros. Vamos a comprobarlo. Tomamos el primer número impar y lo asignamos al primer número par: (1, 2). Después, el segundo impar y el segundo par: (3, 4). Y así sucesivamente. Obtenemos así las parejas (1, 2), (3, 4), (5, 6), (7, 8), … Podríamos escribir que cada número impar l se asigna al número par l + 1 y que cada número par s es la imagen del impar s − 1. Para cada número impar y para cada número par tenemos, pues, una pareja que contiene ese número. Los conjuntos de los números impares y de los pares son, por tanto, igual de grandes.

Números pares frente a naturales

Ahora probemos el mismo procedimiento y comparemos el conjunto de los números naturales con el de los pares. Tenemos los conjuntos ℕ = {1, 2, 3, 4, 5, 6, …} y S = {2, 4, 6, …}. Intuitivamente esperamos que el conjunto de los naturales sea mayor.

Intentemos, sin embargo, encontrar la aplicación biyectiva. Podemos decir que cada número natural n se asigna a su doble, a 2n. Así obtenemos las parejas (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Para cada número natural n tenemos la pareja (n, 2n) y para cada número par s tenemos la pareja (s/2, s). Hemos encontrado una aplicación biyectiva: el conjunto de los números pares y el de los naturales son igual de grandes, tienen la misma cardinalidad.

Esto puede parecer confuso, porque los números naturales contienen, al fin y al cabo, más elementos que los pares. Los naturales contienen todos los números pares y, además, todos los impares. Sin embargo, somos capaces de encontrar una biyección, así que los dos conjuntos son igual de grandes.

Comparación con los números naturales

Los números naturales determinan, en realidad, el tamaño más pequeño de un conjunto infinito. A menudo se puede averiguar con bastante facilidad si otro conjunto tiene el mismo tamaño que el de los números naturales: basta encontrar una biyección con los números naturales, lo que en la práctica significa que basta con que podamos numerar, ordenar, los elementos de nuestro conjunto M.

Es decir, si somos capaces de ordenar los elementos de un conjunto de modo que podamos decidir cuál es el primero, cuál el segundo, el tercero, el cuarto, el décimo, etc., entonces el conjunto es igual de grande que ℕ. De un conjunto así decimos que es numerable.

Fácilmente vemos que los números naturales pares e impares son numerables, porque sabemos decir cuál es el primer, el segundo, el tercer, etc., número par o impar. ¿Y los números enteros pares? Es decir, el conjunto S = {…, −4, −2, 0, 2, 4, …}. ¿Somos capaces de ordenarlos? Sí: basta tomar el mismo orden que antes y, justo después de cada número par positivo, escribir su versión negativa: S = {0, 2, −2, 4, −4, 6, −6, …}. De manera parecida se hace, por ejemplo, con los números enteros.

Tamaño de los números racionales

Un ejemplo más interesante son los números racionales, las fracciones. ¿Somos capaces de ordenarlos? Sí, pero será un poco más complicado. Construimos una tabla con infinitas filas y columnas. En cada casilla habrá una fracción. En la columna n y la fila m tendremos la fracción n/m. Es decir, en la 1.ª columna y la 2.ª fila tenemos $\frac{1}{2}$, y en la tercera columna y la cuarta fila tenemos 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

¿Cómo ordenamos ahora estos números, cómo los numeramos? No podemos numerarlos por filas ni por columnas, porque nos ahogaríamos enseguida en esa fila o columna. En su lugar tomamos los números por diagonales: (primera diagonal:) 1/1, (segunda diagonal:) 2/1, 1/2, (tercera diagonal:) 3/1, 2/2, 1/3, (cuarta diagonal:) 4/1, 3/2, 2/3, 1/4, … Todavía hay muchas fracciones repetidas, pero eso no importa. Lo que importa más es que faltan los números negativos. Eso se arregla fácilmente: cada vez que escribimos una fracción, colocamos justo detrás su versión negativa. Y entonces solo nos falta el cero al principio del todo. Y ya está: tenemos todos los números racionales en una sucesión.

En conjunto obtenemos la sucesión: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Tamaño de los números reales

¿Son los números reales igual de numerosos que los naturales? La decisión será todavía más complicada que en el caso de los números racionales. Haremos una demostración por reducción al absurdo. Supongamos que los números reales son numerables y que existe una aplicación biyectiva con los números naturales. Supongamos, pues, que se pueden ordenar. Y digamos que la siguiente asignación es ese orden:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

En la tabla están los siete primeros números reales de nuestro orden. Por supuesto, este orden puede ser cualquiera; no tiene por qué estar ordenado según el tamaño de los números.

Según la hipótesis, en esta tabla infinita están ordenados todos los números reales. (La tabla es, de nuevo, infinita; aquí solo están las siete primeras entradas.) Ahora intentaremos encontrar o construir un número que sea real, pero que no figure en esta tabla. Si encontramos un número así, tendremos una contradicción con que en la tabla estén todos los números reales, de lo que podremos deducir que el conjunto de los números reales no es numerable.

Ese número que no está en la tabla lo construimos así:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Empezamos escribiendo 0,… Este es el aspecto que tendrá al principio nuestro nuevo número real. En la primera cifra decimal pondremos una cifra que no sea la que está en la primera posición del primer número real de nuestro orden (en la tabla está resaltada con un recuadro). Ahí está la cifra 3, así que elegimos, por ejemplo, 1 y obtenemos el número 0,1…

Continuamos. En el segundo lugar pondremos una cifra que no sea la que está en el segundo lugar del segundo número real. Ahí hay un 9, así que, por ejemplo, 2. Obtenemos el número 0,12… En el tercer lugar pondremos una cifra distinta de la tercera cifra del tercer número real. Ahí hay un 3, así que elegimos, por ejemplo, 7. Obtenemos 0, 127…

Y así sucesivamente. En la posición n del nuevo número habrá siempre una cifra distinta de la cifra que está en la posición n del n-ésimo número de nuestro orden.

¿Qué conseguimos con esto? Conseguimos un número que se diferencia de todos los números de nuestro orden como mínimo en una cifra. Tomemos el último resultado provisional: 0,127… Este número se diferencia con seguridad del primer número de nuestro orden al menos en la primera cifra, porque lo hemos construido así. Del segundo número se diferencia al menos en la segunda cifra. Del tercero, en la tercera cifra. En general, este nuevo número se diferencia del número que ocupa el lugar n en el orden al menos en la cifra de la posición n.

Este número recién construido no lo encontraremos, por tanto, en la tabla que debía simbolizar la biyección entre los números naturales y los números reales. Los números reales son, pues, más numerosos que los naturales. Los números reales no son numerables, son no numerables.