Conjuntos numerables | Blog de Matemática y TIC's

Posts Tagged ‘Conjuntos numerables’

Conjuntos potencia y Teorema de Cantor

Posted in Análisis Real, Producción propia, tagged Cardinalidad de conjuntos, Conjunto potencia, Conjuntos no numerables, Conjuntos numerables, Diagonalización de Cantor, Hipótesis del continuo, Teorema de Cantor, Teorema de Schröder-Bernstein on 17 marzo 2015| 1 Comment »

Dado un conjunto $A$ , el conjunto potencia $P(A)$ se refiere a la colección de todos los subconjuntos de $A$ . Es importante entender que $P(A)$ es en sí mismo considerado un conjunto cuyos elementos son los distintos subconjuntos posibles de $A$ .

Teorema de Cantor. Dado un conjunto $A$ , no existe una función $f: A \rightarrow P(A)$ que sea sobre.

Dem. Lo demostraremos, como se ha hecho costumbre en las últimas entradas, por contradicción, es decir que suponemos que existe $f: A \rightarrow P(A)$ sobre. A diferencia de la situación habitual en la que tenemos conjuntos de números para el dominio y el rango, $f$ es una correspondencia entre un conjunto y su conjunto potencia. Para cada elemento $a\in A$ , $f(a)$ es un subconjunto de $A$ . La suposición de que $f$ es sobre significa que cada subconjunto de $A$ aparece como $f(a)$ para algún $a\in A$ . Para llegar a una contradicción lo que haremos es producir un subconjunto $B\subseteq A$ que no sea igual a $f(a)$ para cualquier $a\in A$ .

Construimos $B$ utilizando la siguiente regla. Para cada elemento $a\in A$ , consideremos el subconjunto $f(a)$ . Este subconjunto de $A$ puede o no contener al elemento $a$ . Esto depende de la función $f$ . Si $f(a)$ no contiene a $a$ , entonces lo incluimos en nuestro conjunto $B$ . Más concretamente, sea

$B=\left\{a\in A:a\notin f(a)\right\}.$

