Curso EVT. Lectura 25. Cardinales (8)

No definiremos de manera precisa lo que entendemos por cardinal pues ello precisaría de la teoría de los ordinales. Consideraremos pues un cardinal como una “clase de equivalencia” formada por conjuntos equinumerosos. La definición de las operaciones entre cardinales las haremos utilizando representantes. De esta manera si \alpha es un cardinal, escribiremos |A| =  \alpha para indicar que A pertenece al cardinal \alpha. Tampoco daremos las demostraciones de todos los teoremas.

Definición 1. Sean \alpha y \beta dos cardinales y sean A y B conjuntos disjuntos tales que |A|= \alpha y |B|= \beta. Se define la suma \alpha + \beta como el cardinal del conjunto A \cup B

Esta definición es consistente pues se prueba con facilidad que es independiente de los representantes elegidos. Podemos extender esta definición para la suma de un número arbitrario de cardinales.

Definición 2. Sea ( \alpha_{i})_{i \in I} una familia de cardinales y sea (A_{i})_{i \in I} una familia de conjuntos tales que |A_{i}| = \alpha_{i} para cada i \in I. Se define su suma \sum_{i} \alpha_{i} como el cardinal del conjunto \bigcup_{i \in I} (A_{i} \times \{ i \}).

De nuevo resulta una definición consistente pues no depende de los representantes que se elijan, además para cada i de I es cierta la igualdad |A_{i} \times \{ i \}| = |A_{i}|, siendo los conjuntos de la familia (A_{i} \times \{i \})_{i \in I} disjuntos dos a dos.

Teorema 1. Sean \alpha, \beta y \gamma tres cardinales cualesquiera. Se cumplen:
a) \alpha + \beta = \beta + \alpha.
b) Si | \emptyset | = 0, entonces \alpha+0 = 0 + \alpha = \alpha.
c) \alpha + (\beta + \gamma) = (\alpha + \beta)+ \gamma.
Definición 3. Sean \alpha y \beta dos cardinales y sean A y B conjuntos tales que |A|= \alpha y |B|= \beta. Se define el producto \alpha  \beta como el cardinal del conjunto A \times B.

Como vemos no se exige que los conjuntos sean disjuntos. Ahora bien, si uno de ellos es vacío, el producto cartesiano será vacío.

Definición4. Sea ( \alpha_{i})_{i \in I} una familia de cardinales y sea (A_{i})_{i \in I} una familia de conjuntos tales que |A_{i}| = \alpha_{i}. Se define el producto \prod_{i \in I} \alpha_{i} como el cardinal del producto cartesiano \prod_{i \in I} A_{i}.

Si ninguno de los cardinales es cero entonces ninguno de los conjuntos de la familia será vacío y el producto cartesiano no será vacío en virtud del axioma de elección.

Teorema 2. Sean \alpha, \beta y \gamma cardinales cualesquiera. Entonces
a) (\alpha  \beta) \gamma = \alpha  (\beta \gamma).
b) \alpha \beta = \beta \alpha.
c) \alpha 1 = \alpha, donde 1 es el cardinal del natural \{ 0 \}.
d) \alpha (\beta+ \gamma) = \alpha \beta + \alpha \gamma.
e) \alpha 0 = 0.
f) \sum_{i \in I} \alpha = |I| \alpha.

Señalemos en especial la propiedad (f) pues la hemos usado en la demostración de la equicardinalidad de las bases de un mismo espacio vectorial.

Definición 5. Se dice que un cardinal \alpha es menor o igual que otro cardinal \beta si podemos hallar conjuntos A y B para los que |A|= \alpha, |B| = \beta y existe una función f:A \rightarrow B inyectiva. En tal caso, escribimos \alpha \leq \beta.
Teorema 3. Si (\alpha_{i})_{i \in I} es una familia de cardinales y (A_{i})_{i \in I} es una familia de conjuntos con |A_{i}| = \alpha_{i} para cada i \in I, entonces |\bigcup_{i \in I} A_{i} | \leq \sum_{i \in I} \alpha_{i}.
Teorema 4. Sean ( \alpha_{i})_{i \in I} y ( \beta_{i})_{i \in I} dos familias de números cardinales tales que \alpha_{i} \leq \beta_{i}, para todo i \in I, entonces:

a) \sum_{i \in I} \alpha_{i} \leq \sum_{i \in I} \beta_{i}.
b) \prod_{i \in I} \alpha_{i} \leq \prod_{i \in I} \beta_{i}.

Es importante señalar que estas propiedades no se cumplen siempre si la desigualdad entre los cardinales es estricta.

Teorema 5. Sea \alpha un cardinal infinito y sea \omega el cardinal de los naturales. Entonces si \beta es un cardinal que cumple \beta \leq \omega, concluimos que \alpha + \beta = \alpha.

Prueba. Consideremos A y B tales que A \cap B = \emptyset y |A| = \alpha y |B| = \beta. Sabemos que todo conjunto infinito contiene un subconjunto numerable. Por tanto, existe C \subset A tal que |C| = \omega. Escribimos C = \{c_{1}, c_{2}, \ldots, c_{n}, \ldots \} y definimos la función f: \mathbb{N} \cup A \rightarrow A, mediante

c_{2n} si x  \in \mathbb{N}.
c_{2n-1} si x \in C.
x si x \in A-C.

Esta función es biyectiva y esto prueba que |\mathbb{N} \cup A| = |A|. Es decir, \omega+ \alpha = \alpha. Aplicando (a) del teorema 4 concluimos de la desigualdad \beta \leq \omega que \alpha+\beta \leq \alpha+\omega = \alpha \leq \alpha + \beta y en virtud del teorema de Schröder-Bernstein es \alpha+\beta = \alpha.

Podemos obtener un conocido resultado a partir de esta demostración.

Corolario 1. Si \omega es el cardinal de los naturales, entonces \omega+ \omega = \omega.

Prueba. Bastará tomar \alpha = \omega y \beta = \omega en el teorema anterior.

Teorema 6. Si \alpha es un cardinal infinito, entonces \alpha+\alpha = \alpha y \alpha \alpha = \alpha.
Teorema 7. Si \alpha y \beta son cardinales mayores que cero y alguno de ellos es infinito, entonces \alpha+\beta =  \alpha \beta = \max \{\alpha, \beta \}.
Teorema 8. Si (A_{i})_{i \in I} es una familia de conjuntos y |A_{i}|= \alpha_{i} para i \in I, entonces |\bigcup_{i \in I} A_{i} | \leq  |I | \bigcup_{i \in I} | A_{i} | \leq |I | \sum_{i \in I} \alpha_{i}.
Definición 6. Sean \alpha y \beta dos cardinales y sean A y B dos conjuntos tales que |A| =  \alpha y |B| = \beta. Definimos \alpha^{\beta} como el cardinal del conjunto A^{B} formado por todas las aplicaciones f:B \rightarrow A.
Teorema 9. Para cualesquiera cardinales \alpha, \beta, \gamma, \delta, se cumplen:
a) Si \alpha >0 y \beta \leq \gamma, entonces \alpha^{\beta} \leq \alpha^{\gamma}.
b) Si \alpha \leq \gamma, entonces \alpha^{\delta} \leq \gamma^{\delta}.

Acabamos esta colección de resultados con un teorema.

Teorema 10. Si \alpha, \beta y $\gamma$ son cardinales, entonces
a) \alpha^{\beta+\gamma} = \alpha^{\beta} \alpha^{\gamma}.
b) \alpha^{\beta \gamma} = (\alpha^{\beta})^{\gamma}.
c) (\alpha \beta)^{\gamma} = \alpha^{\gamma} \beta^{\gamma}.
Anuncios

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

Curso EVT. Lectura 23. Cardinales (6)

Vamos a ver que cualquier intervalo acotado no vacío y que no se limite a un solo punto (degenerado) es equipotente a toda la recta real.

