Cardinalidad, conjuntos finitos e infinitos

Ya hemos dicho que una función inyectiva hace que el dominio sea chico respecto al codominio. También mencionamos que una función suprayectiva hace que el codominio sea chico respecto al dominio. Así, una función biyectiva debería igualar los tamaños.

Recordemos que \(f\colon A\to B\) es biyectiva si y sólo si para cualquier \(b\in B\) existe un único \(a\in A\) tal que \(f(a)=b\). Esta equivalencia nos dice que \(A\) y \(B\) tienen el mismo tamaño.

Cardinalidad

La forma en la que hablaremos de tamaños de conjuntos será de manera indirecta, es decir, no definiremos qué es el cardinal asociado a un conjunto, ya que esta discusión se sale del objetivo de este curso. Sin embargo, sí podemos hablar de cómo se relaciona el tamaño de un conjunto respecto de otro mediante funciones.

Definición

Sean \(A\) y \(B\) conjuntos. Definimos las siguientes relaciones:

1. \(\lvert A\rvert\leq \lvert B\rvert\) si existe una función inyectiva \(f\colon A\to B\).
2. \(\lvert A\rvert = \lvert B\rvert\) si existe una función biyectiva \(f\colon A\to B\).

La notación \(\lvert A\rvert\) se lee “el cardinal de \(A\)” y se refiere al tamaño de \(A\). En la definición anterior se escribieron las relaciones enfatizando que el cardinal es la cantidad de elementos y “se puede tratar” como si fuera un número. También es posible escribir estas definiciones sin hacer referencia a la cantidad de elementos.

Definición

Sean \(A\) y \(B\) conjuntos. Definimos las siguientes relaciones:

1. \(A\preceq B\) si existe una función inyectiva \(f\colon A\to B\).
2. \(A\sim B\) si existe una función biyectiva \(f\colon A\to B\).

La notación de las relaciones entre los tamaños de \(A\) y \(B\) sugiere un resultado que no demostraremos.

Teorema (Cantor-Schröder-Bernstein)

Sean \(A\) y \(B\) conjuntos. Si \(A\preceq B\) y \(B\preceq A\) entonces \(A\sim B\).

Si tenemos que \(A\subseteq B\), entonces podemos considerar la función inclusión \(i\colon A\to B\) dada por \(i(a)=a\). Esta función es inyectiva, por lo que \(A\preceq B\). Esta observación nos da muchos ejemplos de relación entre cardinales, en particular,

\[\mathbb{N} \preceq \mathbb{Z} \preceq \mathbb{Q} \preceq \mathbb{R}.\]

Si recordamos lo que sabemos de funciones inyectivas, entonces podemos obtener algunos resultados de manera inmediata.

Proposición

La relación \(\preceq\) es reflexiva y transitiva.

Demostración

Como la función identidad es inyectiva, entonces la relación \(\preceq\) es reflexiva. Como la composición de funciones inyectivas es inyectiva, entonces la relación \(\preceq\) es transitiva.

Notemos que el teorema de Cantor-Schröder-Bernstein dice que \(\preceq\) es antisimétrica. Con esto tenemos que \(\preceq\) es un orden parcial sobre conjuntos.

Dejaremos algunas preguntas para reflexionar acerca de esta relación. ¿El orden definido por \(\preceq\) es un orden total? ¿El orden tiene un mínimo? ¿Es un orden bien ordenado?

La relación \(\sim\) es más restictiva que \(\preceq\), por lo que cumplirá cosas que \(\preceq\) no.

Proposición

La relación \(\sim\) es de equivalencia.

Demostración

La función identidad es biyectiva, por lo que la relación \(\sim\) es reflexiva. Si \(f\colon A\to B\) es biyectiva, entonces \(f^{-1}\colon B\to A\) es biyectiva, por lo que la relación \(\sim\) es simétrica. Si \(f\colon A\to B\) y \(g\colon B\to C\) son biyectivas, entonces \(g\circ f\colon A\to C\) es biyectiva, por lo que la relación \(\sim\) es transitiva.

Con esto podemos hacer una partición de los conjuntos en clases de equivalencia. En este caso, las clases de equivalencia son los conjuntos que tienen el mismo tamaño.

Si podemos tomar representantes de cada clase de equivalencia, entonces podemos obtener una definición de número. Por ejemplo, el número \(3\) es el conjunto que representa a los conjuntos de tamaño \(3\). Esto es, el \(3\) se ha olvidado de las particularidades de los conjuntos de tamaño \(3\) y sólo recuerda que tienen \(3\) elementos.