Debido a que hemos supuesto que nuestra función $f: A \rightarrow P(A)$ es sobre, debe ser $B=f(a')$ para algún $a'\in A$ . El lector podrá convencerse fácilmente que surge una contradicción cuando consideramos si $a'$ es un elemento de $B$ . Por lo tanto, no existe una función $f: A \rightarrow P(A)$ que sea sobre. $\clubsuit$

Con este resultado podemos ahora profundizar nuestro análisis acerca de la cardinalidad de conjuntos.

La relación de tener la misma cardinalidad es una relación de equivalencia, es decir, más o menos, que todos los conjuntos en el universo pueden ser organizados en grupos disjuntos de acuerdo a su tamaño. Dos conjuntos aparecen en el mismo grupo, o clase de equivalencia, si y sólo si tienen la misma cardinalidad. Por lo tanto, $\mathbb{N}$ , $\mathbb{Z}$ y $\mathbb{Q}$ se agrupan en una clase con todos los otros conjuntos numerables, mientras que $\mathbb{R}$ está en otra clase que incluye al intervalo $(0, 1)$ entre otros conjuntos no numerables (Recordar el Proceso de diagonalización de Cantor). Una consecuencia del Teorema de Cantor es que $P(\mathbb{R})$ –el conjunto de todos los subconjuntos de $\mathbb{R}$ — pertenece a una clase diferente de $\mathbb{R}$ , y no hay razón para parar aquí. El conjunto de subconjuntos de $P(\mathbb{R})$ –digamos $P(P(\mathbb{R}))$ — está en otra clase, y este proceso continúa indefinidamente.

Después de haber dividido el universo de los conjuntos en grupos disjuntos, sería conveniente conectar un número a cada colección, que se podría utilizar de la misma manera que los números naturales se utilizan para referirse a los tamaños de los conjuntos finitos. Dado un conjunto $X$ , existe algo que se llama el número cardinal de $X$ , denotado por $\text{card }X$ , que se comporta en gran medida de esta manera. Por ejemplo, dos conjuntos $X$ e $Y$ satisfacen $\text{card }X=\text{ card }Y$ si y sólo si $X\sim Y$ . (Definir rigurosamente a $\text{card }X$ requiere un tratamiento más profundo de teoría de conjuntos. Una forma de hacerlo es definir $\text{card }X$ como un conjunto muy particular que siempre se puede encontrar de forma única en la misma clase de equivalencia de $X$ .)

Mirando hacia atrás en el Teorema de Cantor, tenemos la fuerte sensación de que hay un orden en los tamaños de los conjuntos infinitos que debería reflejarse en nuestro nuevo sistema numérico cardinal. Específicamente, si es posible mapear un conjunto $X$ en $Y$ de un modo 1-1, entonces queremos que $\text{card }X\leq\text{ card }Y$ . Escribir la desigualdad estricta $\text{card }X<\text{ card }Y$ debería indicar que es posible mapear $X$ en $Y$ pero que es imposible demostrar que $X\sim Y$ . Reformulado en esta notación, el Teorema de Cantor afirma que para cada conjunto $A$ , $\text{card }A<\text{ card }P(A)$ .

Hay algunos detalles importantes para trabajar. Un tipo de problema metafísico surge cuando nos damos cuenta de que una implicación del Teorema de Cantor es que no puede haber ningún conjunto más grande. Una declaración como, «Sea $U$ el conjunto de todas las cosas posibles» es paradójica, porque conseguimos inmediatamente que $\text{card }U<\text{ card }P(U)$ y por lo tanto el conjunto $U$ no contiene todo lo que en el anuncio advierte. Cuestiones como ésta se resuelven en última instancia mediante la imposición de algunas restricciones sobre lo que se puede calificar como un conjunto. Cuando se formalizó la teoría de conjuntos, los axiomas tuvieron que ser elaborados de manera que simplemente no se permitan objetos tales como $U$ . Un problema más con los pies en la tierra que necesita de atención es demostrar que nuestra definición de $\leq$ entre números cardinales es realmente un ordenamiento. Esto implica demostrar que los números cardinales poseen una propiedad análoga a los números reales, que establece que si $\text{card }X<\text{ card }Y$ y $\text{card }Y<\text{ card }X$ entonces $\text{card }X=\text{ card }Y$ . Al final, esto se reduce a demostrar que si existe $f:X\rightarrow Y$ que es 1-1, y si existe $g: Y\rightarrow X$ que es 1-1, entonces es posible encontrar una función $h: X\rightarrow Y$ que es a la vez 1-1 y sobre. Una demostración de este hecho eludió a Cantor, pero finalmente fue suministrada de manera independiente por Ernst Schröder (en 1896) y por Félix Bernstein (en 1898), y hoy se conoce como Teorema de Schröder-Bernstein.

Había otro problema de fondo derivado de la teoría de los números cardinales en ciernes que ocupó a Cantor y que no resolvió durante su vida. Debido a la importancia de los conjuntos numerables, el símbolo $\aleph_{0}$ («aleph cero») se utiliza con frecuencia para el $\text{card }\mathbb{N}$ . El subíndice «0» es apropiado cuando recordamos que los conjuntos numerables son el tipo más pequeño de conjunto infinito. En términos de números cardinales, si $\text{card }X<\aleph_{0}$ , entonces $X$ es finito. Por lo tanto, $\aleph_{0}$ es el número cardinal infinito más pequeño. La cardinalidad de $\mathbb{R}$ también es lo suficientemente importante como para merecer la designación $\text{\textbf{\textit{c}}}=\text{ card }\mathbb{R}=\text{ card }(0,1)$ . De lo que hemos visto, $\aleph_{0}<\text{\textbf{\textit{c}}}$ . La pregunta que atormentó a Cantor fue si existían números cardinales estrictamente entre estos dos. Dicho de otra manera, ¿existe un conjunto $A\subseteq\mathbb{R}$ con $\text{card }\mathbb{N}<\text{ card }A<\text{ card }\mathbb{R}$ ? Cantor era de la opinión de que no existía tal conjunto. En el ordenamiento de los números cardinales, conjeturó, $\text{\textbf{\textit{c}}}$ es el sucesor inmediato de $\aleph_{0}$ .

La Hipótesis del continuo de Cantor, como llegó a ser llamada, fue uno de los más famosos retos matemáticos del siglo pasado. Su resolución inesperada se produjo en dos partes. En 1940, el lógico y matemático alemán Kurt Gödel demostró que, utilizando solamente el conjunto acordado de los axiomas de la teoría de conjuntos, no había manera de refutar la hipótesis del continuo. En 1963, Paul Cohen demostró con éxito que, bajo las mismas reglas, también era imposible probar esta conjetura. Tomados en conjunto, lo que estos dos descubrimientos implican es que la hipótesis del continuo es indecidible. Puede ser aceptada o rechazada como una declaración sobre la naturaleza de los conjuntos infinitos, y en ningún caso se producirán contradicciones lógicas.

Para cerrar este tema y repasar lo que hemos visto en las últimas entradas de Análisis Real, los invito a ver la siguiente recreación histórica:

Referencias bibliográficas:

Abbott, Stephen (2010) Understanding Analysis. Springer.

Read Full Post »

Método de diagonalización de Cantor

Posted in Análisis Real, Producción propia, tagged Cardinalidad de conjuntos, Conjuntos no numerables, Conjuntos numerables, Diagonalización de Cantor, George Cantor on 11 marzo 2015| Leave a Comment »

En la entrada anterior acerca de conjuntos numerables demostramos que el conjunto de los números reales es no numerable. Si bien la demostración presentada es diferente de cualquiera de los argumentos que Georg Cantor dio para este resultado, revela de manera directa la conexión entre los conceptos de numerabilidad y completitud.

Cantor publicó inicialmente su descubrimiento de que $\mathbb{R}$ es no numerable en 1874, pero en 1891 ofreció una demostración más de este mismo hecho que es sorprendente por su sencillez. Se basa en representaciones decimales de los números reales, que aquí aceptaremos y utilizaremos sin ningún tipo de definición formal. El lector interesado en ahondar más en este tema puede recurrir a Apostol.

El intervalo abierto $(0,1)=\left\{x\in\mathbb{R}:0<x<1\right\}$ es no numerable.

Dem. Procedemos por contradicción, suponiendo que sí existe una función $f:\mathbb{N}\rightarrow(0,1)$ que es 1-1 y sobre. Para cada $m\in\mathbb{N}$ , $f(m)$ es un número real entre $0$ y $1$ , y lo representamos usando la notación decimal

$f(m)=0,a_{m1}a_{m2}a_{m3}a_{m4}a_{m5}\ldots.$

Esto significa que para cada $m,n\in\mathbb{N}$ , $a_{mn}$ es el dígito del conjunto $\left\{0,1,2,\ldots,9\right\}$ que representa el $n$ -ésimo dígito del desarrollo decimal de $f(m)$ . La correspondencia 1-1 entre $\mathbb{N}$ y $(0,1)$ se puede resumir en la matriz doblemente indexada

El supuesto clave de esta correspondencia es que todo número real en $(0,1)$ se supone aparecerá en algún lugar de la lista.

Ahora la perlita del argumento. Definimos un número real $x\in(0, 1)$ con el desarrollo decimal $x=0,b_{1}b_{2}b_{3}b_{4}\ldots$ usando la regla

Con un poco de profunda reflexión el lector se podrá dar cuenta de que este número real $x$ no se corresponde con ninguno de los que hemos listado en el rango de la función $f:\mathbb{N}\rightarrow(0,1)$ . Esta contradicción nos lleva a concluir que $(0, 1)$ es no numerable. $\clubsuit$

Una imagen visual quizás ayude…

Se deja al lector demostrar que $(0, 1)$ es no numerable si y sólo si $\mathbb{R}$ es no numerable. Como sugerencia, válgase de la función $h:(0,1)\rightarrow\mathbb{R}$ dada por $h(x)=(2x-1)/(x-x^{2})$ .

Así, tenemos una nueva versión, la dada por el Proceso de Diagonalización de Cantor, que es con el nombre que se conoce la técnica que hemos descrito arriba, de la demostración de la no numerabilidad del conjunto de los números reales.

Hemos visto que demostrar que $(0,1)$ es no numerable lleva su tiempito. Sin embargo, quienes hemos estudiado la Teoría de la Medida de Lebesgue podemos jactarnos de demostrar este hecho en una sola línea. Ocurre que la medida Lebesgue de un intervalo coincide con su longitud, y la medida Lebesgue de todo conjunto numerable es cero. Así, si $(0,1)$ fuera numerable resultaría:

$0=m((0,1))=l((0,1))=1$

lo que claramente es una contradicción. La única línea arriba nos dice que $(0,1)$ es no numerable.

Después de haber distinguido entre la infinidad numerable de $\mathbb{N}$ y la infinidad no numerable de $\mathbb{R}$ , una nueva pregunta ocupó a Cantor: existe un infinito por encima de $\mathbb{R}$ ?. Esto lógicamente es un territorio traicionero. El mismo cuidado que dimos a la definición de la relación tiene la misma cardinalidad que tiene que ser dado a las relaciones que definen tiene cardinalidad mayor que o tiene cardinalidad menor o igual a. Pero esto es tema de otra entrada…

Referencias bibliográficas:

Abbott, Stephen (2010) Understanding Analysis. Springer.
Apostol, Tom M. (2005) Cálculus. Volumen 1. Reverte.
Ferrando, J. C.; Gregori, V. (1995) Matemática discreta. Reverté.
Royden, H (2010) Real Analysis. Mc.Millan

Read Full Post »

Conjuntos numerables (o infinitos numerables)

Posted in Análisis Real, Producción propia, tagged Cardinalidad de conjuntos, Conjuntos no numerables, Conjuntos numerables, Números irracionales, Números racionales, Números reales on 5 marzo 2015| 1 Comment »

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\}$

$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}$ .