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|\leq |B|$.
Demostración. (Por inducción sobre $|B|$).
Base de inducción. Supongamos que $|B|=0$. Entonces $B=\emptyset$, por lo que $A=\emptyset$ y así, $A$ es finito y $0=|A|\leq |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|\leq |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|\leq |B|$.
Si $A=B$, entonces $A$ es finito y $|A|=|B|\leq|B|$.
Si $A\not=B$, existe $x\in B\setminus A$. Luego, $A\subseteq B\setminus\set{x}$ y como $|B\setminus \set{x}|=n$, tenemos por hipótesis de inducción que $A$ es finito y $|A|\leq |B\setminus \set{x}|=n\leq n+1 =|B|$. En cualquier caso, $A$ es finito y $|A|\leq |B|$.
$\square$
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}=\underbrace{m\cdot m\cdots m}_{n-veces}$.
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=\emptyset$ y así, $\mathcal{P}(X)=\set{\emptyset}$, 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=\set{X_1,X_2, \dots, X_n, X_{n+1}}$. Luego, consideremos $X’=X\setminus \set{X_1}$, entonces $|X’|=n$ y así, $|\mathcal{P}(X’)|=2^{|X’|}$. Veamos que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$. Para ello veamos primero que $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{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 \set{Z\in \mathcal{P}(X): X_1\in Z}$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.
Si $X_1\notin Y$, entonces $Y\subseteq X\setminus \set{X_1}=X’$, por lo que $Y\in \mathcal{P}(X’)$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.
Concluimos que $\mathcal{P}(X)\subseteq \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.
$\supseteq$) Sea $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.
Caso 1: Si $Y\in \mathcal{P}(X’)$, entonces $Y\subseteq X’$ y como $X’\subseteq X$, entonces $Y\subseteq X$ y así, $Y\in \mathcal{P}(X)$.
Caso 2: Si $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$, entonces $Y\in \mathcal{P}(X)$.
Por lo tanto, $\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}\subseteq \mathcal{P}(X)$.
Así, $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.
Luego, por hipótesis de inducción tenemos que $\mathcal{P}(X’)$ es finito y $|\mathcal{P}(X’)|=2^n$.
Resulta que $\set{Z\in \mathcal{P}(X)}$ es finito; más aún, afirmamos que $|\set{Z\in \mathcal{P}(X):X_1\in Z}|=|\mathcal{P}(X’)|$. Para probar este último hecho estableceremos una biyección entre $\mathcal{P}(X’)$ y $\set{Z\in \mathcal{P}(X):X_1\in Z}$.
Consideremos $f:\mathcal{P}(X’)\to \set{Z\in \mathcal{P}(X):X_1\in Z}$ dada por $f(Y)=Y\cup \set{X_1}$. Veamos que $f$ es biyectiva.
Inyectividad. Sean $A,B\in \mathcal{P}(X’)$ tales que $f(A)=f(B)$, esto es $A\cup \set{X_1}=B\cup \set{X_1}$. Luego, $A$ y $\set{X_1}$ son ajenos pues $A\subseteq X’=X\setminus \set{X_1}$; asimismo, $B$ y $\set{X_1}$ son ajenos pues $B\subseteq X’=X\setminus \set{X_1}$. De este modo, debe ocurrir que $A=B$. Por lo tanto, $f$ es inyectiva.
Suprayectividad. Sea $Y\in \set{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 \set{X_1}$ tal que $f(W)=Y$. Consideremos $W=Y\setminus \set{X_1}$. Tenemos que $f(W)=(Y\setminus \set{X_1})\cup \set{X_1}=Y$. Por lo tanto, $f$ es suprayectiva.
Así, $f$ es biyectiva y $|\set{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’)\cup \set{Z\in \mathcal{P}(X)}|= 2^n+2^n=2(2^n)= 2^{n+1}$. Esto concluye nuestra prueba.
$\square$
Tarea moral
La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.
- Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
- Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
- 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$?
- 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$?
- 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: Conjuntos finitos
- Siguiente entrada: 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»