Archivo de la categoría: Teoría de Conjuntos

Equicardinalidad de algunos intervalos

Siempre resulta interesante analizar el concepto matemático actual del infinito. Una de las maneras de mostrar su profundidad y su carácter no intuitivo es a través de ciertas demostraciones que se deducen de él. En esta entrada vamos a mostrar una de tales demostraciones. En concreto, probaremos que los intervalos ]0,1[ y [0,1[ de la recta real tienen el mismo número de elementos (o puntos como se  suele decir).  Sea el conjunto

A = \{ \frac{1}{n+1} : n \in \mathbb{N} \} \cup \{ 0 \} .

Tal conjunto está incluido en el intervalo [0,1[. Además, si B = A - \{0 \}, es B un subconjunto de ]0,1[. Una vez considerados estos conjuntos, definimos una aplicación f:[0,1[ \rightarrow ]0,1[, mediante

f(x) = \frac{1}{2} si x=0,

f(x) = \frac{1}{n+2}, si x = \frac{1}{n+1},

f(x) = x, si x \in [0,1[ -A.

En realidad, tal aplicación deja intactos a todos los elementos de [0,1[ que no están en A, a los que están en A y no son cero los “mueve” un lugar en la sucesión que define a A y al cero le hace corresponder el lugar libre que deja la sucesión (el primer término). Es fácil comprobar que este arreglo hace que f sea una biyección. En efecto, las restricciones

f(A) = \{ \frac{1}{2} \} \cup \{ \frac{1}{n+2}, n=1,2, \ldots, \} = B,

f([0,1[ -A) = ]0,1[ -B,

son biyectivas y esto significa que f es también biyectiva. La siguiente imagen ayuda a comprender estas ideas

biyeccion3

 

En realidad, hemos mostrado que a pesar de que parece que el intervalo [0,1[ tiene un punto más (el cero) que el intervalo ]0,1[, esto no es así pues ambos son igual de “infinitos”.

Anuncios

Interesante equicardinalidad de conjuntos de funciones

Sean tres conjuntos A, B y C. Supongamos que los conjuntos A y B son equinumerosos (tienen el mismo cardinal). Sean

A^{C} = \{ f: C \rightarrow A \},

B^{C} = \{g: C \rightarrow B \},

los conjuntos de las funciones f de C en A y de las funciones g de C en B, respectivamente. Probaremos que A^{C} y B^{C} tienen el mismo cardinal. Para ello vamos a utilizar la biyección

f: A \rightarrow B

que, por hipótesis, existe entre A y B. Con ella, definimos la aplicación

\lambda : A^{C} \rightarrow B^{C},

dada por \lambda (h) = f \circ h. Esta aplicación está bien definida (ver imagen)

Imagen

pues a cada aplicación de C en A le hacemos corresponder una aplicación de C en B. Probaremos que \lambda es una biyección. El método que vamos a emplear es definir otra aplicación \mu que resulta ser inversa de \lambda. Sea pues

\mu : B^{C} \rightarrow A^{C}

dada por \mu (j) = f^{-1} \circ j.  Es fácil ver que está bien definida (ver imagen)

Imagen

Sólo nos resta ver las relaciones siguientes:

(\mu \circ \lambda)( h) = \mu (\lambda (h) ) = \mu (f \circ h) = f^{-1} \circ f \circ h =h,

(\lambda \circ \mu) (j) = \lambda (\mu (j )) = \lambda (f^{-1} \circ j) = f \circ f^{-1} \circ j = j.

En efecto, tales relaciones muestran que \lambda y \mu son inversas una de la otra por lo que son biyecciones y concluimos que el cardinal de A^{C} es igual al cardinal de B^{C}.

Las sucesiones binarias y la cardinalidad del continuo (2)

Vamos a probar que el conjunto de todas las sucesiones binarias tiene el mismo cardinal que el de los números reales. Esto, en virtud del resultado demostrado anteriormente, nos muestra que el conjunto de las partes de \mathbb{N} tiene el cardinal del continuo.

Si A es un conjunto, escribimos |A| para denotar su cardinal. Si existe una aplicación inyectiva f:A \rightarrow B, escribimos |A| \leq |B|. En esta demostración vamos a usar el teorema de Cantor-Schröder-Bernstein que nos dice que si |A| \leq |B| y |B| \leq |A|, entonces |A| = |B|.
Sea el intervalo [0,1[ de la recta real. Cada x de dicho intervalo se puede expresar en la forma
x = \sum_{n=1}^{\infty} x_{n} 2^{-n},
donde (x_{n}) es una sucesión binaria. En el caso de que x= \frac{1}{2^{p}} con p \in \mathbb{N}, podemos obtener sucesiones binarias (x_{n}), (y_{n}) distintas tales que
x = \sum_{n=1}^{\infty} x_{n} 2^{-n} = \sum_{n=1}^{\infty} y_{n} 2^{-n}.
Por ejemplo, las sucesiones binarias
(x_{n}) = (0,1,1,1,1, \ldots, 1, \ldots), (y_{n}) = (1,0,0,0,0, \ldots, 0, \ldots)
dan lugar a \frac{1}{2}. Para evitar esto, consideramos que cada x se expresa en forma binaria con un número finito de unos. De esta manera, a cada x del intervalo [0,1[ le correspondería una única representación binaria y, en consecuencia, una única sucesión binaria. Así pues, la aplicación
f:[0,1[ \rightarrow \{0,1 \}^{\mathbb{N}},
que asigna a cada x del intervalo [0,1[ la sucesión binaria (x_{n}) tal que el conjunto \{n \in \mathbb{N}: x_{n} =1 \} es finito y x = \sum_{n=1}^{\infty} x_{n} 2^{-n}, es una aplicación inyectiva. Esto significa que |[0,1[| \leq |\{0,1 \}^{\mathbb{N}}| .
Sea (x_{n}) una sucesión binaria. La aplicación
\phi: \{0,1\}^{\mathbb{N}} \rightarrow [0,1[,
dada por \phi((x_{n})) =\sum_{n=1}^{\infty} x_{n} 10^{-n} , está bien definida y es inyectiva. En efecto, los desarrollos de la forma \sum_{n=1}^{\infty} x_{n} 10^{-n} con x_{n} \in \{0,1 \} dan lugar a números reales del intervalo [0,1[. Además, al no existir en tales desarrollos una infinidad de nueves, resultan ser únicos. Por tanto, |\{0,1 \}^{\mathbb{N}}|\leq |[0,1[|. Aplicando Cantor-Schröder-Bernstein tenemos que |\{0,1 \}^{\mathbb{N}}|=|[0,1[|, lo que prueba que el conjunto de las sucesiones binarias tiene la cardinalidad del continuo.

Las sucesiones binarias y la cardinalidad del continuo (1)

Sea \mathcal{P}(\mathbb{N}) el sistema de todos los posibles subconjuntos de \mathbb{N} y sea \Xi el conjunto de todas las posibles sucesiones binarias. Probaremos que :
(a) los conjuntos \Xi y \mathcal{P}(\mathbb{N}) tienen la misma cardinalidad.
(b) Los conjuntos \Xi y \Xi \times \Xi tienen la misma cardinalidad.
(a) Sean A y B dos conjuntos no vacíos. El conjunto de todas las aplicaciones f:A \rightarrow B, se notará por B^{A}. De acuerdo con este convenio, el conjunto \Xi de todas las sucesiones binarias se puede denotar por \{0,1 \}^{\mathbb{N}} y así lo haremos de ahora en adelante. Sea A un subconjunto de \mathbb{N}. La aplicación
\chi_{A} : \mathbb{N} \rightarrow \{0, 1 \}
dada por \chi_{A}(n) = \left\{ \begin{array}{c}  0, \quad \text{si} \quad n \notin A \\  1, \quad \text{si} \quad n \in A \\  \end{array}  \right.
está bien definida y se trata de un elemento de \{0,1 \}^{\mathbb{N}}. Probaremos que la aplicación
\theta : \mathcal{P}(\mathbb{N}) \rightarrow \{0,1 \} ^{\mathbb{N}}que asigna a cada subconjunto A de \mathbb{N}, la aplicación \chi_{A}, es una biyección. En efecto, supongamos que A y B son subconjuntos diferentes de \mathbb{N}. Entonces existe r \in A tal que r \notin B o bien existe m \in B tal que m \notin A. En el primer caso, \chi_{A}(r)=1 pero \chi_{B}(r)=0 y, por tanto, \chi_{A} \neq \chi_{B} y en el segundo caso \chi_{A}(m)= 0 pero \chi_{B}(m)=1 por lo que \chi_{A} \neq \chi_{B}. Esto significa que \theta es inyectiva. Probaremos que también es sobreyectiva. Sea f una aplicación cualquiera de \mathbb{N} en \{0, 1 \} . El conjunto f^{-1}(1)= \{n \in \mathbb{N} : f(n)=1 \} está bien definido y resulta ser un subconjunto de \mathbb{N} para el que trivialmente \chi_{A} = f. La biyección \theta nos muestra que \{0,1 \}^{\mathbb{N}} y  \mathcal{P}(\mathbb{N}) tienen la misma cardinalidad.

(b). Sean (a_{n}) y (b_{n}) dos sucesiones binarias. Formamos la sucesión (c_{n}) mediante
c_{n} = \left\{ \begin{array}{l}  a_{\frac{n+1}{2}}, \quad \text{si} \quad n \quad \text{es impar} \\  b_{\frac{n}{2}}, \quad \text{si} \quad n \quad \text{es par} \\  \end{array}  \right.
Es decir
(c_{n}) =(a_{1}, b_{1}, a_{2}, b_{2}, a_{3}, b_{3}, \ldots, a_{n}, b_{n}, \ldots ).
Es claro que (c_{n}) es una sucesión binaria. La aplicación
h: \{0,1 \}^{\mathbb{N}} \times \{0, 1\}^{\mathbb{N}} \rightarrow \{0, 1\}^{\mathbb{N}},
tal que h((a_{n}), (b_{n})) = (c_{n}) es una biyección.

En efecto, sean (a_{n}), (b_{n}), (a'_{n}), (b'_{n}) sucesiones binarias y supongamos que ((a_{n}), (b_{n})) \neq ((a'_{n}), (b'_{n})). Entonces puede suceder que (a_{n}) \neq (a'_{n}) y hallaríamos un n_{0} \in \mathbb{N} para el (a_{1}, b_{1}, \ldots, a_{n_{0}}, b_{n_{0}}, \ldots ) \neq (a'_{1}, b'_{1}, \ldots, a'_{n_{0}}, b'_{n_{0}}, \ldots ).

El mismo razonamiento es aplicable para el caso en que (b_{n}) \neq (b'_{n}). Así pues, h es inyectiva. Sea ahora (e_{n}) una sucesión binaria. Consideremos las subsucesiones
(e_{2n-1}), (e_{2n}).
Es inmediato que h((e_{2n-1}), (e_{2n})) = (e_{n}). Esto significa que h es también sobreyectiva y termina la demostración.

El apartado (a) nos muestra que el cardinal de las partes de \mathbb{N} coincide con el cardinal de las sucesiones binarias. Este hecho nos sirve de puente para probar que el cardinal del conjunto de las partes de \mathbb{N} es el cardinal del continuo (es decir, del conjunto de los números reales).  Demostraremos este hecho en una posterior entrada.

Curioso ejercicio de límites superior e inferior

Sabemos que los números racionales de la recta real forman un conjunto numerable. Por ello existe una enumeración en la forma \mathbb{Q} = \{x_{1}, x_{2}, \ldots, x_{n}, \ldots \}. Es importante saber que tal enumeración no implica una ordenación x_{1} < x_{2}< \ldots <x_{n} < \ldots . Tan sólo es el resultado de una aplicación biyectiva f: \mathbb{N} \rightarrow \mathbb{Q}. El siguiente ejercicio es una cuestión de límites superior e inferior de conjuntos pero en su resolución se ha tenido en cuenta este hecho. Se trata de considerar la sucesión de intervalos de la recta real dada por

A_{n} =(x_{n}-1, x_{n}+1), n=1,2, \ldots,

donde x_{n} es el enésimo racional de una enumeración de los racionales. Se nos pide el límite superior e inferior de dicha sucesión.

Supongamos que x pertenece al límite inferior de la sucesión (A_{n})_{n}, entonces x pertenece a todos los elementos de la sucesión, excepto quizás a un número finito de ellos. Es decir, hallaremos un n_{0} tal que x \in A_{n} si n \geq n_{0}. Teniendo en cuenta la definición de la sucesión, esto significa que

x_{n}-1 < x < x_{n}+1 si n \geq n_{0}.

De manera equivalente

|x-x_{n}| <1, para todo n \geq n_{0}.

Ahora es cuando hay que tener cuidado con lo que significa considerar la enumeración de los racionales de n_{0} en adelante. La primera consecuencia de la desigualdad anterior es que

|x_{n}-x_{n_{0}}| = |x_{n}-x+x-x_{n_{0}}| \leq |x_{n}-x|+|x-x_{n_{0}}| <2,

si n es mayor que n_{0}. Lo que nos lleva a que \{x_{n_{0}}, x_{n_{0}+1}, \ldots, x_{m}, \ldots \} \subset (x_{n_{0}}-2, x_{n_{0}}+2). Esto es, todos los racionales, menos un número finito de ellos se hallan en un entorno de radio 2 del racional x_{0}. Pero esto es absurdo pues sabemos que hay una infinidad de racionales en cualquier intervalo no vacío de la recta real. Así pues, \lim \inf A_{n} = \emptyset. Veamos ahora el caso del límite superior. Si x pertenece a \lim \sup A_{n} entonces se hallará en una infinidad de A_{n}. Por ejemplo,  podemos ver que cualquier x real que cumpla

\frac{1}{n}-1 < x < \frac{1}{n}+1, para todo n,

pertenece a \lim \sup A_{n} pues se halla en una infinidad de conjuntos de la forma (x_{n}-1, x_{n}+1), con x_{n} racional. El lector puede comprobar con la siguiente figura que (0,1) \subset \lim \sup A_{n}.

Imagen

Es fácil ver que “trasladando” esta argumentación podemos “cubrir” toda la recta real. Por ejemplo, si sumamos \frac{1}{2}, resulta

\frac{1}{2}+\frac{1}{n}-1 <x < \frac{1}{2} + \frac{1}{n}+1, para todo n,

Luego es (\frac{1}{2}, \frac{3}{2}) \subset \lim \sup A_{n}. Por tanto, \lim \sup A_{n} = \mathbb{R}.

Un caso de convergencia de series de funciones indicadoras

En el caso de una sucesión de subconjuntos disjuntos (A_{n})_{n} de un conjunto X podemos garantizar la igualdad:

\chi_{\cup_{n=1}^{\infty} A_{n}} = \sum_{n=1}^{\infty} \chi_{A_{n}}.

Debemos demostrar que para cada x \in X, la serie
\sum_{n=1}^{\infty} \chi_{A_{n}}(x).
converge a \chi_{\cup_{n=1}^{\infty} A_{n}}(x). Sabemos que
\chi_{\cup_{n=1}^{\infty} A_{n}}(x) = \sup \{ \chi_{A_{n}}(x) : n \in \mathbb{N} \}.
Si x pertenece a \cup_{n=1}^{\infty} A_{n}, entonces x pertenece a uno y sólo uno de los conjuntos A_{n} (ya que la sucesión es disjunta). Sea x \in A_{r}. Entonces
\chi_{A_{k}}(x) = 0, \quad \text{si} \quad k \neq r,
pero
\chi_{A_{r}}(x) = 1
Por tanto,
\sup \{ \chi_{A_{n}}(x) : n \in \mathbb{N} \}= \sup \{0,1 \} = 1.
Por otro lado,
\sum_{k=1}^{r-1} \chi_{A_{k}} (x) = 0,
mientras que
\sum_{k=1}^{s} \chi_{A_{k}} (x) = 1, \quad \text{si} \quad s \geq r.
En consecuencia,
\sum_{n=1}^{\infty} \chi_{A_{n}} (x) = \lim_{n} \sum_{k=1}^{n}\chi_{A_{k}}(x) = 1.
Para acabar, si x \notin \cup_{n=1}^{\infty} A_{n}, entonces x \notin A_{n} para todo n y de aquí
\sup \{ \chi_{A_{n}}(x) : n \in \mathbb{N} \}= \sup \{0\} = 0,
y también
\sum_{k=1}^{n} \chi_{A_{k}} (x) = 0, \quad \text{para todo} \quad n.
Por ello
\sum_{n=1}^{\infty} \chi_{A_{n}} (x) = \lim_{n} \sum_{k=1}^{n}\chi_{A_{k}}(x) = 0.
Esto termina la demostración.

Diferencia simétrica generalizada

La diferencia simétrica entre dos conjuntos A y B es el conjunto A \Delta B de los elementos que se hallan sólo en uno de los conjuntos. Más precisamente,

A \Delta B = (A \cup B) - (A \cap B) = (A-B) \cup (B-A).

Diferencia simétrica de dos conjuntos.

Diferencia simétrica de dos conjuntos.

La diferencia simétrica es una operación conmutativa y asociativa. Esto permite generalizarla para un número n de conjuntos. Es decir, tiene sentido la escritura

\Delta_{i=1}^{n} E_{i},

donde E_{1}, E_{2}, \ldots, E_{n} es una colección de n subconjuntos de un conjunto dado X. Probaremos que \Delta_{i=1}^{n} E_{i} es el conjunto de los elementos de X que se hallan justo en un número impar de conjuntos E_{i}.

Diferencia simétrica de tres conjuntos.

Diferencia simétrica de tres conjuntos.

Hacemos la prueba por inducción sobre n. Para n=1 y n=2 es inmediata por definición de diferencia simétrica. Sea cierto para k \geq 2 y sea x \in \Delta_{i=1}^{k+1} E_{i}. Como

\Delta_{i=1}^{k+1} E_{i} = (\Delta_{i=1}^{k} E_{i}) \Delta E_{k+1},

entonces x \in \Delta_{i=1}^{k} E_{i} y x \notin E_{k+1} o x \notin \Delta_{i=1}^{k} E_{i} y x \in E_{k+1}. En el primer caso, aplicando la inducción, x pertenece a una cantidad impar de conjuntos E_{1}, E_{2}, \ldots, E_{k} y, evidentemente, también a una cantidad impar de conjuntos de E_{1}, E_{2}, \ldots, E_{k}, E_{k+1} (pues no pertenece a E_{k+1}) y, en el segundo caso x pertenece a E_{k+1} pero puede pertenecer a una cantidad par de conjuntos E_{i} de E_{1}, E_{2}, \ldots, E_{k}. Si x pertenece sólo a E_{k+1}, entonces es evidente que pertenece a una cantidad impar de conjuntos de E_{1}, E_{2}, \ldots, E_{k}, E_{k+1} y si pertenece además a una cantidad par de conjuntos E_{i} de E_{1}, E_{2}, \ldots, E_{k}, es inmediato que pertenecerá a una cantidad impar de conjuntos E_{i} de E_{1}, E_{2}, \ldots, E_{k}, E_{k+1} (pues añadimos uno más y par más uno es impar). Por tanto,  la diferencia simétrica \Delta_{i=1}^{k+1} E_{i} es el conjunto de los elementos de X que se hallan en un número impar de conjuntos de E_{1}, E_{2}, \ldots, E_{k}, E_{k+1} y esto termina la demostración.

Referencias:

Wikipedia

Mathematics