Feeds:
Entradas
Comentarios

Archive for 5/03/15

En la entrada anterior hice referencia a la definición de Cardinalidad de un conjunto. Hoy nos dedicaremos a hablar de aquellos conjuntos que tienen  la misma cardinalidad que el conjunto de los números naturales.

Un conjunto A es numerable si \mathbb{N}\sim A. Un conjunto infinito que no es numerable se llama conjunto no numerable.

Cabe citar que mucha literatura se refiere a los conjuntos que están en correspondencia uno a uno con el conjunto de los números naturales como “infinitos” numerables, de modo que los conjuntos finitos son considerados también numerables. No hilaremos tan fino aquí, al menos por el momento.

Por ejemplo, el conjunto E de todos los números enteros pares así como \mathbb{Z} son conjuntos numerables. Poner un conjunto en una correspondencia 1-1 con \mathbb{N} significa poner todos los elementos en una infinitamente larga lista o sucesión. Es fácil ver que esto es sumamente sencillo de hacer para E (verdad?). Una pregunta natural que surge es si todos los conjuntos infinitos son numerables. Dado un conjunto infinito como \mathbb{Q} o \mathbb{R}, podría parecer como si, con la inteligencia suficiente, debiéramos ser capaces de disponer todos los elementos de nuestro conjunto en una sola lista (es decir, en una correspondencia uno a uno con \mathbb{N}). Después de todo, esta lista es infinitamente larga así que debe haber un montón de “lugares”. Pero, por desgracia, como señala Hardy, “El tema [de la matemática] es el más curioso de todos –no hay ninguno en el que la verdad juegue tales bromas extrañas.”


Teorema. El conjunto \mathbb{Q} es numerable.

Dem. Para cada n\in\mathbb{N}, sea A_{n} el conjunto dado por

A_{n}=\left\{\pm\frac{p}{q}:p,q\in\mathbb{N}\text{ are in lowest terms con }p+q=n\right\}.

Algunos pocos, los primeros, de estos conjuntos lucen como

A_{1}=\left\{\frac{0}{1}\right\},A_{2}=\left\{\frac{1}{1},\frac{-1}{1}\right\},A_{3}=\left\{\frac{1}{2},\frac{-1}{2},\frac{2}{1},\frac{-2}{1}\right\}

A_{4}=\left\{\frac{1}{3},\frac{-1}{3},\frac{3}{1},\frac{-3}{1}\right\}

y

A_{5}=\left\{\frac{1}{4},\frac{-1}{4},\frac{2}{3},\frac{-2}{3},\frac{3}{2},\frac{-3}{2},\frac{4}{1},\frac{-4}{1}\right\}.

La observación clave es que cada A_{n} es finito y todo número racional aparece exactamente en uno de estos conjuntos. Nuestra correspondencia 1-1 con \mathbb{N} es entonces alcanzada listando de manera consecutiva los elementos en cada A_{n}.

Es cierto, el lector atento estará pensando con razón que escribir una fórmula explícita para esta correspondencia sería una tarea difícil, y tratar de hacerlo no es el mejor uso del tiempo. Lo que importa es ver por qué cada número racional aparece en la correspondencia exactamente una vez. Por ejemplo, para 22/7, tenemos que 22/7\in A_{29}. Debido a que el conjunto de elementos en A_{1},\ldots,A_{28} es finito, podemos estar seguros de que 22/7 con el tiempo va a incluirse en la sucesión. El hecho de que esta línea de razonamiento se aplica a cualquier número p/q racional es nuestra prueba de que la correspondencia es sobre. Para verificar que es 1-1, se observa que los conjuntos A_{n} se construyeron disjuntos de modo que ningún número racional aparece dos veces. \clubsuit


Teorema. El conjunto \mathbb{R} es no numerable.

Dem. Supongamos que sí existe una función 1-1 y sobre f:\mathbb{N}\rightarrow\mathbb{R}. Una vez más, lo que esto sugiere es que es posible enumerar los elementos de \mathbb{R}. Si hacemos x_{1}=f(1), x_{2}=f(2), y así sucesivamente, entonces nuestra suposición de que f es sobre significa que podemos escribir

\mathbb{R}=\left\{x_{1},x_{2},x_{3},x_{4},\ldots\right\}

y estar seguros de que todo número real aparece en algún lugar de la lista. Ahora usaremos el Principio de los intervalos encajados para producir un número real que no está allí.

Sea I_{1} un intervalo cerrado que no contiene a x_{1}. A continuación, sea I_{2} un intervalo cerrado, contenido en I_{1}, que no contiene a x_{2}. La existencia de un I_{2} de este tipo es fácil de verificar. Ciertamente I_{1} contiene dos intervalos cerrados disjuntos más pequeños, y x_{2} sólo puede estar en uno de ellos. En general, dado un intervalo de I_{n}, construimos I_{n+1} de modo que

  • I_{n+1}\subseteq I_{n}
  • x_{n+1}\notin I_{n+1}

Ahora consideramos la intersección \bigcap^{\infty}_{n=1}I_{n}. Si x_{n_{0}} es algún número real de la lista anterior, entonces tenemos x_{n_{0}}\notin I_{n_{0}}, y se deduce que

x_{n_{0}}\notin\bigcap^{\infty}_{n=1}I_{n}.

Ahora, estamos asumiendo que la lista anterior contiene todos los números reales, y esto lleva a la conclusión de que

\bigcap^{\infty}_{n=1}I_{n}=\emptyset.

Sin embargo, el Principio de los intervalos encajados afirma que \bigcap^{\infty}_{n=1}I_{n}\neq\emptyset. Así, existe al menos un x\in\bigcap^{\infty}_{n=1}I_{n} que, en consecuencia, no se puede estar en la lista dada arriba. Esta contradicción significa que es imposible una enumeración de \mathbb{R}, y llegamos a la conclusión de que \mathbb{R} es un conjunto no numerable. \clubsuit


Pero… ¿qué es exactamente lo que deberíamos hacer con este descubrimiento? Es un ejercicio importante demostrar que cualquier subconjunto de un conjunto numerable debe ser numerable o finito, lo que no debería sorprender demasiado al lector. Si un conjunto se puede organizar en una sola lista, entonces eliminar algunos elementos de esta lista da por resultado otra lista (más corta, y potencialmente con un final). Esto significa que los conjuntos numerables son el tipo más pequeño de conjunto infinito. Cualquier cosa más pequeña es aún numerable ó finita.

La fuerza del Teorema anterior es que la cardinalidad de \mathbb{R} es, hablando informalmente, un tipo más grande de infinitud. Los números reales superan en número a los números naturales por lo que no podemos mapear a \mathbb{N} sobre \mathbb{R}. No importa cómo lo intentemos, siempre sobran números reales. El conjunto \mathbb{Q}, por otro lado, es numerable. ¿Qué implica esto acerca del conjunto \mathbb{I} de los números irracionales? Al imitar la demostración de que \mathbb{N}\sim\mathbb{Z}, podemos demostrar que la unión de dos conjuntos numerables debe ser numerable. Debido a que \mathbb{R}=\mathbb{Q}\cup\mathbb{I}, se deduce que no puede ser numerable porque de lo contrario lo sería \mathbb{R}. La conclusión ineludible es que, a pesar de que hemos encontrado tan pocos de ellos, los números irracionales forman un subconjunto mucho mayor que \mathbb{Q} de \mathbb{R}.

Por último, los dejo una vez más con el Dr. Paenza pensando acerca de los conjuntos infinitos…


Referencias bibliográficas:

  • Abbott, Stephen (2010) Understanding Analysis. Springer.
Anuncios

Read Full Post »