Teorema 1. Todo intervalo I \subset \mathbb{R}, no vacío ni degenerado, es equipotente a \mathbb{R}

Prueba. Consideremos los intervalos unidad I_{1}=[0,1], I_{2}=[0,1[ e I_{3} =]0,1]. Vamos a establecer una biyección entre dichos intervalos y el intervalo ]0,1[. Comenzamos con el intervalo cerrado I_{1}. Sea A = \mathbb{Q} \cap I_{1} el conjunto de los racionales del intervalo cerrado unidad y sea B=\mathbb{Q} \cap ]0,1[ el conjunto de los racionales del intervalo abierto unidad. Como A y B son subconjuntos infinitos de un conjunto numerable serán también infinito numerables por lo que existe una biyección g_{1} entre A y B. Vamos a definir entonces la aplicación f_{1} entre [0,1] y ]0,1[ mediante

f_{1}(x) = x, si x \in [0,1]-A
f_{1}(x) = g_{1}(x), si x \in A.

Esta aplicación es una biyección entre [0,1] y ]0,1[. Para el resto de intervalos sólo hay que modificar ligeramente la argumentación para obtener las correspondientes biyecciones f_{2} y f_{3}. Sean ahora a y b dos números reales con a<b. Podemos definir cualquier intervalo no vacío, acotado y no degenerado como alguno de los [a,b], [a,b[, ]a,b] y ]a,b[. La aplicación h(x) = \frac{1}{b-a} (x-a) es una biyección de cada uno de ellos en los intervalos [0,1], [0,1[, ]0,1] y ]0,1[, respectivamente. Las composiciones f_{i} \circ h, para i=1,2,3 resultan pues biyecciones de cada uno de los intervalos [a,b], [a,b[, ]a,b] en el intervalo abierto unidad ]0,1[. Como dicho intervalo es equipotente a la recta real, cada uno de estos intervalos resulta también equipotente a la recta real. Finalmente, el intervalo abierto ]a,b[ se pone en biyección con el intervalo abierto unidad mediante h y por ello también es equipotente a \mathbb{R}. Esto termina nuestra demostración.

Sea X un conjunto y sea A un subconjunto de X.

Definición 1. La función característica o indicadora de A es la función \lambda_{A} : X \rightarrow \{0, 1\}, dada por \lambda_{A} (x) = 1 si x \in A y \lambda_{A}(x) = 0 si x \notin A.

Veamos algunas interesantes propiedades de esta función.

Teorema 2. Sean A y B subconjuntos de X. Se cumplen
a) \lambda_{X} =1 y \lambda_{\emptyset} = 0.
b)A \subset B, si y sólo si \lambda_{A} \leq \lambda_{B}.
c)\lambda_{A} = \lambda_{B} si y sólo si A=B.
d)\lambda_{A \cap B} = \lambda_{A} \lambda_{B}.
e)\lambda _{A \cup B} + \lambda_{A \cap B} = \lambda_{A} + \lambda_{B}.
e)\lambda_{\overline{A}} = 1 - \lambda_{A}

Prueba. Trivialmente, para todo x \in X será \lambda_{X} (x) = 1 por lo que la función característica de la totalidad del conjunto será la función constante e igual a la unidad. Análogamente, como ningún x \in X pertenece al conjunto vacío, la función característica del conjunto vacío será la función constante e igual a cero. Esto prueba el apartado (a). Sean ahora A y B dos conjuntos y supongamos que A \subset B. En tal caso, para cada x \in A tenemos x \in B por lo que \lambda_{A} (x) =1 \leq 1 =\lambda_{B} (x). Si fuera x \in B pero x \notin A, tendríamos que \lambda_{A} (x) = 0 \leq 1 = \lambda_{B} (x) y, para acabar, si fuera x \notin B, entonces también x \notin A por lo que \lambda_{A} (x) = 0 \leq 0 = \lambda_{B} (x). En todos los casos es \lambda_{A} (x)  \leq  \lambda_{B} (x), lo que permite escribir la desigualdad \lambda_{A} \leq \lambda_{B}. El recíproco es análogo. Por tanto, hemos probado (b). Para probar (c), bastará darse cuenta que A = B si y sólo si A \subset   B y B \subset A y aplicar (b). El resto de demostraciones las dejamos a cargo del lector por su simplicidad.

