Introducción

Ahora que sabemos el concepto de equipotencia, en esta entrada definiremos qué son los conjuntos finitos y hablaremos de ellos. A grandes rasgos, serán aquellos que tengan tantos elementos como alguno de los números naturales que ya definimos. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.

Conjuntos finitos

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$

Principio de las casillas y unicidad de natural equipotente

La definición dice que $X$ es finito cuando hay un natural al que es equipotente pero, ¿este natural es único? La respuesta es que sí. Demostraremos esto a través de algunos resultados auxiliares, que a la vez nos permitirán enunciar y demostrar un par de versiones del principio de las casillas.

Lema (principio de las casillas). No existe ninguna función inyectiva $f:n+1\to n$.

Demostración. Probaremos el resultado por inducción. Para $n=0$ el resultado es cierto pues no existe ninguna función (inyectiva o no) $f:1\to 0$, pues $0=\emptyset$ y $1\neq \emptyset$.

Supongamos que el resultado es cierto para el natural $n$, es decir, que no existe ninguna función inyectiva $f:n+1\to n$. Veremos que no existe ninguna función inyectiva $g:n+2\to n+1$. En busca de una contradicción, supongamos que sí existe tal $g$.

Si $Im(g)\subseteq n$, entonces la restricción de $g$ a $n+1$ es una función inyectiva de $n+1$ en $n$, lo que contradice la hipótesis inductiva. Así, existe un natural $k\leq n+2$ tal que $g(k)=n+1$. Si $k=n+2$, entonces $g\setminus\{(n+2,n+1)\}$ es una función inyectiva de $n+1$ en $n$, que contradice la hipótesis inductiva. Así, $k\leq n+1$. Como $g$ es inyectiva, $g(n+2)=l\neq k$. Pero entonces, $$(g\setminus\{(n+2,l),(k,n+1)\})\cup \{(k,l)\}$$ es una función inyectiva de $n+1$ en $n$, dando una contradicción final a la hipótesis inductiva.

$\square$

Usualmente el principio de las casillas se piensa así: si $f:n+1\to n$ es una función, entonces deben existir $x,y\in n+1$ tales que $f(x)=f(y)$. En términos intuitivos, «si colocamos $n+1$ pelotas en $n$ casillas, entonces por lo menos en alguna casilla quedaron por lo menos dos pelotas». Si son todavía más pelotas, el resultado es cierto, como lo indica el siguiente corolario de manera formal.

Corolario. Sean $m,n$ naturales con $n<m$. Entonces no existen funciones inyectivas $f:m\to n$.

Demostración. Recordemos que si $n<m$, entonces $n\subset m$ y de hecho $n+1\subseteq m$. Si existiera una función inyectiva $f:m\to n$, entonces su restricción a $n+1$ sería una función inyectiva de $n+1$ en $n$, contradiciendo el principio de las casillas.

$\square$

En particular, si $X$ es un conjunto finito, entonces debe haber un único natural $n$ al cual es equipotente. Si hubiera dos distintos $m$ y $n$, sin pérdida de generalidad $n<m$. Tendríamos entonces que $m\sim X$ y $X\sim n$, pero entonces $m\sim n$ y existiría una función biyectiva de $m$ a $n$. En particular, sería una función inyectiva, lo cual contradice el corolario anterior.

Con esto en mente, es conveniente añadir la siguiente notación para conjuntos finitos.

Definición. Sea $X$ un conjunto finito y $n\in\mathbb{N}$ el natural tal que $X\sim n$. Definimos el cardinal de $X$ como $n$ y lo denotaremos por $|X|=n$.

La regla de la suma

La regla de la suma es un resultado muy versátil que nos permite entender exactamente la cardinalidad de la unión de dos conjuntos finitos disjuntos. Además, este resultado motivará posteriormente la definición de suma de cardinales infinitos, cuando hablemos de ellos.

Teorema (regla de la suma). Si $X$ y $Y$ son conjuntos finitos y disjuntos, con $|X|=m$ y $|Y|=n$, entonces $X\cup Y$ es finito y $|X\cup Y|=m+n$.

Demostración. Sean $f:X\to m$ y $g:Y\to n$ biyecciones. Definimos la función $h:X\cup Y \to m+n$ como sigue: $$h(x)= \begin{cases} f(x) & \text{si $x\in X$}\\ m+g(x) & \text{si $x\in Y$.}\end{cases}$$

Como $X$ y $Y$ son disjuntos, $h$ es una función de dominio $X\cup Y$. Como $f(x)\leq m-1 \leq m+n-1$ y $m+g(x)\leq m+ n-1$, entonces la imagen de $h$ está contenida en $m+n$. Afirmamos que $h$ es una biyección de $X\cup Y$ en $m+n$.

