Introducción

En la entrada pasada, demostramos que todo número natural es el conjunto formado por los elementos $\{0,1,\dots ,n-1\}$. Esto nos dice intuitivamente que cada número natural $n$, tiene exactamente $n$ elementos. Pero, de modo formal, ¿qué quiere decir que un conjunto tenga $n$ elementos? Esto lo precisaremos en esta entrada. Más aun, siguiendo esta idea, definiremos que quiere decir que un conjunto sea infinito. Después, veremos las propiedades que los conjuntos finitos e infinitos tienen.

El tamaño de los conjuntos

A la hora de pensar en determinar el tamaño de un conjunto, uno podría aventurarse y empezar a contar los elementos de este uno por uno. Esta forma de aproximar el problema no sólo parece muy laboriosa, sino que también presenta el problema de que no todos los conjuntos tienen la propiedad de que se pueda enlistar a sus elementos (aunque no lo definimos aún, seguramente has escuchado que el conjunto $\mathbb{R}$ de números reales no cumple esta propiedad).

De entrada, parecería que el problema de catalogar a los conjuntos por su tamaño es más complicado de lo que parece. Sin embargo, hay una idea famosa que viene a salvar la situación.

Imagina que eres el acomodador de una sala de cine con una cantidad desconocida de asientos (incluso posiblemente infinita) y que quieres sentar en ellos a un cierto conjunto de espectadores (cuya cantidad también se desconoce). Como dijimos anteriormente, la labor de contar todos los asientos de la sala podría ser demasiado complicada. ¿Cómo podríamos cerciorarnos de que cada espectador podrá tener un asiento?

La respuesta es inusualmente sencilla. La mejor forma de cerciorarse de que todos puedan sentarse, es pidiéndoles que se sienten. Si logran hacerlo de modo que a cada asistente le toque exactamente un asiento y no sobren asientos, podremos decir que hay el mismo número de personas que de lugares.

Notemos que de esta forma no necesitamos saber de forma explícita cuántas sillas hay, ni cuantas personas asistieron a la función, para saber que hay la misma cantidad de personas que de sillas. Formalmente hablando, hemos dado una relación entre el conjunto de personas y el de asientos.

Recordemos que a una relación entre conjuntos se le llama función si a cada elemento de nuestro dominio le corresponde uno y solo un elemento del codominio. Más aún, si a todo elemento del codominio, está relacionado con uno del dominio, la función se llamará suprayectiva. Si una función satisface que los elementos del codominio se relacionan con a lo más un elemento del dominio, se le llama función inyectiva. Cuando ambas condiciones se satisfacen, diremos que la función es biyectiva.

Nota que en el ejemplo de la sala de cine, si logramos hacer que todos los asistentes se sienten sin que sobre alguna silla, entonces la función que damos es una función biyectiva. Con estas observaciones, introducimos la siguiente definición.

Definición. Diremos que dos conjuntos $A$ y $B$ tienen la misma cantidad de elementos, o la misma cardinalidad, si existe una función biyectiva entre ellos. En este caso escribimos $|A|=|B|$.

El tamaño del conjunto $\mathbb{N}$

Aunque los conjuntos finitos parecen ser más cercanos a nuestra realidad, será más interesante definir primero qué son los conjuntos infinitos. Para ello usaremos una de las propiedades «raras» que estos tienen.

Definición. Diremos que un conjunto $X$ es infinito si existe un subconjunto propio $Y$ de $X$ y una función $f:X\to Y$ biyectiva entre ambos conjuntos.

Recuerda que un subconjunto propio es cualquier subconjunto que no sea el conjunto original. En otras palabras, un conjunto es infinito si tiene el mismo tamaño que alguno de sus subconjuntos propios.

Definición. Diremos que un conjunto es finito si no es infinito.

