Monday, June 02, 2014

Tipos de infinitos (grandes y chicos), numerabilidad, axioma de elección y paradojas



Nota: Si estas en tablet o teléfono para visualizar mejor los símbolos haz click aquí

Pregunta para reflexionar antes de empezar este post.


¿Un objeto matemático existe sólo si existe un algoritmo que lo pueda construir explícitamente o sólamente existe si la suposición de su existencia no conlleva a contradicciones a pesar de que no podamos encontrar jamás un ejemplo?

Cardinalidad (tamaño) de conjuntos, numerable y no numerable

Ahora veremos un tema que es muy importante en las matemáticas, el cual desde mi punto de vista , dividieron a los matemáticos, sabemos que los números enteros $latex \mathbb{Z}=\lbrace ...,-2,-1,0,1,2,...\rbrace$  y los números reales $latex \mathbb{R}$ son infinitos, vamos a ver que el infinito de los reales es estrictamente más grande que el infinito de los enteros, después veremos al axioma de elección, el cual aplicado a colecciones infinitas de conjuntos implica resultados paradójicos que pueden llegar a ser sorprendentes.

Definición: Un conjunto A es de cardinalidad finita $latex n$ si existe una función biyectiva del conjunto $latex \lbrace 1,2,3,...,n\rbrace$ con A.
Decimos que un conjunto A es numerable infinito si hay una función biyectiva con el conjunto $latex \mathbb{N}=\lbrace 1,2,3,... \rbrace$, un conjunto infinito numerable o finito se le dice numerable

Un conjunto A es no numerable infinito si no es vacío y no es numerable


Esta definición ya nos permite comenzar a hacer cosas, por ejemplo, si tenemos el conjunto de todos los enteros $latex \mathbb{Z}=\lbrace ...,-2,-1,0,1,2,...\rbrace$ y el conjunto de los naturales con el 0, llamémosle $latex A=\lbrace 0,1,2,3,...\rbrace$


Ejemplo: comparando los enteros negativos con positivos con los enteros positivos.

¿Cuál conjunto es más grande?

Aquí nos topamos con un concepto que deja de ser intuitivo, en primera instancia uno está contenido dentro de otro $latex A\subset \mathbb{Z}$ pero no al revés.

Pero imaginen una fiesta donde hay $latex n$ mujeres y $latex m$ hombres.

¿cómo podemos saber si todos podrán bailar con alguien del sexo opuesto en una canción?

Una opción sería contarlos y ver si $latex n=m$ la otra opción es asignarles una pareja y ver si nadie se queda sin bailar.


La segunda opción es la que equivale a la definición, necesitamos encontrar una función, y si a todas las mujeres les toca un hombre y sólo un hombre entonces no habrá duda que el conjunto de mujeres y hombres mide lo mismo ya que todos tienen una pareja y nadie se queda solo.


Para nuestro ejemplo imaginen esta regla de correspondencia:


$latex A$      $latex \mathbb{Z}$
$latex 0\mapsto 0$
$latex 1\mapsto -1$
$latex 2\mapsto +1$
$latex 3\mapsto -2$
$latex 4\mapsto +2$
$latex 5\mapsto -3$
..
..
$latex 2n$ $latex \mapsto n$
$latex 2n+1$ $latex \mapsto -(n+1)$


En resumen, asociamos pares de $latex A$ con positivos en $latex \mathbb{Z}$ e impares de $latex A$ con negativos de $latex \mathbb{Z}$ y ambos $latex 0$ en $latex A$ y $latex \mathbb{Z}$ los ponemos en la misma pareja.

A mas detalle:

Es decir, a la fiesta asociamos el 0 de $latex A$ con el 0 de $latex \mathbb{Z}$
y a los demás asociamos que si el elemento $latex x\in A$ es par de la forma $latex x=2n$ entonces le asociamos $latex n\in \mathbb{Z}$, y si $latex x \in A$ es impar de la forma $latex x=2n+1$ entonces le asociamos $latex -(n+1)$ lo que nos hace que todos tengan una sola pareja y nos define una función biyectiva de $latex A$ y $latex \mathbb{Z}$ por lo que los enteros positivos comparados con los enteros positivos Y negativos tienen el mismo tamaño.


 Ahora , también tenemos que el conjunto de todas las fracciones (es decir los números racionales) , TAMBIÉN es numerable, es decir que se puede poner en correspondencia con $latex \mathbb{N}$ , el que se pueda poner en correspondencia con $latex \mathbb{N}$ imaginen que es como poderles poner una etiqueta a los elementos a comparar y cubrir TODOS los elementos con los números naturales.


Entonces lo que tenemos que encontrar... es una manera de poder etiquetar con los naturales al conjunto:


$latex \mathbb{Q}=\lbrace \frac{a}{b} : a,b\in \mathbb{Z},b\neq 0\rbrace$

Al etiquetar con TODOS los elementos de $latex \mathbb{N}$ a TODOS los elementos de $latex \mathbb{Q}$ tendríamos automáticamente una correspondencia biyectiva entre ambos conjuntos probando que ambos tienen la misma cardinalidad, pero esto es fácil verlo con el siguiente arreglo de TODOS los números racionales.



 Aquí podemos ver que si siguen el flujo de las flechas rosas, y donde empieza que es en el 1/1 asignamos el 1, y después asignamos el 2,3,4... et cétera a los siguientes, podríamos obtener una función que asigne elementos de $latex \mathbb{N}$ a $latex \mathbb{Q}$ y si se fijan esta tabla cubre a TODOS los racionales... de hecho le sobran, los que le sobran son los $latex \frac{a}{b}$ tales que $latex a,b$ no son primos relativos, es decir que se pueden reducir, pero eso no importa, como pueden ver, los pueden eliminar, esto no causa problemas más que a la hora de definir la biyección explícitamente, pero con esto podemos ver que los naturales y los racionales tienen el mismo tamaño infinito.


Pero este pequeño ejemplo conlleva un teorema importante que vamos a probar



Teorema. Sean $latex A,B$ dos conjuntos infinitos numerables, entonces su producto cartesiano $latex A\times B$ también es infinito numerable.


Recuerden que el producto cartesiano de $latex A$ y $latex B$ resulta en otro conjunto $latex A\times B=\lbrace (a,b) : a\in A , b\in B\rbrace$

Vemos claramente que en nuestro ejemplo anterior si $latex \frac{a}{b} := (a,b)$ donde $latex b\neq 0$ y $latex mcd(a,b)=1$  entonces $latex \mathbb{Q}\subsetneq \mathbb{Z}\times \mathbb{Z}$


Entonces sabiendo esto, vamos a la demostración:

demostración:

Como ambos $latex A$ y $latex B$ están en correspondencia biyectiva con $latex \mathbb{N}$, lo único que tenemos que probar es que $latex \mathbb{N}\times \mathbb{N}$ es infinito numerable.

Entonces cosideremos

$latex \mathbb{N}\times \mathbb{N}=\lbrace (n,m):n,m\in \mathbb{N}\rbrace$ entonces el diagrama que nos conviene es:




 Donde claramente se puede ver que siguiendo las flechas podemos cubrir a cada par con todos los números naturales de manera ordenada y limpia.


Esta demostración más algebraicamente sería al definir una función

$latex f: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$

La cual es fácil verificar que:

$latex f(m,n)=\frac{(n+m-2)(n+m-1)}{2}+m$

cubre todos los pares de naturales y es biyectiva.

$latex \blacksquare$


De hecho por inducción podrías demostrar que el producto cartesiano de $latex n$ conjuntos numerables es numerable.


Pero bueno... ya vimos el primer infinito el cual es el más chico y lo llamamos $latex \aleph_0$.

¿Pero dónde están los otros infinitos?

