Curso EVT. Lectura 24. Cardinales (7)

Vamos a ver otro interesante resultado que involucra a los números reales

Teorema 1. Se cumple que |\mathcal{P}(\mathbb{N})| \leq |\mathbb{R}|

Prueba. Para llevar a cabo esta demostración vamos a utilizar el llamado conjunto de Cantor. Sea el intervalo cerrado unidad C_{1} =[0,1]. Dividimos este intervalo unidad en tres partes
\displaystyle  I_{1} =\bigg[0, \frac{1}{3}\bigg], I_{2} =\bigg]\frac{1}{3}, \frac{2}{3} \bigg[, I_{3} =\bigg[\frac{2}{3}, 1 \bigg]
y tomamos las dos partes cerradas extremas para formar la unión:
\displaystyle C_{2} = \bigg[0, \frac{1}{3}\bigg] \cup \bigg[\frac{2}{3}, 1 \bigg].
Repetimos el proceso para cada una de estas nuevas partes:
\displaystyle \bigg[0, \frac{1}{9}\bigg],\bigg]\frac{1}{9}, \frac{2}{9}\bigg[,\bigg[\frac{2}{9}, \frac{3}{9}\bigg],
\displaystyle \bigg[\frac{6}{9}, \frac{7}{9}\bigg],\bigg]\frac{7}{9}, \frac{8}{9}\bigg[,\bigg[\frac{8}{9}, 1\bigg].
Construimos entonces
\displaystyle C_{3} = \bigg[0, \frac{1}{9}\bigg] \cup \bigg[\frac{2}{9}, \frac{3}{9}\bigg] \cup \bigg[\frac{6}{9}, \frac{7}{9}\bigg] \cup \bigg[\frac{8}{9}, 1\bigg]

conjuntocantor

Este proceso sigue indefinidamente y se caracteriza por las propiedades siguientes
(i)Cada C_{m+1} está incluido en C_{m}
(ii) Cada C_{m} es la unión de 2^{m-1} intervalos cerrados disjuntos.
Al conjunto intersección C = \cap_{i=1}^{\infty} C_{i} le llamamos conjunto de Cantor. Construiremos una función inyectiva de \Delta en C. Para ello, recordemos que en la construcción del conjunto de Cantor cada uno de los 2^{m-1} intervalos [a,b] de C_{m} se reemplaza por 2 intervalos
\displaystyle L[a,b] =\bigg[a, a+\frac{1}{3}(b-a) \bigg], R[a,b] = \bigg[ a+\frac{2}{3}(b-a),b \bigg].
Esto nos va a servir para asociar a cada sucesión infinita de \Delta uno de estos dos intervalos. En efecto, sea \delta(n) una sucesión infinita de ceros y unos, definimos

\displaystyle F_{1}^{\delta}= C_{1},
\displaystyle F_{n+1}^{\delta} = LF_{n}^{\delta}, si \delta(n)=0,
\displaystyle F_{n+1}^{\delta}=RF_{n}^{\delta}, si \delta(n) = 1

Evidentemente, cada F_{n}^{\delta} es subconjunto de C_{n} por lo que F_{n+1}^{\delta} \subset F_{n}^{\delta} y obtenemos una sucesión decreciente de intervalos cerrados. La completitud de la recta implica entonces que su intersección es un único punto que llamaremos f(\delta). La función inyectiva que vamos a construir será pues aquella que a cada sucesión \delta le asocia el único punto f(\delta). En efecto, está bien definida y si suponemos que dos sucesiones \delta y \epsilon de \Delta son diferentes, entonces hallaremos un valor mínimo n \in \mathbb{N} tal que \delta(i) = \epsilon(i) para i \leq n y es \delta(n) = 0 pero \epsilon(n) =1 (o al contrario sin pérdida de generalidad). Entonces f(\delta) \in F_{n+1}^{\delta}=LF_{n}^{\delta} y también f(\epsilon) \in F_{n+1}^{\epsilon}=RF_{n}^{\delta}. Los intervalos LF_{n}^{\delta} y RF_{n}^{\delta} son disjuntos por lo que las imágenes f(\delta) y f(\epsilon) son diferentes. Esto prueba que la aplicación es inyectiva. Evidentemente, la aplicación f también es inyectiva de \Delta en \mathbb{R} y esto prueba que |\Delta| \leq |\mathbb{R}|. Como sabemos que |\Delta|=|\mathcal{P}(\mathbb{N})| se sigue el enunciado del teorema y esto termina nuestra demostración.

Vamos a probar ahora la relación contraria.

Teorema 2. Se cumple que |\mathbb{R}| \leq |\mathcal{P}(\mathbb{N})| .

Prueba. Sea I=]0,1[ el intervalo abierto unidad. Consideremos cada número de dicho intervalo en base dos. Esto es, para cada x de I escribimos
\displaystyle x = \sum_{n=1}^{\infty} \frac{a_{n}}{ 2^{n}},
donde a_{i} es 0 o 1. La aplicación f que a cada x le hace corresponder la sucesión (a_{1}, a_{2}, \ldots, a_{n}, \ldots) es inyectiva ya que si dos sucesiones de ceros y unos son iguales entonces han de representar al mismo número real x. Por tanto, |]0,1[| \leq | \Delta |. Ahora bien, sabemos que el intervalo abierto unidad es equipotente a la recta real y de aquí que |\mathbb{R}| \leq | \Delta |= |\mathcal{P}(\mathbb{N})|

Los teoremas 1 y 2 nos muestran dos desigualdades entre cardinales de la forma a \leq b y b \leq a. Podemos preguntarnos si, como en el orden usual, estas dos desigualdades implican que a=b. La respuesta es afirmativa y viene dada por el teorema llamado de Cantor-Schröder-Bernstein. Para demostrarlo utilizaremos un lema auxiliar

Lema 1.Sean A_{1}, B y A conjuntos tales que A_{1} \subset B \subset A. Si |A_{1}| = |A|, entonces |A| = |B|

Prueba. Como A y A_{1} son equipotentes existe una biyección entre ellos f:A \rightarrow A_{1}. Construimos a partir de esta biyección un par de sucesiones de conjuntos mediante

\displaystyle A_{n} =A, si n=0,
\displaystyle A_{n} = f^{n}(A) , si n \geq 1.
\displaystyle  B_{n} = B, si n =0.
\displaystyle  B_{n} = f^{n}(B), si n \geq 1.

Obsérvese que de la inclusión A_{1} \subset B=B_{0} \subset A_{0} = A se sigue fácilmente por inducción que f^{n}(A_{1}) \subset f^{n} (B_{0}) \subset f^{n} (A_{0}). Esto es, A_{n+1} \subset B_{n} \subset A_{n} para todo n. Definimos C_{n} = A_{n}- B_{n} para cada n. Como f es inyectiva tenemos que f(C_{n}) = f(A_{n})- f(B_{n}) = A_{n+1} -B_{n+1} = C_{n+1}. Sea entonces
\displaystyle C = \bigcup_{n=0}^{\infty} C_{n},
\displaystyle D = A-C.
Esto significa que
\displaystyle f(C) = f(\cup_{n=0}^{\infty} C_{n})= \cup_{n=0}^{\infty}f(C_{n}) = \cup_{n=0}^{\infty}C_{n+1} = \cup_{n=1}^{\infty}C_{n}.
\displaystyle D = A-C = A -\bigcup_{n=0}^{\infty} C_{n} = \bigcap_{n=0}^{\infty} (A-C_{n}).
Entonces f(C) \cup D = B (unión disjunta) y definimos una aplicación g:A \rightarrow B mediante

\displaystyle g (x) =f(x), si x \in C,
\displaystyle g (x) =x, si x \in D,

Esta aplicación es una biyección entre A y B, luego |A| = |B|

Lema 2.Sean A y B dos conjuntos y sea f: A \rightarrow B una aplicación inyectiva. Si |f(A)| = |B| entonces |A| = |B|.

Prueba. Si f: A \rightarrow B es una aplicación inyectiva, entonces la aplicación f: A \rightarrow f(A) es una biyección. Si suponemos que |f(A)| = |B|, entonces existe una biyección h: f(A) \rightarrow B por lo que la composición h \circ f es una biyección entre A y B y esto termina la demostración.

Teorema 3 (Cantor-Schröder-Bernstein).Sean A y B dos conjuntos tales que |A| \leq B y |B| \leq |A|. Entonces |A| = |B|.

Prueba. Existen aplicaciones inyectivas f: A \rightarrow B y g:B \rightarrow A. Por tanto, la composición g \circ f:A \rightarrow A es una biyección (ya que el ser una inyección de un conjunto en sí mismo resulta también sobreyectiva). Claramente
\displaystyle g \circ f (A) \subset g(B) \subset A..
Obviamente |g \circ f(A)| = |A |, por lo que aplicando el lema 1 concluimos que |A | = |g(B) |. Finalmente, aplicando el lema 2 concluimos que |A|=|B|.

Estos resultados nos llevan a afirmar que |\mathcal{P}(\mathbb{N})| =|\mathbb{R}|.

Anuncios

Curso EVT. Lectura 20. Cardinales (3)

Teorema 1. Sea A un conjunto. Son equivalentes:
a) Existe B \subset A, tal que B es infinito numerable.
b) El conjunto A es D-infinito.