La propiedad que usamos para caracterizar a los conjuntos infinitos fue muy novedosa cuando se enunció por primera vez. Incluso con los años fue el origen de aparentes paradojas al sentido común. Si el tema te parece interesante, puedes leer o ver algún vídeo sobre el famoso Hotel de Hilbert.

Con nuestra definición lista, empezaremos a catalogar los conjuntos que ya conocemos en finitos e infinitos.

Teorema. El conjunto $\mathbb{N}$ de números naturales es infinito.

Demostración. Para demostrar esto, consideraremos el conjunto $\mathbb{N}\setminus \{0\}$. Este es un subconjunto propio de $\mathbb{N}$. Tomemos la función $\sigma :\mathbb{N}\to \mathbb{N}\setminus \{0\}$. De acuerdo con la definición de conjunto infinito hay que demostrar que $\sigma$ es biyectiva, es decir, que es inyectiva y suprayectiva.

El hecho de que el codominio esté bien definido y que $\sigma$ sea inyectiva, fue demostrado en la entrada La construcción de los naturales, a la hora de probar los axiomas de Peano. La prueba de la suprayectividad se dejó como un ejercicio moral en la entrada de Principio de inducción y teoremas de recursión, ya que se usó para la prueba del teorema de Recursión débil. De cualquier forma, a continuación damos esa prueba.

Demostraremos que $\{0\}\cup \sigma (\mathbb{N})$ es inductivo. Evidentemente $0\in \mathbb{N}$ , y si $n\in \{0\}\cup \sigma (\mathbb{N})$, entonces es trivial que $\sigma (n)\in \sigma (\mathbb{N})$. Entonces $\{0\}\cup \sigma (\mathbb{N})=\mathbb{N}$, por lo que $\sigma (n)$ sí es suprayectiva y por lo tanto biyectiva. Con esto se concluye la prueba.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

La idea de determinar si dos conjuntos tienen la misma cantidad de elementos usando funciones se puede extender un poco más. La usaremos a continuación para definir cuándo un conjunto tiene al menos tantos elementos como otro.

Definición. Decimos que un conjunto $A$ tiene a lo más tantos elementos como un conjunto $B$ si existe una función inyectiva $f:A\to B$. En este caso, escribimos $|A|\le |B|$.

Todo número natural es finito

Como hemos visto, los conjuntos infinitos se comportan de forma inesperada. Sin embargo los conjuntos finitos sí se comportarán de una forma más intuitiva. El teorema siguiente ejemplifica esto.

Teorema. Si $A$ es un conjunto finito, y $f:A\to A$, entonces son equivalentes las siguientes tres afirmaciones:

1. $f$ es biyectiva
2. $f$ es inyectiva
3. $f$ es suprayectiva

Demostración. Evidentemente, $1)\Rightarrow 2)$ y $1)\Rightarrow 3)$. Si logramos demostrar la equivalencia entre $2)$ y $3)$ terminaremos, pues al tener uno, tendríamos el otro y por lo tanto tendríamos ambas partes de la definición de biyectividad.

$2)\Rightarrow 3)$ Supongamos que $f$ es inyectiva y supongamos que $f$ no es suprayectiva. Entonces $f:A\to f(A)$ es una biyección de $A$ con un subconjunto propio, lo cual diría que $A$ es infinito. Esto es una contradicción, así que $f$ debe ser suprayectiva.

$3)\Rightarrow 2)$ Si $f$ es suprayectiva, entonces tiene inversa derecha, es decir, existe $g:A\to A$ tal que $f\circ g=I{d}_A$. A partir de esta igualdad se puede probar que $g$ es inyectiva. En efecto, si $g(a)=g(b)$, entonces $f(g(a))=f(g(b))$, pero entonces $a=b$. Por la implicación del párrafo anterior, $g$, también es suprayectiva. Pero con esto se puede mostrar que $f$ es inyectiva. Si tenemos $a$ y $b$ tales que $f(a)=f(b)$, tomemos $c$ y $d$ tales que $g(c)=a$ y $g(d)=b$. De aquí, $c=f(g(c))=f(g(d))=d$ y por lo tanto $a=g(c)=g(d)=b$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Sigamos estudiando propiedades de los conjuntos infinitos. El siguiente resultado es bastante intuitivo: si le quitamos un elemento a un conjunto infinito, sigue siendo infinito. La demostración es algo elaborada pues debemos hacerla a partir de nuestras definiciones.