¿Cuáles conjuntos son más grandes estrictamentes que los naturales? , pues la respuesta más básica es el conjunto de los números reales $latex \mathbb{R}$, este conjunto obviamente no es finito, y de hecho no es infinito numerable.

Aquí veremos el argumento usual debido a Cantor de diagonalización que prueba que también un conjunto inocentemente más chico que los reales $latex [0,1]=\lbrace x\in \mathbb{R} : 0\leq x \leq 1\rbrace$ NO es numerable también.



Teorema: El intervalo $latex [0,1]$ es NO numerable


Vamos a hacerlo por contradicción, supongamos que existe una correspondencia biyectiva $latex f:\mathbb{N}\rightarrow [0,1]$, lo que haremos es encontrar un número real en $latex [0,1]$ que no está en la imagen, contradiciendo la suposición de que $latex f$ es suprayectiva.


Para esto, lo único que vamos a suponer es que todo número real en $latex [0,1]$ tiene una expansión decimal

$latex 0.x_1x_2x_3x_4...$

Donde cada $latex x_k$ es $latex 0,1,2,3,...9$ para que esta expansión sea única, siempre vamos a redondear, excepto en el caso de $latex 0.99999...$ donde lo dejaremos como tal.

Por lo que $latex 0.32999...$ siempre será escrito como $latex 0.3300$ .

Ahora, tomemos nuestra supuesta correspondencia $latex f:\mathbb{N}\rightarrow [0,1]$ y escribamos los términos.



$latex f(1)=.a_1a_2a_3...$
$latex f(2)=.b_1b_2b_3...$
$latex f(3)=.c_1c_2c_3...$
$latex f(4)=.d_1d_2d_3...$
$latex f(5)=.e_1e_2e_3...$

 Y así... noten que los $latex a_i,b_j$ et cétera son números fijos entre 0 y 9, dándonos una correspondencia uno a uno, es decir no son variables.


Vamos a construir un nuevo número real $latex .N_1N_2N_3N_4...$ que no podrá aparecer en esa lista, forzando a que no sea suprayectiva por lo tanto contradiciendo la suprayección.

Supongamos que del número que queremos construir, definamos la k-ésimo dígito es:

$latex N_k = 4$ si la k-ésima entrada de $latex f(k)\neq 4$
$latex N_k = 5$ si la k-ésima entrada de $latex f(k)=4$


Nota que $latex N_1=4$ si $latex a_1\neq 4$ y $latex N_1=5$ si $latex a_1=4$

Entonces como sea que esté definido $latex f(1)$ siempre sucederá que:


$latex .N_1N_2N_3... \neq .a_1a_2...=f(1)$

Esto también sucederá para $latex N_2$ ya que si $latex N_2=4$ entonces $latex b_2\neq 4$ y será 5 si $latex b_2=4$ por lo que:


$latex .N_1N_2N_3...\neq .b_1b_2b_3...=f(2)$


Esto síganlo para todo $latex N_k$ y tendremos que nunca se parecerá a $latex f(k)$ por lo que este nuevo número no está en la imagen de $latex f$ para como sea que esté definida, por lo que no podría ser numerable. $latex \blacksquare$

Decimos que $latex [0,1]$ tiene cardinalidad $latex \aleph_1$


¿Existe un infinito intermedio entre $latex \aleph_0$ y $latex \aleph_1$?

Esta es la hipótesis del continuo... ¿ustedes qué creen?

Bueno esta pregunta es un gran hoyo en las matemáticas... y muestra la razón que tenía Gödel (Teoremas de incompletud) al decir que las matemáticas como las usamos son imperfectas en el sentido que son incompletas, existen proposiciones que no se pueden demostrar falsas o verdaderas.


Esto significa que esta pregunta... de que si existe un infinito intermedio... es indecidible... se demostró que NO se puede demostrar que esta pregunta es demostrable.

Esta pregunta de la hipótesis del continuo nos lleva a la pregunta inicial filosófica.

Formalización de los conjuntos

