Introducción
Ahora que sabemos el concepto de equipotencia, en esta sección veremos a los conjuntos finitos, los cuales podremos contar según el número natural al que sean equipotentes. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.
Concepto
Definición: Sea $X$ un conjunto. Decimos que $X$ es un conjunto finito si y sólo si existe $n\in \mathbb{N}$ tal que $X\sim n$.
Ejemplo:
El conjunto $\emptyset$ es finito, pues existe una biyección entre el conjunto $\emptyset$ y $0$; a saber, la función vacía.
$\square$
Ejemplo:
El conjunto $A=\set{2,4,6,8, 10}$ es finito pues $f:A\to 5=\set{0,1,2,3,4}$ definida por medio de $f=\set{(2,0), (4,1), (6,2), (8,3), (10, 4)}$ es una función biyectiva.
$\square$
Es conveniente añadir la siguiente notación para conjuntos finitos, pues hará más fluida la escritura.
Definición: Sea $X$ un conjunto finito y $n\in\mathbb{N}$ tal que $X\sim n$. Definimos el cardinal de $X$ como el número natural al cual $X$ es equipotente, y lo denotaremos por medio del símbolo $|X|$; esto es, $|X|:=n$.
Lema: Si $X$ es finito y $y\notin X$, entonces $X\cup\set{y}$ es finito y $|X\cup \set{y}|= |X|+1$.
Demostración:
Sea $X$ finito tal que $|X|=n$, entonces existe $f:n\to X$ tal que $f$ es biyectiva.
Definimos $f’:s(n)\to X\cup \set{y}$ como
$f'(x)= \left\{ \begin{array}{lcc}
f(x) & si & x \in n \\
\\ y& si & x=n \\
\end{array}
\right.$
Tenemos que $f$ es biyectiva.
En efecto, primero veamos que $f$ es inyectiva. Sean $x_1, x_2\in s(n)$ tales que $f'(x_1)=f'(x_2)$.
Caso 1: Si $x_1\in n$ y $x_2\in n$, entonces $f(x_1)=f'(x_1)=f'(x_2)=f(x_2)$. Como $f$ es inyectiva, entonces $x_1=x_2$.
Caso 2: Si $x_1= n$ y $x_2= n$, entonces $x_1=x_2$.
No ocurre que $x_1\in n$ y $x_2=n$ pues $f'(x_1)=f(x_1)\in X$ y $f'(x_2)=y\notin X$. De manera análoga, no ocurre que $x_1=n$ y $x_2\in n$.
Por lo tanto, $f’$ es inyectiva.
Veamos ahora que $f’$ es sobreyectiva.
Sea $w\in X\cup \set{y}$. Veamos que existe $x\in s(n)$ tal que $f'(x)=w$.
Caso 1: Si $w\in X$, entonces existe $x\in n$ tal que $f(x)=w$, pues $f:n\to X$ es una función sobreyectiva, así que existe $x\in s(n)$ tal que $f'(x)=f(x)=w$.
Caso 2: Si $w=y$, entonces tomamos al elemento $n\in s(n)$ y se tiene que $f'(n)=w$.
De los casos 1 y 2, concluimos que $f’$ es sobreyectiva.
Por lo tanto, $f’$ es biyectiva y así $X\cup\set{y}$ es finito; más aún, $X\cup\set{y}\sim s(n)$, es decir, $|X\cup \set{y}|=s(n)=n+1=|X|+1$.
$\square$
Teorema: Sean $X$ y $Y$ conjuntos finitos, entonces $X\cup Y$ es finito. Más aún, $|X\cup Y|\leq |X|+|Y|$.
Demostración: (Por inducción sobre $|Y|$.
Base de inducción: Si $|Y|=0$, entonces $Y=\emptyset$, así $X\cup Y=X\cup \emptyset=X$ y por lo tanto, $|X\cup Y|=|X|=|X|+0=|X|+|\emptyset|$.
Hipótesis de inducción: Ahora supongamos que si $X$ y $Y$ son finitos tales que $|X|=m$ y $|Y|=n$, entonces $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$.
Paso inductivo: Veamos que si $|Y|=n+1$, entonces $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$. Si para todo $y\in Y$, $y\in X$, entonces $Y\subseteq X$, por lo que $X\cup Y=X$ y, por tanto, $X\cup Y$ es finito; además, como $n\leq n+t$ para cualesquiera naturales $n$ y $t$, entonces $|X\cup Y|=|X|\leq |X|+|Y|$.
Supongamos ahora que existe $y\in Y\setminus X$. Luego, sea $Y’=Y\setminus \set{y}$. Tenemos que $|Y’|=n$ por lo que, por hipótesis de inducción, se tiene que $X\cup Y’$ es finito y $|X\cup Y’|\leq |X|+|Y’|$.
Luego, dado que $y\notin Y’$ y $y\notin X$, entonces, $y\notin X\cup Y’$, y así por el lema anterior, tenemos que $(X\cup Y’)\cup\set{y}$ es finito y
\begin{align*}
|(X\cup Y’)\cup \set{y}|&=|X\cup Y’|+1\\
&\leq |X|+|Y’|+1\\
&=|X|+n+1=|X|+|Y|.
\end{align*}
Por lo tanto, $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$, siempre que $X$ y $Y$ son conjuntos finitos.
$\square$
Teorema: Si $\mathcal{F}$ es finito y para cualquier $X\in \mathcal{F}$, $X$ es finito. Entonces $\bigcup\mathcal{F}$ es finito.
Demostración: (Por inducción sobre la cardinalidad de $\mathcal{F}$).
Base de inducción: Si $|\mathcal{F}|=0$, entonces $\mathcal{F}=\emptyset$. Así, se cumple por vacuidad, que si cualquier $X\in \mathcal{F}$ es finito, entonces $\bigcup \mathcal{F}$ es finito. Más aún, $\bigcup \mathcal{F}=\emptyset$ y $|\bigcup \mathcal{F}|=0$.
Hipótesis de inducción: Supongamos que si $|\mathcal{F}|=n$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, se cumple que $\bigcup\mathcal{F}$ es finito.
Paso inductivo: Veamos que si $|\mathcal{F}|=n+1$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.
Sea $X\in\mathcal{F}$ y definamos $\mathcal{F’}:=\mathcal{F}\setminus X$. Tenemos que cualquier elemento de $\mathcal{F’}$ es finito y que $|\mathcal{F}’|=n$, por lo que por hipótesis de inducción se cumple que $\bigcup\mathcal{F’}$ es finito.
Ahora, por el lema, tenemos que $\bigcup\mathcal{F}’\cup X$ es finito.
Afirmación: $\bigcup\mathcal{F}=\bigcup\mathcal{F}’\cup X$.
Demostración de la afirmación:
Sea $x\in\bigcup \mathcal{F}$, entonces existe $Y\in \mathcal{F}$ tal que $x\in Y$.
Caso 1: Si $Y=X$, entonces $x\in X$ y por lo tanto, $x\in \bigcup\mathcal{F}’\cup X$.
Caso 2: Si $Y\not=X$, entonces $Y\in \mathcal{F}’$ y así, $x\in \bigcup\mathcal{F}’$, lo cual implica que $\bigcup\mathcal{F}\subseteq \bigcup\mathcal{F}’\cup X$.
Ahora, como $\mathcal{F’}\subseteq\mathcal{F}$ y $X\in\mathcal{F}$, entonces $\bigcup\mathcal{F’}\cup X\subseteq\mathcal{F}$.
Así, $\bigcup \mathcal{F}=\bigcup\mathcal{F}’\cup X$. Por lo tanto, $\bigcup\mathcal{F}$ es finito. Lo que concluye nuestra prueba.
$\square$
,
Tarea moral
La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección.
- Sea $X$ un conjunto finito y $x\in X$. Si $|X|=n+1$, demuestra que $X\setminus\set{x}$ es finito y que $|X\setminus\set{x}|=n$.
- Prueba que si $X$ y $Y$ son conjuntos finitos, entonces $X\cap Y$ también es finito.
- Si $A$ y $B$ son conjuntos finitos, prueba que $A\setminus B$ también es finito.
Más adelante…
En la siguiente entrada continuaremos con el contenido de esta sección, probaremos más propiedades sobre los conjuntos finitos y a su vez hablaremos acerca de la cardinalidad del conjunto potencia.
Enlaces
- Entrada anterior: Teoría de los Conjuntos I: Equipotencia
- Siguiente entrada: Teoría de los Conjuntos I: Conjuntos finitos (parte II)
Hola Gabriela.
Me gusta tu trabajo, y quizás pueda serme de utilidad, pero no veo la Bibliografía, o ¿Es de tu propia autoría?
Disculpa, espero tu respuesta.
Gracias de antemano.