Conjuntos finitos e infinitos

Sabemos que si \(A\subseteq B\), entonces \(A\preceq B\). En particular podemos suponer que \(A\subsetneq B\). Con esta hipótesis adicional podemos preguntarnos si es posible que \(A\sim B\).

Notemos que hay algunos casos en lo que no será posible obtener \(A\sim B\). Por ejemplo si \(A=\{a,b,c\}\) y \(B=\{a,b,c,d\}\), entonces no es posible que podamos hacer una función función suprayectiva entre \(A\) y \(B\). Además, no importa como sea el subconjunto propio de \(B\), no será posible que sea del mismo tamaño que \(B\).

Por otro lado, hay casos donde un subconjunto propio sí tiene el mismo tamaño que el original. Por ejemplo, si consideramos \(\mathbb{N}\) y el conjunto de números pares, \(2\mathbb{N}=\{n\in\mathbb{N}\mid\exists m(n=2m)\}\), entonces es claro que \(2\mathbb{N}\subsetneq\mathbb{N}\). Sin embargo, la función \(f\colon\mathbb{N}\to 2\mathbb{N}\) dada por \(f(n)=2n\) es biyectiva, por lo que \(\mathbb{N}\sim 2\mathbb{N}\).

Esta es la distinción que usaremos para definir conjuntos finitos e infinitos.

Definición (Dedekind)

Un conjunto \(A\) es infinito si existe un subconjunto propio \(S\subsetneq A\) tal que \(A\sim S\). En otro caso diremos que \(A\) es finito.

Con esta definición, podemos decir que \(\mathbb{N}\) es infinito y que el conjunto \(B=\{a,b,c,d\}\) es finito, como esperábamos.

La intuición es que los conjuntos finitos son “chicos” y los infinitos son “grandes”. Siguiendo esta intuición, si tenemos alguien más grande que un conjunto infinito, entonces debería ser infinito. Viceversa, si tenemos alguien más chico que un conjunto finito, entonces debería ser finito.

Proposición

Sea \(A\subseteq B\). Si \(A\) es infinito, entonces \(B\) es infinito.

Demostración

Como \(A\) es infinito, entonces existe un subconjunto propio \(S\subsetneq A\) y una función biyectiva \(f\colon S \to A\). Como \(A\subseteq B\), entonces podemos considerar el conjunto

\[S\cup (B\setminus A).\]

Notemos que \(S\cap (B\setminus A)=\emptyset\), por lo que podemos considerar la función \(g\colon S\cup (B\setminus A)\to B\) dada por

\[g(x) = \begin{cases} f(x) & \text{si } x\in S, \\ x & \text{si } x\in B\setminus A. \end{cases}\]

Para ver que \(g\) es inyectiva consideremos \(x,y\in S\cup (B\setminus A)\) tales que \(g(x)=g(y)\). Notemos que la suposición y la definición de \(g\) implican que \(x,y\in S\) o \(x,y\in B\setminus A\). En el primer caso, por definición de \(g\), tenemos que \(f(x)=f(y)\), por lo que \(x=y\), pues \(f\) es inyectiva. En el segundo caso, por definición de \(g\), tenemos que \(x=y\). Así, \(g\) es inyectiva.

Para ver que \(g\) es suprayectiva, consideremos \(b\in B\). Si \(b\in A\), entonces usamos que \(f\) es suprayectiva para obtener un \(s\in S\) tal que \(f(s)=b\). Si \(b\in B\setminus A\), entonces usamos que \(b\in S\cup (B\setminus A)\) y así \(g(b)=b\).

Como la definición de finito es no ser infinito, entonces podemos obtener el resultado correspondiente con conjuntos finitos haciendo la contrapuesta de la proposición anterior.

Corolario

Sea \(B\subseteq A\). Si \(A\) es finito, entonces \(B\) es finito.

En este momento es difícil ver resultados interesantes acerca de conjuntos infinitos. Sin embargo, ya tenemos lo suficiente para mostrar algunos resultados acerca de conjuntos finitos.

Lo primero será ver otra forma de decir cuando un conjunto es finito. Para facilitar la notación usaremos, de manera intuitiva, la definición de número natural de teoría de conjuntos. Esto es, \(n=\{0,1,\ldots,n-1\}\). De esta manera, \(0=\emptyset\), \(1=\{0\}=\{\emptyset\}\), \(2=\{0,1\}\), etc. Con esta definición de número natural tenemos que \(x\in n\) si y sólo si \(x<n\).