Ahora, antes de entrar a lo esotérico, regresen a la pregunta inicial de este post.


A la hora de probar que un objeto existe a veces puede ser constructiva o simplemente existencial, todo esto está fundamentado con la teoría de conjuntos formal, y ahora la más usada son los axiomas de Zermelo-Fraenkel unido con el axioma de elección.


Ahora veremos un poco el detalle de estos axiomas y la paradoja de Russell que muestra que debemos tener cuidado a la hora de trabajar con conjuntos en algo formal, ya que hay objetos que podrían definirse pero no existir.

La idea linda es muy razonable e inocente de cómo definir un conjunto, es decir como una colección de objetos que comparten cierta propiedad.

Noten que uno de los mayores estudiosos de la teoría de conjuntos (Georg Cantor) define un conjunto así:

Un conjunto es:

Toda multiplicidad que puede ser pensada como unidad, esto es, toda colección de elementos determinados que pueden ser unidos en una totalidad mediante una ley

 Por lo que el siguiente conjunto es muy razonable:

$latex \lbrace n: n$ es un número par $latex\rbrace $

Vamos a ver como los conjuntos forman la aritmética que conocemos.

Para formar nuevos conjuntos con conjuntos ya dados por ejemplo si tenemos al conjunto $latex A$ podemos formar a $latex \lbrace A\rbrace$ que es un conjunto de un elemento.

También definimos el conjunto sucesor de $latex A$ como $latex A^{+}=A\cup \lbrace A \rbrace$ es decir $latex x\in A^{+}$ si $latex x\in A$ o $latex x=\lbrace A\rbrace$.


Empecemos con el conjunto $latex \emptyset$ que es el vacío, éste no tiene elementos y corresponderá con el entero $latex 0$ , y vamos a denotar al sucesor de 0 como 1 el cual es:

$latex 1=\emptyset^{+}=\lbrace\emptyset\rbrace$

Después el sucesor del sucesor del vacío es el 2


$latex 2=(\emptyset^{+})^{+})=\lbrace\emptyset ,\lbrace \emptyset \rbrace \rbrace$


En general, vamos a definir al sucesor de $latex n$ como $latex n+1$

Lo cual el sucesor será sumar 1, podemos recobrar por recursión la adición y convertirla en multiplicación y después en resta y división, suena bien no?


Pero bueno, esto es la manera inocente de proceder, aquí Cantor tuvo un error que descubrió Russell, que la pasión de Cantor por el tema y la falta de soluciones ante el escenario de Russell lo llevó a la locura por el hecho de no poder solucionarlo, ya que el definir conjuntos inocentemente como el ejemplo de los números pares o así como procedimos va a llevar a paradojas.


Vamos a construir algo que cumple la definición de conjunto pero que no puede existir.


Veamos primero que existen conjuntos que son elementos de si mismos, hay conjuntos que no cumplen esto, por ejemplo.


El conjunto de números pares NO es elemento de si mismo, ya que éste conjunto como tal no es un número par, por lo tanto no se pertenece a si mismo.


Por otro lado el conjunto de los conjuntos  que tienen más de dos elementos , éste conjunto es miembro de si mismo.


Paradoja


Viendo que podemos construir estos conjuntos, definamos este conjunto.



$latex X = \lbrace A:A$ es un conjunto que no se pertenece a si mismo$latex \rbrace$

        $latex =\lbrace A:A\notin A\rbrace$



Este conjunto conlleva a una paradoja, es decir algo que viola en particular el principio del tercero excluido.


Pregunta: ¿Es $latex X$ un elemento de si mismo?

Si $latex X\in X$, entonces por definición de $latex X$ tenemos que $latex X\notin X$, lo cual es absurdo.

Entonces lo natural es que ya demostramos que $latex X\notin X$ , ... PERO...


Supongamos que $latex X\notin X$, entonces esto implica que $latex X\in X$ lo cual es otra contradicción.