Prueba. (a) implica (b). Supongamos que B \subset A es infinito numerable. Hallaremos pues una biyección g: \mathbb{N} \rightarrow B. Sea ahora P el conjunto de los números pares. Es claro que la restricción g_P:P \rightarrow B es una biyección de P en g(P). También la aplicación f:\mathbb{N} \rightarrow P, dada por f(n) = 2n es una biyección. Por tanto, g_P \circ f \circ g^{-1} es una aplicación inyectiva y aplica B en B-g(P). Podemos extender esta aplicación a todo A mediante h(x) = (g_P \circ f \circ g^{-1})(x), si x \in B y h(x) si x \in A-B. Es fácil probar que h es inyectiva y aplica A en (A-B) \cup g(P) \subsetneq A. Esto prueba que A es D-infinito.
(b) implica (a). Como A es D-infinito, existen H \subsetneq A y una biyección \phi:A \rightarrow H. Sea a \in A-H, entonces \phi(a) \neq a pues \phi(a) \in H. Del mismo modo \phi^{2}(a) \neq \phi(a), pues si así fuera, entonces \phi(a) =a en contra de lo supuesto. Reiterando este argumento por inducción obtenemos un subconjunto \{a, \phi(a), \phi^{2}(a), \ldots, \phi^{n}(a), \ldots \} que resulta numerable.

