Archivo de la categoría: Cursos

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

Curso EVT. Lectura 18. Cardinales (1)

En esta lectura vamos a introducir algunas nociones sobre la cardinalidad de los conjuntos.

Definición 1. Sean A y B dos conjuntos. Decimos que son coordinables, equivalentes o equipotentes si existe al menos una biyección (es decir, una aplicación inyectiva y sobreyectiva) entre A y B. Convenimos además en que el único conjunto equipotente al vacío es él mismo. Escribiremos A \approx B o bien |A| = |B| para notar que A y B son coordinables o equipotentes.

Se deduce fácilmente de la definición el siguiente resultado.

Teorema 1. Sean A,B y C conjuntos dados. Se cumplen las propiedades siguientes:
a) Es |A|= |A|.
b) Si es |A| = |B|, entonces |B|= |A|.
c) Si |A| = |B| y |B| = |C|, entonces |A| = |C|.

El teorema pueda dar lugar a la idea de que la relación de equipotencia entre conjuntos es una relación de equivalencia. Sin embargo, para que pudieramos afirmar tal cosa deberíamos tener una clase formada por todos los conjuntos. Esto no es posible pues la teoría axiomática de conjuntos de Zermelo-Fraenkel afirma concretamente que tal clase no es un conjunto. Así pues, nos limitaremos a afirmar que dos conjuntos A y B tienen el mismo cardinal o la misma cardinalidad o la misma potencia si son equipotentes.
La siguiente definición nos permite afinar un poco más a la hora de establecer comparaciones.

Definición 2. Sean A y B dos conjuntos. Decimos que A tiene un cardinal igual o menor que B y escribimos |A | \leq |B| si es posible hallar una aplicación inyectiva entre A y B.

La siguiente proposición da una definición equivalente.

Teorema 2. Dados los conjuntos A y B, es |A | \leq |B| si y sólo si podemos hallar un subconjunto de B equipotente a A.

Prueba. Supongamos que |A | \leq |B| entonces existe una aplicación inyectiva f: A \rightarrow B. Sea f(A) el subconjunto de B formado por las imágenes de los elementos de A. La aplicación f:A \rightarrow f(A) es una biyección puesto que es inyectiva y sobreyectiva. Recíprocamente, supongamos que existe una aplicación biyectiva g entre A y un subconjunto Y de B. Es inmediato que se trata de una aplicación inyectiva entre A y B. Esto termina nuestra demostración.

Podemos ir un paso más alla en esta definición.

Definición 3. Sean A y B dos conjuntos. Escribimos |A| < |B| si y sólo si existe una aplicación inyectiva f: A \rightarrow B pero ninguna sobreyectiva.

En este punto nos vamos a plantear la definición de conjuntos finitos e infinitos. Es importante tener claro que hay dos maneras de hacerlo y que ambas resultan equivalentes sólo en virtud del axioma de elección.

Definición 4. Un conjunto E se dice infinito (o infinito según Dedekind o D-infinito) si existe una aplicación inyectiva f:E \rightarrow E que no es sobreyectiva. Un conjunto que no es infinito se dice que es finito. En cuanto al conjunto vacío se considera finito por convenio.

Según la definición anterior. El conjunto \mathbb{N} de los enteros positivos es infinito pues la aplicación

f(n) = n+1

resulta inyectiva pero no suprayectiva. En efecto, si f(n) = f(m) es n+1=m+1 de donde n=m. Sin embargo, si tomamos m=1 no podremos hallar un entero positivo n tal que n+1=1 (el cero no vale pues no lo consideramos miembro de los enteros positivos).
Se puede probar fácilmente que un conjunto A es D-infinito si existe una biyección entre A y uno de sus subconjuntos propios B. En efecto, supongamos que existe una aplicación f:A \rightarrow A que es inyectiva pero no sobreyectiva, entonces tomando B=f(A) es B \subset A con B \neq A, por lo que la restricción f:A \rightarrow B es una biyección entre A y el subconjunto propio B. El recíproco es inmediato. Los siguientes resultados son más útiles.

Teorema 3. Sean E y F dos conjuntos y sea f:E \rightarrow F una aplicación,entonces
(a) Todo superconjunto de un conjunto infinito es infinito.
(b) Todo subconjunto de un conjunto finito es finito.
(c) Si f es biyectiva y E es infinito, entonces F es infinito.
(d) Si f es biyectiva y E es finito, entonces F es finito.
(e) Si f es inyectiva y E es infinito, entonces F es infinito.
(f) Si f es inyectiva y F es finito, entonces E es finito.
(g) Si f es sobreyectiva y E es finito, entonces F es finito.
(h) Si f es sobreyectiva y F es infinito, entonces E es infinito.

Prueba. (a) Supongamos que E es infinito y que E \subset F. Si E=F no hay nada que probar y si E \neq F, sabemos que existe una aplicación f:E \rightarrow E que es inyectiva y no sobreyectiva (pues E es infinito). La aplicación g:F \rightarrow F dada por g(x) =f(x), si x \in E y g(x)=x, si x \in F-E es inyectiva (esto es inmediato) pero no es sobreyectiva pues sabemos que al menos existe un y \in E tal que f^{-1}(y)= g^{-1}(x) = \emptyset.
La prueba de (b) es inmediata pues (a) implica que si F es finito y E \subset F, entonces E es finito. Utilizamos el argumento contrapositivo.
(c). Si f:E \rightarrow F es una biyección y g:E \rightarrow E es inyectiva pero no sobreyectiva, tenemos que f \circ g \circ f^{-1}:F \rightarrow F es inyectiva (pues es composición de aplicaciones inyectivas) pero no sobreyectiva (si lo fuera también lo sería f^{-1} \circ(f \circ g \circ f^{-1}) \circ f=g).
(d) Si f:E \rightarrow F es biyectiva también lo es f^{-1} :F \rightarrow E por lo que aplicando (c) se tiene que si E es finito también lo será F (en realidad aplicamos de nuevo el argumento contrapositivo).
(e) Si E es infinito y f:E \rightarrow F es inyectiva, entonces podemos definir una biyección f:E \rightarrow f(E). Por (c) resulta que f(E) \subset F es infinito y por (a) es F infinito.
(f) Es el contrarecíproco de (e) y, en consecuencia, válido.
(g) Esta demostración precisa del axioma de elección. Una de sus consecuencias es que si f:E \rightarrow F es sobreyectiva, entonces existe una aplicación g:F \rightarrow E que es inyectiva. Por tanto, si E es finito entonces F también lo es por (f) y si F fuera infinito entonces E sería infinito por (e).
(h) Es el contrarecíproco de (g) y por tanto es válido.