Sea $X$ un conjunto cualquiera. Designamos por \mathcal{P}(X) el conjunto de todos sus subconjuntos (o partes).

Teorema 3. El conjunto \{0,1\}^{X} de todas las funciones características de X es equipotente al conjunto de sus partes \mathcal{P}(X).

Prueba. Sea la función f: \mathcal{P} (X) \rightarrow \{0,1\}^{X}, definida por f(A) = \lambda_{A} para cada A \in \mathcal{P}(X). Veremos que es una biyección. En efecto, si fuera \lambda_{A} = \lambda_{B}, entonces A = B por (c) del teorema 2. Esto prueba que f es inyectiva. Sea ahora h un elemento cualquiera de \{0,1\}^{X}. El conjunto A = \{ x \in X : h(x) =1 \} nos sirve para comprobar que \lambda_{A} = h y concluimos que f es sobreyectiva.

Con este resultado y apoyándonos en el teorema 1 de la lectura 22 estamos en condiciones de probar un interesante resultado.

Teorema 4. El conjunto de las partes de \mathbb{N} es no numerable.

Prueba. Evidentemente, el conjunto \{0,1 \}^{\mathbb{N}} de las funciones características de \mathbb{N} coincide con \Delta. Por tanto, aplicando el teorema 3 es \mathcal{P}(\mathbb{N}) equipotente a \Delta y aplicando el teorema 1 de la lectura 22 resultará que al ser \Delta no numerable también lo es \mathcal{P}(\mathbb{N}). Aquí termina la demostración.

Existe un resultado más general debido a Cantor que relaciona un conjunto con el conjunto de sus partes.

Teorema 5. Sea A un conjunto. Entonces |A |< |\mathcal{P}(A)|

Prueba. En primer lugar, la aplicación f: A \rightarrow \mathcal{P}(A), dada por f(x) = \{x \} es inyectiva. Por tanto, |A| \leq |\mathcal{P}(A)|. Veamos que no existe ninguna aplicación sobreyectiva entre A y el conjunto de sus partes utilizando la reducción al absurdo. Sea \phi : A \rightarrow \mathcal{P}(A) tal aplicación sobreyectiva y consideremos el conjunto B = \{x \in A : x \notin \phi(x) \}. Para dicho conjunto B podríamos hallar al menos un b \in X tal que \phi(b) = B. Por tanto, si b \in B concluiremos que b \notin \phi(b) = B y si b \notin B concluiremos que b \in \phi(b) =B. En cualquier caso hay contradicción. Así pues, no existe tal aplicación sobreyectiva y el teorema queda demostrado.

Esto permite construir una serie de infinitos cada vez mayores partiendo de un conjunto infinito cualquiera. Por ejemplo, partimos de los naturales y el conjunto de sus partes es “mayor” que los naturales. El conjunto de las partes de las partes será mayor y así sucesivamente. En la siguiente lectura veremos que el conjunto de los números reales es equipotente al de las partes de los naturales y como herramienta de esta prueba definiremos el llamado “Conjunto de Cantor”.

Curso EVT. Lectura 22. Cardinales (5)

Probaremos ahora la existencia de conjuntos infinitos no numerables.

Teorema 1. El conjunto de las sucesiones binarias \Delta = \{(a_{1}, a_{2}, \ldots ), \forall i, a_{i} = 0 \vee  a_{i} =1 \}
es infinito y no es numerable.