Tenemos contradicción por la negación y la no negación por lo que esto es una paradoja, esto significa que $latex X$ no sería entonces un conjunto es decir es algo que se sale de la teoría y esta es la paradoja de Russell

La cual en símbolos es

$latex X\in X \Leftrightarrow X\notin X$

La solución a esto fue toda la teoría axiomática de Zermelo Fraenkel la cual elimina la posibilidad de poder construir objetos así, y que en pocas palabras limita a los objetos a que puedan ser definidos con lógica de primer orden "acotados" por otro objeto que ya sabemos es un conjunto.

Es decir no existe el conjunto de todos los conjuntos , o el complemento de un conjunto, éste último existe sólo cuando lo tomas como $latex U\setminus X$ que es el complemento de $latex X$ en $latex U$.


Ahora entremos al axioma de elección.



Axioma:  (elección)  Sea $latex \lbrace X_\alpha \rbrace$ una familia de conjuntos no vacíos, entonces existe un conjunto $latex X$ que contiene de cada conjunto $latex X_\alpha$ exactamente un elemento.


Esto es algo que suena obvio si tienes una colección finita de conjuntos, hasta un niño podría comprender que puede tomar un elemento de cada uno


Pero la dificultad viene cuando aplicas el axioma de elección a una colección infinita de conjuntos, y peor aún, una colección infinita NO numerable.

El axioma no te dice como encontrar este conjunto $latex X$ que contiene un elemento de cada conjunto de la colección sólo te dice que existe y punto.


El axioma de elección es peligroso mentalmente hablando, te puede llevar a paradojas como la de Banach-Tarski que te dice que tú puedes partir una esfera en un número finito de partes de tal manera que después  puedas armar 2 esferas iguales a la original.

O por ejemplo también, el elemento más chico en $latex (0,1)=\lbrace x: 0 < x < 1 \rbrace$

También existe un conjunto no numerable de puntos en el plano que tienen vecindades de radio $latex \epsilon >0$ que son ajenas.


Gracias a Andrei Rodríguez por la corrección, aquí dejo con sus propias palabras la demostración de que eso que dije es falso.

"Este ejemplo no funciona ya que $latex \mathbb{R}\times \mathbb{R}$ es separable; es decir porque tiene un subconjunto denso numerable.
A saber $latex \mathbb{Q}\times\mathbb{Q}$.

Veamos


Supongamos que existe una cantidad no numerable de abiertos ajenos en $latex \mathbb{R}\times \mathbb{R}$


Por la densidad de los racionales, cada uno de estos abiertos contiene al menos un punto de coordenadas racionales $latex (\mathbb{Q}\times\mathbb{Q})$, como los abiertos son ajenos, cada uno de estos puntos es distinto, esto implica que $latex \mathbb{Q}\times \mathbb{Q}$ o bien los puntos del plano con coordenadas racionales son un conjunto no numerable... lo cual es una contradicción, por lo tanto no existe un conjunto no numerable de abiertos ajenos en $latex \mathbb{R}\times\mathbb{R}$ $latex \blacksquare$"



Lo que Andrei quizo decir aquí de manera más compacta es que este supuesto conjunto no numerable de abiertos en $latex \mathbb{R}^2$ tiene a racionales en cada abierto (porque $latex \mathbb{Q}$ es denso en $latex \mathbb{R}$), por lo que de existir habría una cantidad no numerable de racionales lo cual es absurdo.

Y mi ejemplo fue mal pensado, habrá que pensar un espacio diferente para que esto suceda. 

 Por decir algunas cosas raras...

Esto sucede en la matemática no en la física, recuerden la analogía de los sacos de frijol, ahí estamos eligiendo frijoles de cada saco... pero realmente podemos elegir un frijol dentro de un conjunto de $latex \aleph_1$ sacos? , la matemática dice que esto es un axioma, es decir es una regla del juego... ¿te gusta la regla?


Eduardo Ruiz Duarte (beck)
twitter: @toorandom