Lema 1. Si $X$ es un conjunto infinito y $x\in X$, entonces $X\setminus \{x\}$ también es un conjunto infinito.

Demostración. Sea $f:X\to A$ una biyección de $X$ a un subconjunto propio $A$. Tenemos que considerar dos casos: que $x\notin A$ o que $x\in A$. Comencemos con el caso $x\notin A$.

Para mostrar que $X\setminus \{x\}$ es infinito, utilizaremos como subconjunto a $A\setminus \{f(x)\}$ y como función a la restricción de $f$ a $X\setminus \{x\}$. Debemos demostrar que $A\setminus \{f(x)\}$ es un subconjunto propio de $X\setminus \{x\}$ y que dicha restricción es una biyección.

Lo primero sucede ya que $$A\setminus \{f(x)\}⊊A\subseteq X\setminus \{x\}.$$ El hecho de que $f:X\setminus \{x\}\to A\setminus \{f(x)\}$ sea una biyección es consecuencia directa de que originalmente $f:X\to A$ era una biyección. Los detalles quedan como tarea moral.

Si por el contrario $x\in A$, como $A⊊X$ debe existir $x^{\prime }\in X\setminus A$. Consideremos la función

$$\begin{array}{rlrlrlrlr}& g:& & X& & ⟶& (A\cup \{x^{\prime }& \})\setminus \{x\}& \\ & & & y& & \mapsto & f(& y)& \text{ si }y\ne f^{-1}(x)\\ & & f^{-1}& (x)& & \mapsto & & x^{\prime }& \end{array}$$

Veamos que $g$ es una biyección entre $X$ y $(A\cup \{x^{\prime }\})\setminus \{x\}$. Lo primero que notamos es que el codominio está bien definido ya que para todo $y\in X$ se tiene que $g(y)\ne x$ (¿por qué?).

Además es inyectiva, ya que si $g(y)=g(z)$, con $y\ne f^{-1}(x)\ne z$, entonces se tiene que $f(y)=g(y)=g(z)=f(z)$, y por la inyectividad de $f$ se tiene que $y=z$. Mientras que si $y=f^{-1}(x)$, tenemos que $g(y)=x^{\prime }=g(z)$ si $z\ne f^{-1}(x)$, tendríamos que $x^{\prime }=f(z)$, por lo que $x^{\prime }\in A$ lo cual es absurdo, entonces $z=f^{-1}(x)=y$, así $g$ es efectivamente inyectiva.

Para probar que es suprayectiva, consideremos $z\in (A\cup \{x^{\prime }\})\setminus \{x\}$. Si $z=x^{\prime }$, entonces $g(f^{-1}(x))=x^{\prime }$, mientras que si $z\in A\setminus \{x\}$, por la suprayectvidad de $f$, debe de existir $y$ tal que $f(y)=z$. Además $y\ne f^{-1}(x)$ ya que si lo fuera $f(f^{-1}(x))=x=z$, lo cual sería absurdo. Se tiene entonces que $g(y)=f(y)=z$.

Con esto probamos que $g$ es una biyección de $X$ a un subconjunto propio al que no pertenece $x$. Para concluir, aplicamos el primer caso.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Usando el lema anterior es fácil dar un corolario importante sobre conjuntos finitos, cuya prueba queda como un ejercicio.

Corolario. Si $X$ es un conjunto finito, y $x$ es un conjunto arbitrario, entonces $X\cup \{x\}$ es también un conjunto finito.

Armados con este corolario, podemos dar uno de los teoremas importantes de esta entrada.