Prueba. En primer lugar, el conjunto \Delta es infinito pues no podemos hallar ninguna aplicación inyectiva f: \Delta \rightarrow S(n). En efecto, si tomamos n sucesiones de ceros y unos diferentes, siempre podremos hallar una sucesión de ceros y unos diferente a las n anteriores sin más que invertir (o sea cambiar cero por uno o uno por cero) el primer término de la primera, el segundo de la segunda y así sucesivamente. Esto dará lugar a una nueva sucesión diferente a las anteriores y, en consecuencia, la aplicación f no podrá ser inyectiva. Supongamos que es numerable, probaremos que entonces obtenemos una contradicción siguiendo el mismo razonamiento que en el caso anterior. Escribamos pues, \Delta como una enumeración.

\Delta = \{ a_{1}, a_{2}, a_{3}, \ldots, a_{n}, \ldots \}.

Utilizando la enumeración escribimos una matriz de ceros y unos en la forma

a_{1} : x_{11} \quad  x_{12} \quad x_{13} \quad \cdots
a_{2} : x_{21}\quad x_{22} \quad x_{23} \quad \cdots
a_{3} : x_{31} \quad x_{32} \quad x_{33} \quad \cdots
\vdots \quad \quad \quad \cdots

Obtenemos una nueva sucesión que no está en la lista sin más que intercambiar los ceros y los unos en la diagonal: b_{n} = 1 - x_{nn}. De esta manera hallamos una contradicción a nuestra hipótesis de la enumeración y el conjunto \Delta resulta no numerable.

El conjunto de los números reales también resulta ser no numerable. La prueba se basa también en el mismo razonamiento “diagonal” que hemos usado en el teorema 1. Pero antes debemos repasar la expresión decimal de los reales en el intervalo unidad. Recordemos que los reales 0 <x<1 se expresan en forma decimal mediante

0.x_1 x_2 x_3 \ldots x_n \ldots

donde x_i \in \{0,1,2, \ldots, 9\} y eventualmente si existe j tal que x_j=0 para todo k \geq j, obtenemos una expresión finita sin más que prescindir de los decimales x_j, j \geq k (este es el caso de los decimales exactos). Ahora bien, sabemos que en este caso también existe una expresión infinita en la que x_{j}=9 para j \geq k. Por ejemplo,

0.124 = 0.123999999 \ldots.

Para evitar esta doble expresión admitiremos sólo expresiones infinitas.

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

Prueba. Probaremos que el intervalo abierto unidad (0,1) no es numerable y como la aplicación f(x) = -\cot(\pi x) es una biyección entre (0,1) y la recta real concluiremos que la recta real tampoco es numerable. Supongamos que (0,1) es numerable y escribamos los elementos de dicho intervalo en forma de decimales con infinitas cifras y donde el número de ceros es finito. Por ejemplo, en lugar de 0,3 escribiremos 0,29999  \ldots. Esta notación nos proporcionaría una enumeración completa y unívoca:

a_{1} :0. x_{11} \quad  x_{12} \quad x_{13} \quad \cdots
a_{2} :0. x_{21}\quad x_{22} \quad x_{23} \quad \cdots
a_{3} :0. x_{31} \quad x_{32} \quad x_{33} \quad \cdots
\vdots \quad \quad \quad \cdots

Podemos construir un número real y =0,b_{1} b_{2} b_{3} \ldots del intervalo (0,1) que no está en la lista, tomando para cada i \in \mathbb{N} el valor b_{i} \neq 0, c_{ii}. Llegamos a una contradicción y por tanto, (0,1) no es numerable.

Curso EVT. Lectura 21. Cardinales (4)

Recordemos que un conjunto A es numerable si es vacío, finito o equipotente al conjunto de los enteros positivos. Ahora vamos a dar propiedades de tales conjuntos y nos vamos a basar en la visto en lecturas anteriores.

Teorema 1. Todo subconjunto de un conjunto numerable es numerable.

Prueba. Sea A numerable y sea B un subconjunto de A. Sabemos que existe una aplicación inyectiva g:A \rightarrow \mathbb{N} y que la aplicación f:B \rightarrow A, dada por f(x)=x es inyectiva. En consecuencia, la composición g \circ f:B \rightarrow \mathbb{N} es inyectiva y B es numerable.

