Introducción

En esta entrada daremos continuación al tema de conjuntos finitos. Probaremos más resultados que se satisfacen para los conjuntos finitos y veremos cuál es la cardinalidad del conjunto potencia de un conjunto finito dado.

Conjuntos finitos y contención

Teorema. Sean $A$ y $B$ conjuntos tales que $B$ es finito. Si $A\subseteq B$, entonces $A$ es finito. Más aún, $|A|\le |B|$.

Demostración. (Por inducción sobre $|B|$).

Base de inducción. Supongamos que $|B|=0$. Entonces $B=\mathrm{\varnothing }$, por lo que $A=\mathrm{\varnothing }$ y así, $A$ es finito y $0=|A|\le |B|=0$.

Hipótesis de inducción. Supongamos que para $|X|=n$ se cumple que si $Y\subseteq X$, entonces $Y$ es finito y $|Y|\le |X|$.

Paso inductivo. Sea $B$ un conjunto finito tal que $|B|=n+1$. Veamos que si $A\subseteq B$, entonces $A$ es finito y $|A|\le |B|$.

Si $A=B$, entonces $A$ es finito y $|A|=|B|\le |B|$.

Si $A\ne B$, existe $x\in B\setminus A$. Luego, $A\subseteq B\setminus \{x\}$ y como $|B\setminus \{x\}|=n$, tenemos por hipótesis de inducción que $A$ es finito y $|A|\le |B\setminus \{x\}|=n\le n+1=|B|$. En cualquier caso, $A$ es finito y $|A|\le |B|$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Cardinalidad del conjunto potencia

Como parte de los ejercicios de la unidad de números naturales, definimos la operación binaria potencia en $\mathbb{N}$, que intuitivamente se realiza como sigue $m^n=\underset{n-veces}{\underbrace{m\cdot m\cdots m}}$.

Teorema. Si $X$ es finito, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$.

Demostración. (Por inducción sobre $|X|$).

Base de inducción. Si $|X|=0$, entonces $X=\mathrm{\varnothing }$ y así, $\mathcal{P}(X)=\{\mathrm{\varnothing }\}$, por lo que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=1=2^0=2^{|X|}$.

Hipótesis de inducción. Supongamos que si $A$ es finito tal que $|A|=n$, entonces $\mathcal{P}(A)$ es finito y $|\mathcal{P}(A)|=2^{|A|}$.

Paso inductivo. Sea $X$ un conjunto finito tal que $|X|=n+1$. Supongamos que $X=\{X_1,X_2,\dots ,X_n,X_{n+1}\}$. Luego, consideremos $X^{\prime }=X\setminus \{X_1\}$, entonces $|X^{\prime }|=n$ y así, $|\mathcal{P}(X^{\prime })|=2^{|X^{\prime }|}$. Veamos que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$. Para ello veamos primero que $\mathcal{P}(X)=\mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}$.

Procederemos por doble contención.

$\subseteq$) Sea $Y\in \mathcal{P}(X)$, entonces $Y\subseteq X$. Si $X_1\in Y$, entonces $Y\in \{Z\in \mathcal{P}(X):X_1\in Z\}$ y por lo tanto, $Y\in \mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}$.

Si $X_1\notin Y$, entonces $Y\subseteq X\setminus \{X_1\}=X^{\prime }$, por lo que $Y\in \mathcal{P}(X^{\prime })$ y por lo tanto, $Y\in \mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}$.

Concluimos que $\mathcal{P}(X)\subseteq \mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}$.

$\supseteq$) Sea $Y\in \mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}$.

Caso 1: Si $Y\in \mathcal{P}(X^{\prime })$, entonces $Y\subseteq X^{\prime }$ y como $X^{\prime }\subseteq X$, entonces $Y\subseteq X$ y así, $Y\in \mathcal{P}(X)$.

Caso 2: Si $Y\in \{Z\in \mathcal{P}(X):X_1\in Z\}$, entonces $Y\in \mathcal{P}(X)$.

Por lo tanto, $\mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}\subseteq \mathcal{P}(X)$.

Así, $\mathcal{P}(X)=\mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X):X_1\in Z\}$.

Luego, por hipótesis de inducción tenemos que $\mathcal{P}(X^{\prime })$ es finito y $|\mathcal{P}(X^{\prime })|=2^n$.

Resulta que $\{Z\in \mathcal{P}(X)\}$ es finito; más aún, afirmamos que $|\{Z\in \mathcal{P}(X):X_1\in Z\}|=|\mathcal{P}(X^{\prime })|$. Para probar este último hecho estableceremos una biyección entre $\mathcal{P}(X^{\prime })$ y $\{Z\in \mathcal{P}(X):X_1\in Z\}$.

Consideremos $f:\mathcal{P}(X^{\prime })\to \{Z\in \mathcal{P}(X):X_1\in Z\}$ dada por $f(Y)=Y\cup \{X_1\}$. Veamos que $f$ es biyectiva.

Inyectividad. Sean $A,B\in \mathcal{P}(X^{\prime })$ tales que $f(A)=f(B)$, esto es $A\cup \{X_1\}=B\cup \{X_1\}$. Luego, $A$ y $\{X_1\}$ son ajenos pues $A\subseteq X^{\prime }=X\setminus \{X_1\}$; asimismo, $B$ y $\{X_1\}$ son ajenos pues $B\subseteq X^{\prime }=X\setminus \{X_1\}$. De este modo, debe ocurrir que $A=B$. Por lo tanto, $f$ es inyectiva.

Suprayectividad. Sea $Y\in \{Z\in \mathcal{P}(X):X_1\in Z\}$. Entonces $Y\subseteq X$ y $X_1\in Y$.

Veamos que existe $W\subseteq X\setminus \{X_1\}$ tal que $f(W)=Y$. Consideremos $W=Y\setminus \{X_1\}$. Tenemos que $f(W)=(Y\setminus \{X_1\})\cup \{X_1\}=Y$. Por lo tanto, $f$ es suprayectiva.

Así, $f$ es biyectiva y $|\{Z\in \mathcal{P}(X):X_1\in Z\}|=2^n$.

Por lo tanto, usando regla de la suma, tenemos que $|\mathcal{P}(X)|=|\mathcal{P}(X^{\prime })\cup \{Z\in \mathcal{P}(X)\}|=2^n+2^n=2(2^n)=2^{n+1}$. Esto concluye nuestra prueba.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

1. Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
2. Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
3. Sean $A$ y $B$ conjuntos finitos. Sea $\mathcal{F}$ el conjunto de todas las posibles funciones de $A$ en $B$. Muestra que $\mathcal{F}$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$?
4. Sean $A$ y $B$ conjuntos finitos. Muestra que $A\times B$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$?
5. Demuestra que para cualquier número natural $n$ se tiene que $n<2^n$.

Más adelante…

En la siguiente entrada abordaremos a los conjuntos infinitos. Esto nos acercará a una discusión importante sobre qué son en realidad los cardinales en teoría de los conuntos.

Entradas relacionadas

• Ir a Teoría de los Conjuntos I
• Entrada anterior: Teoría de los Conjuntos I: Conjuntos finitos
• Siguiente entrada: Teoría de los Conjuntos I: Conjuntos infinitos

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»