Archivo de la categoría: Conjuntos

Sobre cardinalidades

de

Consideremos un conjunto no vacío X y el conjunto de las partes de X (o dicho de otra forma, el conjunto de subconjuntos de X), denotado por \mathcal{P}(X). Entonces X y \mathcal{P}(X) tienen cardinalidades distintas.

 

Recordemos que cuando los conjuntos son infinitos, decimos que dos conjuntos A,B tienen la misma cardinalidad si existe una biyección entre ellos; i.e. si existe \phi:A\rightarrow B biyectiva.

Supongamos entonces que X y \mathcal{P}(X) tienen la misma cardinalidad y denotemos \phi su biyección.

Definimos entonces el siguiente conjunto

E:=\{x\in X\textmd{ }|\textmd{ }x\not\in\phi(x)\}

Esta definición tiene sentido por lo siguiente: \phi(x) denota un subconjunto de X por lo que es natural preguntarse si x está o no en su imagen.


Observación: E\neq\emptyset pues en particular \emptyset\in\mathcal{P}(X) por lo que (por definición de biyección) debe existir algún elemento y\in X tal que \phi(y)=\emptyset, de donde se concluye que y\not\in\phi(y) y luego y\in E

Como E\subset X, y nuevamente por definición de biyección, se tiene que debe existir z\in X tal que \phi(z)=E. Entonces, ¿z está o no en E? si lo estuviera quiere decir (por definición de E) que z\not\in\phi(z)=E, lo cual sería absurdo. Si no lo estuviera entonces nuevamente por definición del conjunto z\in\phi(z)=E lo cual es también un absurdo. Hemos llegado entonces a una contradicción lógica, no puede existir ningún elemento en X que tenga por imagen E y por lo tanto no puede existir una biyección.

 

Una aplicación directa de este resultado es el hecho de que los naturales no se encuentran en biyección con las sucesiones a valores en \{0,1\}. Dicho mas precisamente \mathbb{N} y \{0,1\}^{\mathbb{N}} no tienen la misma cardinalidad. De hecho mostraremos algo más concreto: \mathcal{P}(\mathbb{N}) y \{0,1\}^{\mathbb{N}} tienen la misma cardinalidad (y por lo que mostramos anteriormente esto demuestra lo que queremos).

Definimos \phi:\mathcal{P}(\mathbb{N})\rightarrow\{0,1\}^{\mathbb{N}} como sigue: si E\in\mathcal{P}(\mathbb{N}) es decir E\subset X, escribimos \phi(E)=\{x_{i}\}_{i\in\mathbb{N}}, donde x_{i}=1 si i\in E y x_{i}=0 si i\not\in E.

Es claro por la definición que \phi es efectivamente una función, y además es biyectiva pues si \phi(E)=\phi(F) para E,F\subset X, entonces (para \phi(E)=\{x_{i}\}_{i\in\mathbb{N}} y \phi(F)=\{y_{j}\}_{j\in\mathbb{N}}) se tiene x_{i}=y_{i} para todo i\in\mathbb{N}, de donde i\in E\Leftrightarrow i\in F, lo que concluye que E=F. Finalmente una sucesión \{x_{i}\}_{i\in\mathbb{N}} define al conjunto A=\{i\in\mathbb{N}:x_{i}=1\} y por definicion \{x_{i}\}_{i\in\mathbb{N}}=\phi(A) (la construcción de A nos entrega realmente la inversa de \phi).


Observación: Muchas veces en los textos se denota la cardinalidad de \mathcal{P}(\mathbb{N}) como 2^{\mathbb{N}}. Tiene bastante sentido si lo pensamos por el hecho de que \{0,1\} tiene dos elementos.

 

Como ultima observación, uno puede definir una función inyectiva X\rightarrow\mathcal{P}(\mathbb{X}) que asocia a cada elemento x\in X al conjunto singleton \{x\}\subset X. No deben confundir, x es solo un elemento del conjunto X y su singleton es el conjunto que contiene a un solo elemento de X, solo contiene a x. Esto nos dice que la cardinalidad de X es estrictamente menor que la cardinalidad de  \mathcal{P}(\mathbb{X}).