Teorema 2. El conjunto \mathbb{N} \times \mathbb{N} es numerable.

Prueba. Sea la aplicación

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

dada por f(m,n) = 2^{m} 3^{n}. Vemos que es inyectiva. En efecto, si f(m,n)= f(a,b), entonces 2^{m} 3^{n} = 2^{a} 3^{b}, de donde 2^{m-a} = 3^{n-b} y esto sólo es posible si m-a=n-b=0. En consecuencia, f es inyectiva y \mathbb{N} \times \mathbb{N} es numerable.

Es fácil comprobar que este teorema implica el corolario siguiente.

Corolario 1. Si A y B son numerables. Entonces A \times B es numerable.

La demostración es sencilla y se deja a cargo del lector.

Teorema 3. La unión numerable de conjuntos numerables también es un conjunto numerable.

Prueba. Consideremos una colección (A_n) numerable de conjuntos numerables. Si alguno de ellos es vacío se suprime y no cambia la unión. Por ello no perdemos generalidad si consideramos el caso en que todos son no vacíos. Para cada n, existe una aplicación inyectiva

f_n : A_n \rightarrow \mathbb{N}.

Utilizando este hecho vamos a construir una aplicación inyectiva entre \cup_{n} A_n y \mathbb{N} \times \mathbb{N}. En efecto, sea a \in \cup_{n} A_n. Esto implica que el conjunto C_a=\{n \in \mathbb{N}: a \in A_n \} es no vacío. Al ser este un subconjunto de los enteros positivos, existe y es único el valor m_a = \min C_a. Definimos f(a) = (m_a, f_{m_{a}}(a)) para cada a de la unión y obtenemos una inyección. Así es ya que si fuera f(a)=f(b), entonces m_a = m_b=k y también f_{m_a}(a) = f_{m_b} (b), luego a,b \in A_k y f_k(a)=f_k(b). Como f_k es inyectiva, es a=b. Esto termina la demostración.

Teorema 4. El conjunto \mathbb{Z} de los enteros es numerable y también lo es el conjunto \mathbb{Q} de los racionales.

Prueba. Sabemos que \mathbb{Z} = \mathbb{N} \cup \{0\} \cup \{-n : n \in \mathbb{N}\}. Como cada uno de estos conjuntos es numerable, su unión también lo es y así el conjunto de los enteros es numerable. Sea \mathbb{Q} el conjunto de los racionales. Entonces \mathbb{Q} = \{ \frac{p}{q} : p,q \in \mathbb{Z}, q \neq 0\}. La aplicación

g : \mathbb{Z} \times (\mathbb{Z}-\{0\}) \rightarrow \mathbb{Q}.

dada por f(p,q) =\frac{p}{q} es sobreyectiva. Como \mathbb{Z} \times (\mathbb{Z}-\{0\}) es numerable (al ser un subconjunto de \mathbb{Z} \times \mathbb{Z}), resulta que \mathbb{Q} es numerable.

Todavía quedan más resultados que expondremos en un par de entradas posteriores.

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.

Curso EVT. Lectura 19. Cardinales (2)

Recordemos que un conjunto E es D-infinito si es posible encontrar una aplicación f:E \rightarrow E que es inyectiva y no sobreyectiva. Existe otra forma de definir un conjunto infinito que parte de su idea contraria.

Definición 1. Sea \mathbb{N} el conjunto de los números naturales. Un conjunto E es finito si es vacío o existe un subconjunto S(n) =\{ 1, 2, \ldots, n \}, de \mathbb{N} tal que E es equipotente a S(n). En otro caso diremos que el conjunto es infinito.

Si probamos que S(n) es D-finito, entonces por (d) del teorema 3 de la lectura 18, se sigue que todo conjunto finito es D-finito. Para hacer tal prueba suponemos conocida la buena ordenación de los números naturales.

