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 dada un conjunto finito.
Propiedades de los conjuntos finitos
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 $|B|=n$ se cumple que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.
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|$.
Sea $A\subseteq B$ arbritario.
Si $A=B$, entonces $A$ es finito y $|A|\leq |B|$.
Si $A\not=B$, entonces 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$. Luego entonces, $A$ es finito y $|A|\leq |B|$.
$\square$
Cardinalidad del conjunto potencia
Teorema: Si $X$ es finito, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$.
Nota: $2^{n}=\underbrace{2\cdot 2\cdots 2}_{n-veces}$
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)|=2^{|X|}=2^0=1$.
Hipótesis de inducción: Supongamos que si $X$ es finito tal que $|X|=n$, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|= 2^{|X|}$.
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$.
Además, $\set{Z\in \mathcal{P}(X)}$ es finito, más aún, $|\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.
Sobreyectividad: 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 sobreyectiva.
Así, $f$ es biyectiva y $|\set{Z\in \mathcal{P}(X): X_1\in Z}|=2^n$.
Por lo tanto, $|\mathcal{P}(X)|=|\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X)}|= 2^n+2^n=2(2^n)= 2^{n+1}$. Lo que concluye nuestra prueba.
$\square$
Tarea moral
La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:
- Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
- Si $A$ y $B$ son conjuntos finitos y ajenos, muestra que $A\cup B$ es finito y $|A\cup B|=|A|+|B|$.
- Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
- Demuestra que si $A$ y $B$ son cualesquiera conjuntos finitos, entonces $|A\cup B|+|A\cap B|=|A|+|B|$.
Más adelante
En la siguiente sección abordaremos a los conjuntos infinitos, esto nos acercara a preguntarnos sobre la cardinalidad de dichos conjuntos.
Enlaces
Entrada anterior: Teoría de los Conjuntos I: Conjuntos finitos
Siguiente entrada: Conjuntos infinitos