Teoría de los Conjuntos I: Conjuntos finitos (parte II)

Por Gabriela Hernández Aguilar

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 $|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|$.

Si $A=B$, entonces $A$ es finito y $|A|=|B|\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\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 $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, 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.

  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

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»

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.