Teorema 1. Para todo n \in \mathbb{N} el conjunto S(n) = \{1,2, \ldots, n\} es D-finito.

Prueba. Supongamos que C es el subconjunto de los naturales formado por aquellos n para los cuales es posible la existencia de una biyección de S(n) en uno de sus subconjuntos propios. Sea m = \min C (cuya existencia está garantizada por la buena ordenación), entonces existe h: \{1,2, \ldots, m \} \rightarrow B, donde B \subset \{1,2, \ldots, m\}, pero B \neq \{1,2, \ldots, m\}. Si suponemos que m \notin B, se sigue que B \subset \{1,2, \ldots, m-1\} y de aquí h(\{1,2, \ldots, m-1\} \subset B-\{h(m)\}. Por tanto,

h(\{1,2,\ldots, m-1\}) \subset B-\{h(m)\} \subsetneq B \subset \{1,2, \ldots, m-1\}).

cevt19
Esto significa que h aplica el conjunto S(m-1) en uno de sus subconjuntos propios y contradice la minimalidad de m. Así pues, concluimos que m \in B. Esto da lugar a dos posibilidades:
a) Es h(m)=m. Entonces

h(\{1,2,\ldots, m-1\}) \subset B-\{m\} \subsetneq \{1,2, \ldots, m-1\}.

Lo que implica que S(m-1) se aplica mediante la biyección h en un subconjunto propio y volvemos a caer en contradicción.
b) Es h(j)=m para algun j \neq m. Pero esto no nos salva de contradicción pues podemos “reordenar” los elementos mediante la biyección g(i) = i si i \neq j,m, g(i) =j para i=m y g(i)=m para i=j para volver a la situación de (a) mediante la composición h \circ g.
Concluimos pues que no es posible encontrar biyecciones entre S(m) y alguno de sus subconjuntos propios por lo que el conjunto C es vacío y llegamos al resultado deseado.

Para terminar veremos que todo conjunto D-infinito es infinito según esta definición. Para eso necesitamos unos resultados previos.

Definición 2. Un conjunto A se dice numerable si es finito o equipotente a los enteros positivos.
Teorema 2.Son equivalentes:
a) El conjunto A es no vacío y numerable.
b) Existe una aplicación inyectiva f:A \rightarrow \mathbb{N}.
c) Existe una aplicación sobreyectiva \phi:\mathbb{N} \rightarrow A.

Prueba. (a) implica (b). Supongamos que A es no vacío y finito. Entonces existe un entero positivo n y una biyección f:A \rightarrow S(n). Como S(n) \subset \mathbb{N}, la extensión f:A \rightarrow \mathbb{N} es inyectiva. Si A es infinito numerable, existe una biyección f:A \rightarrow \mathbb{N} y dicha aplicación es trivialmente inyectiva.
(b) implica (c). Supongamos que existe una inyección f:A \rightarrow N. Sea x_0\in A, definimos \phi(x):\mathbb{N} \rightarrow A, mediante \phi(i) = x_0, si i \notin f(A) y \phi(i) = f^{-1}(i), si i \in f(A). Es fácil comprobar que \phi es sobreyectiva y que podemos escribir A= \{ \phi(1), \phi(2), \ldots, \phi(n), \ldots \}. Esto es una enumeración de A donde eventualmente existen elementos repetidos.
(c) implica (a). Sea \phi: \mathbb{N} \rightarrow A una aplicación sobreyectiva. Si A es no vacío y finito no hay nada que probar. En caso de ser infinito, escribimos como antes A= \{ \phi(1), \phi(2), \ldots, \phi(n), \ldots \} y eliminamos los elementos repetidos. Esto da lugar a una biyección y termina la demostración.

Nuestro objetivo final es probar que todo conjunto infinito es D-infinito (pues todo conjunto D-infinito es infinito en virtud de la implicación ya demostrada: A finito implica A D-finito) y para ello vamos a precisar de algunos resultados más que dejaremos para la próxima lectura.