Teorema 2. Un conjunto A es infinito si y sólo si contiene un subconjunto infinito numerable.

Prueba. Supongamos que B \subset A y B es infinito numerable. En ese caso, por el teorema anterior resulta que es D-infinito y, por tanto es infinito. Supongamos que A es infinito . Sea 2^{A} el conjunto de las partes de A. El axioma de elección nos garantiza la existencia de una función de elección f:2^{A}-\{\emptyset\} \rightarrow A. Con ella vamos a formar una sucesión a_n mediante a_n = f(A), si n=1, a_n=f(A-\{a_1,\ldots, a_{n-1}\}) si n \geq 2. Esta sucesión está bien formada ya que al ser A infinito, se tiene que A-\{a_1, \ldots, a_{n-1}\} es no vacío para cualquier n \geq 2 y como f es una función de elección resulta que f(X) \in X para cada X no vacío. Así resultará que a_n \neq a_m, si n \neq m. El conjunto B=\{a_n : n \in \mathbb{N} \} es numerable y está incluido en A.

Llegamos por fin al resultado buscado.

Teorema 3. Todo conjunto infinito es D-infinito

Prueba. Sea A infinito. Entonces existe B \subset A, tal que B es numerable (por el teorema 2) y, por tanto por el teorema 1 es D-infinito.

Cuando definimos el concepto de conjunto infinito utilizamos dos aproximaciones aparentemente diferentes. Una de ellas se basaba en la posibilidad de encontrar aplicaciones inyectivas sobre sí mismo que no eran sobreyectivas y otra se basaba en la imposibilidad de encontrar un entero positivo n tal que el conjunto fuera equipotente a \{1,2, \ldots, n\}. Hemos visto que estas dos ideas son equivalentes pero para ello hemos tenido que usar el axioma de elección. A partir de ahora, usaremos una u otra sin distinción y daremos una serie de resultados básicos sobre operaciones y cardinales.

Sobre la definición de conjunto infinito

La definición clásica de conjunto infinito es sencilla: un conjunto es infinito cuando no es finito. Es claro que llegado a este punto, la pregunta inmediata que nos hacemos es, ¿cuándo un conjunto es finito? Pues también existe una definición clásica y es la siguiente.

Un conjunto A es finito si es vacío o existe un subconjunto  S(n)= \{1,2, \ldots, n \} de \mathbb{N} y una biyección f  de A en S(n).

Sin embargo, existe otra definición menos conocida pero muy interesante atribuida a Dedekind:

Un conjunto A se dice que es finito tipo Dedekind o D-finito si no es posible encontrar ninguna biyección entre el conjunto A y cualquiera de sus subconjuntos propios. En caso contrario, se dirá que es infinito tipo Dedekind o D-infinito.

Utilizando la propiedad de buena ordenación de los naturales podemos probar que todo conjunto finito es D-finito.  Sin embargo, la única prueba que conozco de la equivalencia de que todo conjunto infinito es D-infinito precisa del axioma de elección.