Definición (Cantor)

Un conjunto \(A\) es finito si existe un número natural \(n\in\mathbb{N}\) tal que \(A\sim n\). En otro caso diremos que \(A\) es infinito.

La equivalencia entre las definiciones de Dedekind y Cantor se sigue de un axioma que no veremos en este curso, el axioma de elección.

Los naturales, definidos como arriba, son los representantes de los conjuntos finitos. Por lo tanto, muchos argumentos acerca de conjuntos finitos se pueden hacer con los naturales.

Una observación acerca de los números naturales, definidos como arriba, es la siguiente

Proposición

Si \(n,m\in\mathbb{N}\), entonces \(n<m\) si y sólo si \(n\subsetneq m\).

Demostración

Como \(n<m\), entonces para todo natural \(x\) se satisface que \(x<n\) implica \(x<m\). Con esto, \(n\subsetneq m\). Por otro lado, como \(n\ne m\), entonces la contención es propia, como queríamos.

Ahora supongamos que \(n\subsetneq m\). Como la contención es propia, entonces existe un \(x\in m\) tal que \(x\notin n\). Como \(x\notin n\), entonces \(n\leq x\) y como \(x\in m\), entonces \(x<m\). Por lo tanto, \(n<m\).

Si usamos la equivalencia entre las definiciones de finito de Dedekind y Cantor, entonces obtenemos que si \(n<m\), entonces no hay una biyección entre \(n\) y \(m\). Si escribimos la contrapuesta de esta implicación, obtenemos el siguiente resultado.

Corolario

Si \(n\sim m\), entonces \(n=m\).

La siguiente propiedad se puede demostrar con conjuntos finitos arbitrarios. Primero la demostraremos con números naturales y después veremos cómo esto implica que también se cumple con conjuntos finitos arbitrarios. Es más fácil demostrarla con conjuntos finitos arbitrarios, pero queremos dar un ejemplo de que argumentar con números naturales implica que se cumple con conjuntos finitos.

Proposición

Sean \(n\in\mathbb{N}\) y \(f\colon n\to n\) una función. Los siguientes son equivalentes

1. \(f\) es inyectiva.
2. \(f\) es suprayectiva.

Demostración

Supongamos que \(f\) es inyectiva. Si \(f\) no es suprayectiva, entonces existe un \(x\in n\) tal que no existe un \(y\in n\) tal que \(f(y)=x\). En otras palabras, existe \(x\in n\) tal que \(x\notin\text{im}(f)\). Esto último significa que \(\text{im}(f)\subsetneq n\). Además, como \(f\) es inyectiva, entonces \(f\colon n\to\text{im}(f)\) es biyectiva, lo que contradice el corolario anterior. Por lo tanto, \(f\) es suprayectiva.

Ahora supongamos que \(f\) es suprayectiva. Si \(f\) no es inyectiva, entonces existen \(x,y\in n\) tales que \(x\ne y\) y \(f(x)=f(y)\), lo que significa que \(f\vert_{n\setminus\{y\}}\colon n\setminus\{y\}\to n\) sigue siendo suprayectiva. Si repetimos este proceso, entonces llegaremos a que existe una función biyectiva \(g\colon m\to n\) con \(m\subsetneq n\), lo que contradice el corolario anterior. Por lo tanto, \(f\) es inyectiva.

Ahora veamos como deducir el resultado general a partir de este resultado particular.

Corolario

Sean \(A\) y \(B\) conjuntos finitos tales que \(A\sim B\). Si \(f\colon A\to B\) es una función , entonces los siguientes son equivalentes:

1. \(f\) es inyectiva.
2. \(f\) es suprayectiva.

Demostración

Por las hipótesis sobre \(A\) y \(B\) tenemos que existen \(n\in\mathbb{N}\) y funciones biyectivas \(g\colon n\to A\) y \(h\colon n\to B\). Consideramos la composición \(h^{-1}\circ f\circ g\colon n\to n\) y notamos que si \(f\) es inyectiva entonces \(h^{-1}\circ f\circ g\) es inyectiva. Por lo tanto, por la proposición anterior \(h^{-1}\circ f\circ g\) es suprayectiva. Como \(g\) y \(h^{-1}\) son biyectivas, entonces \(f\) es suprayectiva.

De manera análoga, si \(f\) es suprayectiva, entonces \(h^{-1}\circ f\circ g\) es suprayectiva, lo que implica que \(f\) es inyectiva.