Teorema. Si $n$ es un natural, entonces $n$ es un conjunto finito.

Demostración. Procedamos por inducción. Si $n=0$, entonces $n=\mathrm{\varnothing }$, entonces $n$ no tiene subconjuntos propios con los que pueda biyectarse, ya que no tiene subconjuntos propios. Entonces por vacuidad el vacío es finito.

Supongamos que $n$ es un natural finito. Debemos demostrar que $\sigma (n)$ es también finito. Pero como $\sigma (n)=n\cup \{n\}$, el paso inductivo es consecuencia del corolario anterior. Con esto concluimos la inducción.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Caracterizando los conjuntos finito e infinitos

Ya probamos que cada número natural es finito y que el conjunto de todos los naturales es infinito. Lo siguiente que haremos es ver que estos conjuntos nos sirven para catalogar a todos los demás conjuntos en finitos o infinitos. Comenzamos con un lema bastante intuitivo: si con conjunto tiene un subconjunto infinito, entonces es infinito.

Lema 2. Si $X$ es infinito y $X\subset Y$ entonces $Y$ también es infinito.

Demostración. Como $X$ es infinito, existe una biyección $f$ entre $X$ y uno de sus subconjuntos propios $A$. Consideremos entonces $(Y\setminus X)\cup A⊊Y$, y demos una biyección entre $Y$ y este conjunto dada por

$$\begin{array}{rlrlrlrlr}& g:& & Y& & ⟶& (Y\setminus & X)\cup A& \\ & & & y& & \mapsto & & y& \text{ si }y\notin Y\setminus X\\ & & & x& & \mapsto & f(& x)& \text{ si }x\in X\end{array}$$

Probaremos que esta función es una biyección. Primero, veamos que es inyectiva. Esto se debe a que si $g(x)=g(y)$ y $x\in X$, entonces $g(y)=g(x)=f(x)\in A\subset X$, entonces $g(y)$ está en $X$, y como $Y\setminus X$ es enviado en si mismo, debe pasar que $y$ también está en $X$, por lo que $f(y)=g(y)=f(x)$ y por la inyectividad de $f$, tenemos que $y=x$. Por el contrario, si $x\notin X$, se tiene que $g(x)=x=g(y)$ entonces $g(y)\notin X$, por lo que $y$ tampoco puede estar en $X$, así, $g(y)=y=x$.

Veamos ahora que la función es suprayectiva. Si $z\in (Y\setminus X)\cup A$, consideremos dos casos: $z\in Y\setminus X$ en cuyo caso $g(z)=z$, o $z\in A$, por lo que por la suprayectividad de $f$, debemos tener que existe $x\in X$ tal que $z=f(x)=g(x)$. Así, $g$ es suprayectiva y por lo tanto es una biyección..

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Ahora sí, pasamos a demostrar los teoremas con los que concluiremos la entrada.

Teorema. El conjunto de números naturales es el conjunto infinito más pequeño, es decir, que si $X$ es un conjunto infinito, entonces $|\mathbb{N}|\le |X|$.

Demostración. Como $X$ es infinito, debe ser distinto del vacío. Así, existe $x_0\in X$. Consideremos el conjunto $X\setminus \{x_0\}$, por el lema 1 que demostramos, este es de nuevo infinito. Una vez más, no es vacío, entonces existe $x_1\in X\setminus \{x_0\}$, y el conjunto $X\setminus \{x_0,x_1\}=(X\setminus \{x_0\})\setminus \{x_1\}$ será de nuevo infinito. Procediendo de manera recursiva, podemos dar una función

$$\begin{array}{rl}h:& \mathbb{N}\to X\\ & n\mapsto x_n\end{array}$$

tal que todos los $x_n$ son distintos entre sí (esto se puede demostrar inductivamente). Pero entonces $h$ es una función inyectiva de $\mathbb{N}$ al conjunto $X$, que es precisamente nuestra definición de que $|\mathbb{N}|\le |X|$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