Veamos que $h$ es inyectiva. Supongamos que $x,y$ en $X\cup Y$ son tales que $h(x)=h(y)$. Es imposible que $x\in X$ y $y\in Y$ pues en ese caso $h(x)=f(x)\leq m-1$ y $h(y)=m+g(y)\geq m$. Análogamente, $x\in Y$ y $y\in X$ es imposible. Así, o bien ambos $x$ y $y$ están en $X$, o bien ambos están en $Y$. Si están en $X$, tenemos $f(x)=h(x)=h(y)=f(y)$ y como $f$ es inyectiva, obtenemos $x=y$. Si están en $Y$, tenemos $m+g(x)=h(x)=h(y)=m+g(y)$. Por ley de cancelación de la suma, se tiene $g(x)=g(y)$. Y por inyectividad de $g$ se tendría $x=y$.

Ahora, veamos que $h$ es suprayectiva. Tomemos $k\in m+n$. Si $k\leq m-1$, entonces como $f$ es suprayectiva, existe $x\in X$ tal que $f(x)=k$ y entonces $h(x)=f(x)=k$. Si $k\geq m$, entonces existe $l$ tal que $m+l=k$. Dicha $l$ debe cumplir $l\leq n-1$, pues en otro caso $m+n-1\geq k=m+l \geq m+n$, lo cual sería una contradicción. Como $g$ es biyectiva, existe $r$ tal que $g(r)=l$. Y entonces $h(r)=m+g(r)=m+l=k$.

Como $h$ es inyectiva y suprayectiva, obtenemos que es biyectiva, como queríamos.

$\square$

La regla de la suma tiene varios corolarios como consecuencia.

Corolario. Si $X$ es finito y $y\notin X$, entonces $X\cup\set{y}$ es finito y $|X\cup \set{y}|= |X|+1$.

Demostración. Aplicamos la regla de la suma y $|\set{y}|=1$.

$\square$

Corolario (principio de inclusión-exclusión). Sean $X$ y $Y$ conjuntos finitos. Entonces $X\cup Y$ es finito. Más aún, $|X\cup Y| + |X\cap Y| = |X| + |Y|$.

Demostración. Se tiene que $X=(X\cap Y) \cup (X\setminus Y)$ y que $(X\cap Y) \cap (X\setminus Y)=\emptyset$ (verifica ambas cosas). Así, por regla de la suma se tiene que $$|X|=|X\cap Y| + |X\setminus Y|.$$

De manera similar, se tiene que $X\cup Y = Y \cup (X\setminus Y)$ con $Y\cap (X\setminus Y)=\emptyset$ (verifíca ambas cosas). Así, por la regla de la suma se tiene que $$|Y| + |X\setminus Y| = |X\cup Y|.$$

Sumando las dos igualdades que obtuvimos, tenemos que $$|X|+|Y|+|X\setminus Y| = |X\cap Y| + |X\cup Y| + |X\setminus Y|.$$

Aplicando la ley de cancelación para eliminar $|X\setminus Y|$, obtenemos el resultado deseado.

$\square$

Corolario. 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 el principio de inclusión-exclusión, $$|X\cup Y| \leq |X\cup Y| + |X\cap Y| = |X| + |Y|.$$

$\square$

La regla de la suma por sí misma es muy versátil y tiene una versión más general.

Teorema (regla de la suma generalizada). Sea $n$ un natural y sean $A_1,\ldots,A_n$ conjuntos finitos y tales que $A_j\cap A_i=\emptyset$ para cualesquiera $i,j$ en $\{1,\ldots,n\}$. Entonces $A:=\bigcup \{A_i: i\in \{1,\ldots,n\}\}$ es finito.

En los ejercicios tendrás que probar esta versión.

Un último resultado que demostraremos es el siguiente.

Teorema. Si $\mathcal{F}$ es finito y para cualquier $X\in \mathcal{F}$ pasa que $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{G}|=n$ y para cualquier $X\in \mathcal{G}$, $X$ es finito, se cumple que $\bigcup\mathcal{G}$ 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.

Como $|\mathcal{F}|$ es distinto de $0$, tomeos $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 corolario del principio de inclusión-exclusión, 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}’$.

Los casos anteriores muestran 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\bigcup\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.

1. 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$.
2. Sea $X$ es un conjunto finito. Prueba que si $A\subseteq X$, entonces, $A$ es un conjunto finito.
3. Demuestra por inducción la regla de la suma generalizada. Como sugerencia, uno de los pasos intermedios es que enuncies formalmente y demustres que para todo natural $n$ se cumple que $(A_1\cup \ldots \cup A_n) \cap B = (A_1 \cap B) \cup \ldots \cup (A_n \cap B)$.

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.

Entradas relacionadas

• Ir a Teoría de los Conjuntos I
• Entrada anterior: Teoría de los Conjuntos I: Teorema de Cantor-Schröder-Bernstein 
• Siguiente entrada: Teoría de los Conjuntos I: Conjuntos finitos (parte II)

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»