Teoría de los Conjuntos I: Conjuntos finitos

Por Gabriela Hernández Aguilar

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

1 comentario en “Teoría de los Conjuntos I: Conjuntos finitos

  1. Rosa Garcia

    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.

    Responder

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.