El regreso del teorema anterior es evidentemente cierto, es decir que si un conjunto $X$ cumple que $|\mathbb{N}|\le |X|$, entonces $X$ es infinito. Queda como ejercicio demostrarlo.

Para finalizar la entrada, damos un resultado análogo al anterior, para conjuntos finitos.

Teorema. Si $X$ es un conjunto finito, entonces existe $n\in \mathbb{N}$ tal que $|X|=|n|$.

Demostración. Si $X=\mathrm{\varnothing }$, entonces $|\mathrm{\varnothing }|=|X|$. Si $X$ no es vacío, entonces existe $x_0\in X$. Consideremos entonces $X\setminus \{x_0\}$. Si este conjunto es vacío, significa que $X=\{x_0\}$ y claramente podríamos biyectarlo con el conjunto $\sigma (0)=\{0\}$. Si por el contrario, $X\setminus \{x_0\}\ne \mathrm{\varnothing }$, podemos elegir $x_1\in X\setminus \{x_0\}$ y verificar la misma condición.

Necesariamente debemos de terminar en algún momento pues, de otro modo, podremos usar el teorema de recursión para construir una función inyectiva de $\mathbb{N}$ a $X$. Esto diría que $X$ sería infinito, lo cual sería absurdo.

Entonces debe ocurrir que existe una $n$ tal que $X\setminus \{x_0,x_1,\dots ,x_n\}$ es vacío, por lo que $X=\{x_0,x_1,\dots ,x_n\}$, y por lo tanto podemos biyectarlo con $\sigma (n)$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

Más adelante…

Así como los conjuntos transitivos, la teoría que se desarrolla al estudiar las cardinalidades de los conjuntos es un área de estudio importante en la teoría de conjuntos. Aunque no lo veremos a profundidad, la teoría que acabamos de desarrollar es suficiente para comparar la cardinalidad de la mayoría de los conjuntos que veamos con total precisión. Esto será cierto para, conjuntos como $\mathbb{Z}$ (el de los números enteros) o $\mathbb{Q}$ (el de los números racionales). No será sino hasta que definamos el conjunto de números reales que tendremos un conjunto con una cardinalidad estrictamente mayor que la de $\mathbb{N}$.

En la siguiente entrada definiremos el orden de los naturales, para lo cual de nuevo pensaremos a los números naturales como conjuntos. Más aún, las propiedades que estudiamos en la entrada pasada, serán de suma importancia a la hora de definir el buen orden de un conjunto. Esta es una propiedad que usamos anteriormente sin prueba, cuando demostramos el teorema de Recursión.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

1. Supón que diriges un hotel con tantas habitaciones como números naturales. Supón que todas tus habitaciones se encuentran ocupadas, y de repente llega una persona solicitando un cuarto. ¿Cómo puedes hospedarlo sin desalojar a ningún cliente? Supón ahora que después llega un camión con tantas personas como números naturales, todas buscando un cuarto. ¿De qué forma puedes acomodarlos a ellos y a todos los clientes ya hospedados?
2. Completa los detalles de la prueba del lema 1.
3. Demuestra el corolario de la entrada: Si $X$ es un conjunto finito, y $x$ es un conjunto arbitrario, entonces $X\cup \{x\}$ es también un conjunto finito.
4. Demuestra que si $X$ es tal que $|\mathbb{N}|\le |X|$, entonces $X$ es infinito.
5. Demuestra por inducción que si $X$ es infinito y $A$ es un subconjunto con $k$ elementos, entonces $X\setminus A$ es infinito. Si $A$ tiene tantos elementos como naturales, ¿el resultado sigue siendo cierto?

Entradas relacionadas

• Ir a Álgebra Superior II
• Entrada anterior del curso: Conjuntos transitivos
• Siguiente entrada el curso: La relación de orden en los naturales

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»