Archivo del Autor: Gabriela Hernández Aguilar

Teoría de los Conjuntos I: El lema de Zorn

Por Gabriela Hernández Aguilar

Introducción

En la entrada anterior vimos algunas equivalencias del axioma de elección. En esta nueva entrada veremos algunas otras equivalencias del mismo axioma, pero en términos de órdenes. Estas versiones no son tan evidentes e incluso resultan sorprendentes. En muchas ramas de las matemáticas se apela a las formas equivalentes del axioma de elección que veremos a continuación, por lo que es importante tratarlas.

Familias de caracter finito

Para llegar al lema de Zorn, necesitaremos desarrollar previamente algo de teoría. La siguiente definición jugará un papel clave a lo largo de esta entrada.

Definición. Sea $\mathcal{F}$ una familia de conjuntos. Decimos que $\mathcal{F}$ es de carácter finito si dado un conjunto $A$ se tiene que $A\in\mathcal{F}$ si y sólo si todo subconjunto finito de $A$ está en $\mathcal{F}$.

Veamos los siguientes ejemplos.

Ejemplo.

Sea $\mathcal{F}$ la familia vacía. Luego, por vacuidad, un conjunto $A\in\mathcal{F}$ si y sólo si todo subconjunto finito de $A$ está en $\mathcal{F}$.

$\square$

Ejemplo.

Sea $X$ un conjunto y $\mathcal{F}=\mathcal{P}(X)$ su conjunto potencia. Luego, si $A$ es un conjunto tal que $A\in\mathcal{F}$, entonces $A\subseteq X$ y, por tanto, todo subconjunto finito de $A$ es un subconjunto de $X$, por lo que todo subconjunto finito de $A$ está en $\mathcal{P}(X)$. Ahora, sea $A$ un conjunto tal que cualquiera de sus subconjuntos finitos está en $\mathcal{P}(X)$. Veamos que $A\in\mathcal{P}(X)$, es decir, que $A\subseteq X$. Sea pues $a\in A$ cualquier elemento. Luego, $\set{a}$ es un subconjunto finito de $A$ por lo que $\set{a}\in\mathcal{P}(X)$ y, en consecuencia, $\set{a}\subseteq X$, lo cual es equivalente a que $a\in X$. Por tanto, $A\subseteq X$, lo que muestra que $A\in\mathcal{P}(X)$. De modo que para todo conjunto $X$ su conjunto potencia $\mathcal{P}(X)$ es una familia de conjuntos de carácter finito.

En el último ejemplo tenemos una familia de carácter finito no vacía que tiene al vacío como elemento, pues el conjunto potencia de cualquier conjunto siempre tiene al vacío Esto no sólo ocurre para este caso particular, si tenemos una familia no vacía de carácter finito, entonces el conjunto vacío es un elemento de dicha familia. En efecto, sea $\mathcal{F}$ cualquier familia no vacía de carácter finito. Luego, sea $A\in\mathcal{F}$. Dado que $\emptyset\subseteq A$ y $\emptyset$ es finito, entonces $\emptyset\in\mathcal{F}$.

$\square$

Un poco más adelante necesitaremos del siguiente lema. En un conjunto parcialmente ordenado $(X,\leq)$, una cadena es un subconjunto $Y$ de $X$ tal que la restricción de $\leq$ a $Y$ es un orden total. Dicho de otra forma, en $Y$ cualesquiera dos elementos son $\leq$-comparables.

Lema. Sea $\mathcal{F}$ una familia de carácter finito y sea $\mathcal{B}$ una cadena en $\mathcal{F}$ con respecto a la contención, entonces $\bigcup\mathcal{B}\in\mathcal{F}$.

Demostración.

Dado que $\mathcal{F}$ es de carácter finito basta mostrar que cada subconjunto finito de $\bigcup\mathcal{B}$ está en $\mathcal{F}$. Sea $F$ un subconjunto finito de $\bigcup\mathcal{B}$. Luego, para cada $x\in F$ existe $B_x\in\mathcal{B}$ tal que $x\in B_x$. Dado que $F$ es finito existe un natural $n$ y una función biyectiva $f:n\to F$, por lo que podemos expresar a $F$ como el conjunto $\set{f(m):m\in n}$. Luego, $F\subseteq\cup_{m\in n}B_{f(m)}$. Ahora, como $\mathcal{B}$ es una cadena, entonces existe $m_0\in n$ tal que $B_{f(m)}\subseteq B_{f(m_0)}$ para todo $m\in n$, así que $F\subseteq B_{f(m_0)}$. Finalmente, como $B_{f(m_0)}\in\mathcal{F}$ y $F$ es un subconjunto finito de $B_{f(m_0)}$, entonces $F\in\mathcal{F}$. Esto muestra que $\bigcup\mathcal{B}\in\mathcal{F}$.

$\square$

El lema de Tukey-Teichmüller

Para probar el siguiente teorema debemos asumir que el axioma de elección se cumple. El resultado que enunciamos a continuación John W. Tukey lo enuncia y demuestra en su tesis doctoral en 1939.

Teorema. (Lema de Tukey-Teichmüller). Toda familia no vacía de carácter finito tiene un elemento $\subseteq$-maximal.

Demostración.

La prueba será por contradicción. Supongamos entonces que existe una familia no vacía $\mathcal{F}$ de carácter finito tal que no tiene elementos $\subseteq$-maximales. Luego, para cada $F\in\mathcal{F}$ definamos $\mathcal{A}_F=\set{E\in\mathcal{F}:F\subset E}$, es decir, $\mathcal{A}_F$ es el conjunto de todos los elementos de $\mathcal{F}$ que contienen propiamente a $F$. Dado que $\mathcal{F}$ no tiene elementos $\subseteq$-maximales, para cada $F\in\mathcal{F}$ el conjunto $\mathcal{A}_F$ es no vacío.

Sea $\mathcal{E}=\set{\mathcal{A}_F:F\in\mathcal{F}}$, la cual es una famila no vacía de conjuntos no vacíos. Por el teorema de la entrada anterior sobre algunas de las equivalencias del axioma de elección, existe una función $f:\mathcal{F}\to\mathcal{E}$ de tal forma que $f(F)\in\mathcal{A}_F$ para todo $F\in\mathcal{F}$. Luego, como $f(F)\in\mathcal{A}_F$ para cada $F\in\mathcal{F}$, entonces $F\subset f(F)$ para todo $F\in\mathcal{F}$.

Utilizando esta función $f$ diremos que una subfamilia $\mathcal{G}$ de $\mathcal{F}$ es $f$-inductiva si tiene las siguientes propiedades:

  1. $\emptyset\in\mathcal{G}$.
  2. $A\in\mathcal{G}$ implica $f(A)\in\mathcal{G}$.
  3. Si $\mathcal{B}$ es una $\subseteq$-cadena contenida en $\mathcal{G}$, entonces $\bigcup\mathcal{B}\in\mathcal{G}$.

Dado que $\mathcal{F}$ es una familia de carácter finito no vacía tenemos que $\emptyset\in\mathcal{F}$. Ahora, si $F\in\mathcal{F}$, entonces $f(F)\in\mathcal{F}$ por la elección de la función $f$. Finalmente, si $\mathcal{B}$ es una $\subseteq$-cadena contenida en $\mathcal{F}$, entonces, por el lema previo, $\bigcup\mathcal{B}\in\mathcal{F}$. Así pues, $\mathcal{F}$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva. Consecuentemente, la familia de conjuntos $\set{\mathcal{G}\subseteq\mathcal{F}:\mathcal{G}\ \textnormal{es $f$-inductiva}}$ es no vacía. Podemos considerar así al conjunto $\mathcal{G}_0:=\bigcap\set{\mathcal{G}\subseteq\mathcal{F}:\mathcal{G}\ \textnormal{es $f$-inductiva}}$.

Veamos que $\mathcal{G}_0$ es $f$-inductiva. Primero, como $\emptyset\in\mathcal{G}$ para toda subfamilia $f$-inductiva de $\mathcal{F}$, entonces $\emptyset\in\mathcal{G}_0$. Ahora, si $A\in\mathcal{G}_0$, entonces $A\in\mathcal{G}$ para toda familia $f$-inductiva de $\mathcal{F}$, por lo que, por definición de subfamilia $f$-inductiva, $f(A)\in\mathcal{G}$ para toda familia $f$-inductiva de $\mathcal{F}$ y, por ende, $f(A)\in\mathcal{G}_0$. Por último, si $\mathcal{B}$ es un $\subseteq$-cadena contenida en $\mathcal{G_0}$, entonces $\mathcal{B}$ es una $\subseteq$-cadena contenida en cada subfamilia $f$-inductiva de $\mathcal{F}$, por lo que $\bigcup\mathcal{B}$ pertenece a cada una de estas subfamilias $f$-inductivas y, consecuentemente, $\bigcup\mathcal{B}\in\mathcal{G}_0$. Esto muestra que $\mathcal{G}_0$ es $f$-inductiva.

Por el párrafo anterior tenemos que toda subfamilia $f$-inductiva de $\mathcal{F}$ contiene a $\mathcal{G}_0$. Lo que haremos ahora es probar que $\mathcal{G}_0$ es una $\subseteq$-cadena, es decir, que para cualesquiera $A$ y $B$ elementos de $\mathcal{G}_0$ se tiene que $A\subseteq B$ o $B\subseteq A$.

Definamos el conjunto $$\mathcal{H}=\{A\in\mathcal{G}_0:\textnormal{si $B\in\mathcal{G}_0$ y $B\subset A$, entonces $f(B)\subseteq A$}\}.$$

Notemos que $\mathcal{H}$ es no vacío. En efecto, si consideramos $A=\emptyset$, entonces $A\in\mathcal{H}$, ya que si $B\in\mathcal{G}_0$ es un subconjunto propio de $A$, entonces, por vacuidad, $f(B)\subseteq A$, pues $\emptyset$ no tiene subconjuntos propios.

Veamos ahora que para cualquier $A\in\mathcal{H}$ y cualquier $C\in\mathcal{G}_0$, se cumple que $C\subseteq A$ o $f(A)\subseteq C$. Sea pues $A\in\mathcal{H}$ cualquier elemento. Definamos $\mathcal{G}_A=\set{C\in\mathcal{G}_0:C\subseteq A\ o\ f(A)\subseteq C}$. Notemos que si $C\in\mathcal{G}_A$, entonces $C\subseteq A$ o bien, $f(A)\subseteq C$ por lo que $A\subseteq C$, ya que $A\subset f(A)$. Así que para probar que $A\subseteq C$ o $C\subseteq A$ para cualquier $C\in\mathcal{G}_0$, basta probar que $\mathcal{G}_A=\mathcal{G}_0$.

Lo que haremos será mostrar que $\mathcal{G}_A$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva. Primero, como $\emptyset\in\mathcal{G}_0$ y $\emptyset\subseteq A$, entonces $\emptyset\in\mathcal{G}_A$. Luego, si $C\in\mathcal{G}_A$, entonces o bien $C\subset A$ o $C=A$ o $f(A)\subseteq C$. Si $C\subset A$, entonces $f(C)\subseteq A$ pues $A\in\mathcal{H}$. Si $C=A$, entonces $f(A)=f(C)$ y por tanto $A\subseteq f(A)=f(C)$. Si $f(A)\subseteq C$, entonces $A\subseteq C$ y, por ende, $A\subseteq f(C)$, ya que $C\subset f(C)$. En cualquier posibilidad tenemos que $f(C)\subseteq A$ o $f(A)\subseteq f(C)$, lo que implica que $f(C)\in\mathcal{G}_A$. Sea ahora $\mathcal{B}$ una cadena en $\mathcal{G}_A$. Si $C\subseteq A$ para todo $C\in\mathcal{B}$, entonces $\bigcup\mathcal{B}\subseteq A$. Si existe $C\in\mathcal{B}$ tal que $f(A)\subseteq C$, entonces $f(A)\subseteq\bigcup\mathcal{B}$, pues $C\subseteq\bigcup\mathcal{B}$. Como estas son las únicas posibilidades, concluimos que o bien $\bigcup\mathcal{B}\subseteq A$ o $f(A)\subseteq\bigcup\mathcal{B}$ y, por tanto, $\bigcup\mathcal{B}\in\mathcal{G}_A$. Estas propiedades muestran que $\mathcal{G}_A$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva.

En consecuencia, $\mathcal{G}_0\subseteq\mathcal{G}_A$. Luego, por definición tenemos que $\mathcal{G}_A\subseteq\mathcal{G}_0$ y, por consiguiente, tenemos la igualdad $\mathcal{G}_0=\mathcal{G}_A$.

Así pues, para todo $A\in\mathcal{H}$ y cualquier $C\in\mathcal{G}_0$, o bien $C\subseteq A$ o $A\subseteq C$.

Para terminar de probar que $\mathcal{G}_0$ es una cadena basta probar que $\mathcal{H}$ es una subfamilia $f$-inductiva de $\mathcal{F}$. Primero, ya vimos que $\emptyset\in\mathcal{H}$. Ahora, sea $A\in\mathcal{H}$ y sea $B\in\mathcal{G}_0$ cualquier elemento tal que $B\subset f(A)$. Dado que $B\in\mathcal{G}_A=\mathcal{G}_0$, entonces $B\subseteq A$ o $f(A)\subseteq B$, pero hemos supuesto que $B\subset f(A)$, por lo que es imposible que $f(A)\subseteq B$ y, en consecuencia, $B\subseteq A$. Luego, si $B\subset A$, entonces $f(B)\subseteq A$ pues $A\in\mathcal{H}$ y, por tanto, $f(B)\subseteq f(A)$. Si $B=A$, entonces $f(B)=f(A)\subseteq f(A)$. Por lo tanto, $f(B)\subseteq f(A)$. Esto muestra que $f(A)\in\mathcal{H}$. Para finalizar, sea $\mathcal{B}$ una $\subseteq$-cadena de $\mathcal{H}$. Sea $B\in\mathcal{G}_0$ cualquier elemento tal que $B\subset\bigcup\mathcal{B}$. Si existe $C\in\mathcal{B}$ tal que $B\subseteq C$, entonces $B\subset C$ o $B=C$, en el primer caso tendríamos que $f(B)\subseteq C$, porque $C\in\mathcal{H}$, y por ende que $f(B)\subseteq\bigcup\mathcal{B}$; supongamos ahora que $B=C$, entonces, $B\in\mathcal{H}$ (pues $C$ es un elemento de $\mathcal{H}$) y $\bigcup\mathcal{B}\in\mathcal{G}_0=\mathcal{G}_B$. Así, $\bigcup\mathcal{B}\subseteq B$ o $f(B)\subseteq\bigcup\mathcal{B}$, pero $\bigcup\mathcal{B}\subseteq B$ es imposible pues asumimos que $B\subset\bigcup\mathcal{B}$, por lo que debe ocurrir necesariamente que $f(B)\subseteq\bigcup\mathcal{B}$. De modo que si existe $C\in\mathcal{B}$ tal que $B\subseteq C$, entonces $f(B)\subseteq\bigcup\mathcal{B}$. Supongamos ahora que $B\nsubseteq C$ para todo $C\in\mathcal{B}$. Ahora, como $B\in\mathcal{G}_0$ y $\mathcal{G}_0=\mathcal{G}_C$ para todo $C\in\mathcal{B}\subseteq\mathcal{H}$, entonces $B\in\mathcal{G}_C$ para todo $C\in\mathcal{B}$. Consecuentemente, $B\subseteq C$ o $f(C)\subseteq B$ para cada $C\in\mathcal{B}$, pero asumimos ahora que $B\nsubseteq C$ para todo $C\in\mathcal{B}$, por lo que $f(C)\subseteq B$ para todo $C\in\mathcal{B}$ y, por consiguiente, $C\subseteq B$ para todo $C\in\mathcal{B}$, lo cual implica que $\bigcup\mathcal{B}\subseteq B$ pero esto contradice el hecho de que $B\subset\bigcup\mathcal{B}$. De modo que, necesariamente, debe existir $C\in\mathcal{B}$ tal que $B\subseteq C$, lo cual vimos implica que $f(B)\subseteq\bigcup\mathcal{B}$. Esto demuestra que $\bigcup\mathcal{B}\in\mathcal{H}$. Por lo tanto, $\mathcal{H}$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva.

Como consecuencia del párrafo anterior tenemos que $\mathcal{G}_0\subseteq\mathcal{H}$, pero por definición sabemos que $\mathcal{H}\subseteq\mathcal{G_0}$, lo cual implica $\mathcal{G}_0=\mathcal{H}$.

De esta serie de argumentos tenemos que si $A,B\in\mathcal{G}_0$, entonces $A\in\mathcal{H}$ y $B\in\mathcal{G}_A$, por lo que $B\subseteq A$ o bien $f(A)\subseteq B$, es decir, $B\subseteq A$ o $A\subseteq B$. Por lo tanto, cualesquiera dos elementos de $\mathcal{G}_0$ son $\subseteq$-comparables y, en consecuencia, $\mathcal{G}_0$ es una $\subseteq$-cadena.

Consideremos ahora $M=\bigcup\mathcal{G_0}$, el cual es un elemento de $\mathcal{G_0}$ por ser $\mathcal{G}_0$ $f$-inductiva y una subcadena de sí misma. Ahora para todo $A\in\mathcal{G}_0$ se tiene que $A\subseteq\bigcup\mathcal{G}_0=M$. Por otro lado, como $M\in\mathcal{G}_0$, entonces $f(M)\in\mathcal{G}_0$ y, por tanto, $f(M)\subseteq M$; sin embargo, como $M\in\mathcal{F}$, entonces $M\subset f(M)$, pero esto es una contradicción.

Dado que esta contradicción viene de suponer que $\mathcal{F}$ no tiene un elemento $\subseteq$-maximal, concluimos que $\mathcal{F}$ sí tiene un elemento $\subseteq$-maximal.

$\square$

El principio maximal de Hausdorff

Pasemos ahora a un resultado muy cercano al lema de Zorn, demostrado por Felix Hausdorff en 1914. Se obtiene rápidamente al aplicar el lema de Tukey-Teichmüller.

Teorema. (Principio Maximal de Hausdorff). Cualquier conjunto no vacío y parcialmente ordenado tiene una cadena $\subseteq$-maximal.

Demostración.

Sea $A\neq \emptyset$ y $\leq$ un orden parcial para $A$. Sea $\mathcal{C}=\set{B\subseteq A:B\ \textnormal{es una cadena}}$. Recordemos que $B\subseteq A$ es una cadena en $A$ si cualesquiera dos elementos en $B$ son comparables con el orden de $A$.

Lo que queremos probar es que existe $C\in\mathcal{C}$ tal que ningún otro elemento de $\mathcal{C}$ contiene propiamente a $C$. Para ello probaremos que $\mathcal{C}$ es una familia no vacía de carácter finito y aplicaremos el lema de Tukey-Teichmüller para concluir que $\mathcal{C}$ tiene un elemento $\subseteq$-maximal.

Supongamos que $B\in\mathcal{C}$ es cualquier elemento. Luego, sea $B’\subseteq B$ un conjunto finito. Veamos que $B’$ es una cadena en $A$, es decir, que cualesquiera dos elementos de $B’$ son comparables con el orden de $A$. Si $B’=\emptyset$, por vacuidad $B’$ es una cadena en $A$. Asumamos ahora que $B’\not=\emptyset$ y sean $a,b\in B’$ cualesquiera elementos. Luego, como $a,b\in B’$, entonces $a,b\in B$ y como $B$ es una cadena en $A$, entonces $a$ y $b$ son comparables con el orden de $A$, y esto muestra que $B’$ es también una cadena en $A$, por lo que $B’\in\mathcal{C}$.

Supongamos ahora que $B$ es un conjunto tal que cualquiera de sus subconjuntos finitos está en $\mathcal{C}$. Ciertamente $B\subseteq A$, pues si $a\in B$, entonces $\set{a}\in\mathcal{C}$, es decir, $\set{a}$ es una cadena en $A$, por lo que $a\in A$. Ahora, si $a,b\in B$, entonces $\set{a,b}\in\mathcal{C}$ y, por tanto, $\set{a,b}$ es una cadena en $A$, es decir, $a$ y $b$ son comparables con el orden de $A$. Por tanto, $B$ es una cadena en $A$, ya que cualesquiera dos de sus elementos son comparables con el orden de $A$.

Esta serie de argumentos muestra que $\mathcal{C}$ es una familia de conjuntos de carácter finito. Por el lema de Tukey-Teichmüller, $\mathcal{C}$ tiene un elemento $\subseteq$-maximal, es decir, existe una cadena en $A$ $\subseteq$-maximal.

$\square$

El lema de Zorn

Finalmente enunciaremos y demostraremos una de las versiones más usadas del axioma de elección: el conocido lema de Zorn. Este resultado fue demostrado por Max Zorn en 1935 (y de manera independiente por Kazimierz Kuratowski en 1922). Para nuestra demostración usaremos el principio maximal de Hausdorff.

Teorema. (Lema de Kuratowski-Zorn). Cualquier conjunto parcialmente ordenado y no vacío en el cual toda cadena tiene una cota superior tiene un elemento maximal.

Demostración.

Sea $(A,\leq)$ un conjunto parcialmente ordenado no vacío en el que toda cadena tiene una cota superior. Por el principio maximal de Hausdorff el conjunto $A$ tiene una cadena $\subseteq$-maximal. Sea pues $C\subseteq A$ una cadena $\subseteq$-maximal de $A$. Luego, por hipótesis, existe $a\in A$ cota superior de $C$, es decir, $c\leq a$ para todo $c\in C$. Ahora, notemos que $a$ es maximal con respecto a $\leq$, ya que si existiera $x\in A$ tal que $a<x$, entonces $x\not=a$ y $x\notin C$, por lo que $C\cup\set{x}$ sería una cadena en $A$ que contiene propiamente a $C$ y esto contradice la maximalidad de $C$ con respecto a la contención en el conjunto de cadenas de $A$. Por lo tanto, $a$ es un elemento maximal en $A$.

$\square$

Tarea moral

  1. Prueba que la intersección de un sistema de familias $f$-inductivas es una familia $f$-inductiva.
  2. Sea $X$ un conjunto. Prueba que si $X$ puede ser bien ordenado, entonces $\mathcal{P}(X)$ puede ser linealmente ordenado. (Sugerencia: dados $A,B\in\mathcal{P}(X)$ considera al mínimo de $A\Delta B$).
  3. Demuestra que para cualesquiera dos conjuntos $A$ y $B$, o bien existe una función inyectiva $f:A\to B$, o bien existe una función inyectiva $g:B\to A$.
  4. Demuestra que la colección $\mathcal{F}$ de subconjuntos finitos de $\mathbb{N}$ no es de caracter finito.

Más adelante…

En la siguiente entrada comenzaremos probando un resultado algo antintuitivo: que cualquier conjunto puede ser bien ordenado. Por ejemplo, a $\mathbb{R}$ se le podrá dar un orden de manera que cualquier subconjunto no vacío tenga mínimo. ¡Esto es muy difícil de imaginar! Sobre todo si pensamos en el orden usual de $\mathbb{R}$. El resultado que probaremos será existencial (y no constructivo), así que aunque tengamos la garantía de que dicho buen orden existe, no podremos saber muy bien cuál es.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Axioma de elección

Por Gabriela Hernández Aguilar

Introducción

En esta entrada abordaremos un axioma relevante no sólo en teoría de conjuntos sino en muchas ramas de las matemáticas. Distintas proposiciones aparentemente sencillas no podrían demostrarse sin su ayuda y algunas de sus consecuencias son tan poderosas que cuesta trabajo aceptarlas. Es por eso que el llamado axioma de elección ha sido controversial desde su formulación a manos de Ernst Zermelo en 1904.

Funciones de elección

Comenzaremos dando una definición para después enunciar el mencionado axioma.

Definición. Sea $A$ un conjunto. Una función de elección para $A$ es una función $f:\mathcal{P}(A)\setminus\{\emptyset\}\to A$ tal que, para todo $B\in\mathcal{P}(A)\setminus\{\emptyset\}$, se tiene que $f(B)\in B$.

Ejemplo.

Sea $A=\set{0,1}$. Luego, $\mathcal{P}(A)=\{\emptyset,\{0\},\{1\},\{0,1\}\}$. Si definimos $f:\mathcal{P}(A)\setminus\set{\emptyset}\to A$ por medio $f=\set{(\set{0},0),(\set{1},1),(\set{0,1},1)}$, entonces $f$ es una función de elección.

$\square$

El siguiente resultado muestra que existe una gran cantidad de conjuntos que tienen una función de elección.

Proposición. Si $X$ es un conjunto finito no vacío, entonces $X$ tiene una función de elección.

Demostración.

Sea $X$ un conjunto finito y no vacío. Luego, por ser finito, existe un número natural $n$ y una función biyectiva $f:n\to X$ y, además, $n\not=0$ ya que $X$ es no vacío. Ahora, para cada $A\subseteq X$ no vacío consideremos su imagen inversa, $f^{-1}[A]=\set{m\in n:f(m)\in A}$. Dado que $f^{-1}[A]\not=\emptyset$, entonces existe $\min(f^{-1}[A])$. Definamos $F:\mathcal{P}(X)\setminus\set{\emptyset}\to X$ por medio de $F(A)=f(\min(f^{-1}[A]))$. Luego, $F$ es una función de elección para $X$.

$\square$

Axioma de elección y equivalencias

Aunque todos los conjuntos finitos tengan función de elección, resultará imposible demostrar lo mismo para todos los conjuntos. Es por ello que necesitaremos agregar un axioma a nuestra teoría.

Axioma de elección. Todo conjunto no vacío tiene una función de elección.

Nos discutir varios de los usos de este axioma, pero para ello es conveniente poder pensarlo de muchas maneras. En esta primera entrada enunciaremos una serie de equivalencias a este teorema muy relacionadas con «elegir». En la siguiente entrada enunciaremos equivalencias relacionadas con «ordenar».

Teorema. Las siguientes proposiciones son equivalentes:

  1. El axioma de elección.
  2. Si $\mathcal{A}$ es una familia no vacía de conjuntos no vacíos y ajenos dos a dos, entonces existe un conjunto $B$ tal que para todo $A\in\mathcal{A}$, se tiene que $A\cap B$ es un conjunto unitario.
  3. Toda función suprayectiva tiene al menos una inversa derecha.
  4. Si $\set{A_\alpha}_{\alpha\in\Gamma}$ es tal que $A_\alpha\not= \emptyset$ y $A_\alpha\cap A_\beta=\emptyset$ para cualesquiera $\alpha,\beta\in\Gamma$ con $\alpha\not=\beta$, entonces existe $B\subseteq\cup_{\alpha\in\Gamma}A_\alpha$ tal que $B\cap A_\alpha$ es unitario para cada $\alpha\in\Gamma$.
  5. Si $\set{A_\alpha}_{\alpha\in \Gamma}$ es una famila indizada no vacía de conjuntos no vacíos, entonces existe una función $f:\Gamma\to\cup_{\alpha\in\Gamma}A_\alpha$ tal que para cada $\alpha\in\Gamma$, se cumple que $f(\alpha)\in A_\alpha$.
  6. Si $F:X\to \mathcal{P}(Y)\setminus\set{\emptyset}$ es una función, entonces existe una función $f:X\to Y$ tal que $f(x)\in F(x)$ para todo $x\in X$.

La diferencia entre $2$ y $4$ es que en $5$ se pide que $B$ sea subconjunto de la unión de la familia.

Demostración.

$1)\Rightarrow 2)$ Supogamos que el axioma de elección es válido. Sea $\mathcal{A}$ una familia no vacía de conjuntos no vacíos ajenos dos a dos.

Sea $C=\bigcup\mathcal{A}$. Luego, podemos fijar $f:\mathcal{P}(C)\setminus\set{\emptyset}\to C$ una función de elección. Notemos que si $A\in\mathcal{A}$, entonces $A\subseteq C$, por lo que $A\in\mathcal{P}(C)\setminus\set{\emptyset}$. Definamos $B=\set{f(A):A\in\mathcal{A}}$. Veamos ahora que $B\cap A$ es un conjunto unitario para todo $A\in\mathcal{A}$.

Sea $A\in\mathcal{A}$ un elemento arbitrario. Notemos que $f(A)\in B$ por definición de $B$, pero también $f(A)\in A$ ya que $f$ es una función de elección en $C$. Por lo tanto, $\set{f(A)}\subseteq A\cap B$. Ahora, si $x\in A\cap B$, en particular, $x\in B$, por lo que $x=f(A’)\in A’$ para algún $A’\in\mathcal{A}$ y así $x\in A\cap A’$. En consecuencia, $A=A’$ pues elementos distintos de $\mathcal{A}$ son ajenos dos a dos. Tenemos entonces que $x=f(A’)=f(A)$, lo cual es suficiente para concluir que $A\cap B=\set{f(A)}$, es decir, $A\cap B$ es un conjunto unitario.

$2)\Rightarrow 3)$

Sean $A$ y $B$ conjuntos y $f:A\to B$ una función suprayectiva. Para cada $x\in B$ definamos $A_x=\set{a\in A:f(a)=x}$. Notemos que para cada $x\in B$, se tiene que $A_x\not=\emptyset$, pues $f$ es suprayectiva. Además, si $x\not=x’$, entonces $A_x\cap A_{x’}=\emptyset$, ya que si existiera un elemento $y\in A_x\cap A_{x’}$, tendríamos que $f(y)=x$ y $f(y)=x’$ y, por consiguiente, $x=x’$ ya que $f$ es una función, pero esto contradice que $x\not=x’$. Así pues, si $x\not=x’$, entonces $A_x\cap A_{x’}=\emptyset$.

Consideremos a la familia de conjuntos $\mathcal{A}=\set{A_x:x\in B}$ la cual consta de conjuntos no vacíos y ajenos dos a dos. Por hipótesis, existe un conjunto $C$ tal que $C\cap A_x$ es un conjunto unitario para cada $A_x\in\mathcal{A}$. Para $x\in B$, denotemos por $a_x$ al único elemento del conjunto $C\cap A_x$. Definamos $g:B\to A$ por medio de $g(x)=a_x$. Expresando a $g$ como un subconjunto de $B\times A$ tenemos que $g=\set{(x,a_x):x\in B}$. Notemos que $g$ es una función, ya que si $(w,v),(w,z)\in g$, entonces $(w,v)=(x,a_x)$ y $(w,z)=(y,a_y)$ para algunos $x,y\in B$. De las iguladades anteriores se sigue que $w=x=y$ y, por tanto, $v=a_x=a_y=z$. Por tanto, $g$ es función. Finalmente, veamos que $g$ es inversa derecha de $f$, es decir, que $f\circ g:B\to B$ es la función identidad; esto es, $f\circ g=Id_B$, donde $Id_B$ es la función que va de $B$ en $B$ tal que $Id_B(x)=x$ para cada $x\in B$.

Sea pues $x\in B$ un elemento arbitrario. Luego, $(f\circ g)(x)=f(g(x))=f(a_x)=x$, pues $a_x\in A_x$. Por lo tanto, $f\circ g=Id_B$, lo que muestra que $g$ es inversa derecha de $f$.

$3)\Rightarrow 4)$ Supongamos que $\mathcal{A}=\set{A_\alpha:\alpha\in\Gamma}$ es una familia no vacía de conjuntos no vacíos tales que $A_\alpha\cap A_\beta=\emptyset$ si $\alpha\not=\beta$.

Definamos $f:\bigcup_{\alpha\in\Gamma}A_\alpha\to\Gamma$ por medio de $f(x)=\alpha$ si $x\in A_\alpha$. Podemos describir a $f$ como el siguiente conjunto $f:=\set{(x,\alpha):x\in A_\alpha,\alpha\in\Gamma}\subseteq(\bigcup_{\alpha\in\Gamma}A_\alpha)\times \Gamma$. Nuevamente, lo primero que hay que hacer es verificar que $f$ sea una función. Sean $(a,b),(a,c)\in f$. Luego, $(a,b)=(x,\alpha)$ y $(a,c)=(y,\beta)$ para algunos $x,y\in\bigcup_{\alpha\in \Gamma}A_\alpha$ y $\alpha,\beta\in\Gamma$, tales que $x\in A_\alpha$ y $y\in A_\beta$. Dado que $(a,b)=(x,\alpha)$ y $(a,c)=(y,\beta)$, entonces $a=x=y$ y, en consecuencia, $x\in A_\alpha\cap A_\beta$, lo que muestra que $A_\alpha\cap A_\beta\not=\emptyset$ y, por tanto, $\alpha=\beta$, es decir, $b=\alpha=\beta=c$, lo que muestra que $f$ es una función.

Ciertamente, $f$ es una función suprayectiva, pues si $\alpha\in\Gamma$ es cualquier elemento, entonces, existe $x\in A_\alpha$ pues $A_\alpha\not=\emptyset$, tal que $f(x)=\alpha$, por definición de $f$. Esto muestra que $\alpha$ es la imagen de un elemento en $\bigcup_{\alpha\in \Gamma}A_\alpha$ bajo la función $f$ y, por tanto, $f$ es suprayectiva. Luego, por hipótesis, existe $g:\Gamma\to\bigcup_{\alpha\in\Gamma}A_\alpha$ función inversa derecha de $f$, es decir, $f\circ g=Id_\Gamma$. Sea $B:=g[\Gamma]=\set{g(\alpha):\alpha\in\Gamma}\subseteq\bigcup_{\alpha\in\Gamma}A_\alpha$.

Notemos que para cada $\alpha\in\Gamma$, se tiene que $g(\alpha)\in A_\alpha$. En efecto, si $\alpha\in\Gamma$, entonces $f(g(\alpha))=Id_\Gamma(\alpha)=\alpha$, por lo que $g(\alpha)\in A_\alpha$. Por lo tanto, $\set{g(\alpha)}\subseteq A_\alpha\cap B$ para todo $\alpha\in\Gamma$.

Ahora, si $x\in A_\alpha\cap B$, entonces $x=g(\beta)$ para algún $\beta\in\Gamma$. Luego, $f(x)=f(g(\beta))=Id_\Gamma(\beta)=\beta$. Por otro lado, como $x\in A_\alpha$, también se tiene que $f(x)=\alpha$ y, por consiguiente, $\beta=\alpha$. Así, $x=g(\alpha)$, lo que demuestra que $A_\alpha\cap B=\set{g(\alpha)}$. Por lo tanto, $B$ es subconjunto de $\bigcup_{\alpha\in\Gamma}A_\alpha$ y cumple que $B\cap A_\alpha$ es un conjunto unitario para cada $\alpha\in\Gamma$.

$4)\Rightarrow 5)$ Sea $\set{A_\alpha}_{\alpha\in\Gamma}$ una familia de conjuntos no vacíos. Para cada $\alpha\in\Gamma$ definamos $B_\alpha:=\set{\alpha}\times A_\alpha$. Luego, $\set{B_\alpha:\alpha\in\Gamma}$ es una familia no vacía de conjuntos no vacíos tales que $B_\alpha\cap B_\beta=\emptyset$ si $\alpha\not=\beta$.

Luego, por hipótesis, existe $B\subseteq\bigcup_{\alpha\in\Gamma}B_\alpha$ tal que $B\cap B_{\alpha}$ es un conjunto unitario para cada $\alpha\in \Gamma$. Ahora bien, el único elemento de $B\cap B_\alpha$ es de la forma $(\alpha,a)$ con $a\in A_\alpha$, pues pertenece, en particular, al conjunto $B_\alpha=\set{\alpha}\times A_\alpha=\set{(\alpha,a):a\in A_\alpha}$. Denotemos por $a_\alpha$ al único elemento de $A_\alpha$ tal que $B\cap B_\alpha=\set{(\alpha,a_\alpha)}$. Definamos $f:\Gamma\to\bigcup_{\alpha\in \Gamma}A_\alpha$ por medio de $f(\alpha)=a_\alpha$. Notemos que $f$ puede ser descrita como el conjunto $\set{(\alpha,a_\alpha):\alpha\in\Gamma}$. Luego, para comprobar que $f$ es una función tomemos $(a,b),(a,c)\in f$. Entonces, $(a,b)=(\alpha,a_\alpha)$ y $(a,c)=(\beta,a_\beta)$ para algunos $\alpha,\beta\in\Gamma$ y $a_\alpha\in A_\alpha$ y $a_\beta\in A_\beta$ tales que $(\alpha,a_\alpha)$ y $(\beta,a_\beta)$ son los únicos elementos de $B\cap B_\alpha$ y $B\cap B_\beta$, respectivamente. A partir de las igualdades $(a,b)=(\alpha,a_\alpha)$ y $(a,c)=(\beta,a_\beta)$ se sigue que $a=\alpha=\beta$ y, por tanto, $b=a_\alpha=a_\beta=c$. Esto que muestra $f$ es una función. Finalmente, para cada $\alpha\in\Gamma$, se tiene que $f(\alpha)\in A_\alpha$.

$5)\Rightarrow 6)$ Sea $F:X\to\mathcal{P}(Y)\setminus\set{\emptyset}$ una función.

Consideremos a la familia de conjuntos no vacíos $\mathcal{F}=\set{F(x):x\in X}$. Luego, por hipótesis, existe una función $f:X\to\bigcup\mathcal{F}$ tal que $f(x)\in F(x)$ para cada $x\in X$. Notemos ahora que $\bigcup\mathcal{F}=\bigcup_{x\in X}F(x)\subseteq Y$. Así, $f$ es una función con dominio $X$ y codominio $Y$. Por lo tanto, existe $f:X\to Y$ tal que $f(x)\in F(x)$ para cada $x\in X$.

$6)\Rightarrow 1)$ Sea $X$ un conjunto. Definamos $F:\mathcal{P}(X)\setminus\set{\emptyset}\to\mathcal{P}(X)\setminus\set{\emptyset}$ por medio de $F(B)=B$. Luego, por hipótesis, existe una función $f:\mathcal{P}(X)\setminus\set{\emptyset}\to X$ tal que $f(B)\in F(B)=B$ para todo $B\in\mathcal{P}(X)\setminus\set{\emptyset}$. Por lo tanto, $X$ tiene una función de elección.

$\square$

Una aplicación del axioma de elección a cardinales numerables

Para finalizar esta entrada, enunciaremos y demostraremos un resultado sobre cardinalidades que puede deducirse con el uso del axioma de elección.

Teorema. Sea $\set{A_n:n\in\mathbb{N}}$ una familia de conjuntos ajenos dos a dos tal que $A_n$ es numerable para todo $n\in\mathbb{N}$. Entonces, $\bigcup_{n\in\mathbb{N}}A_n$ es numerable.

Demostración.

Para cada $n\in\mathbb{N}$ sea $B_n:=\set{f\subseteq \mathbb{N}\times A_n:f \ \text{es función biyectiva}}$. Dado que cada $A_n$ es numerable, entonces, por definición, existe una función $f_n:\mathbb{N}\to A_n$ biyectiva para todo $n\in\mathbb{N}$. Así pues, $B_n\not=\emptyset$ para cada $n\in\mathbb{N}$.

Consideremos la colección de conjuntos no vacíos $\set{B_n:n\in\mathbb{N}}$. Por el teorema anterior, el axioma de elección implica que existe una función $F:\mathbb{N}\to\bigcup_{n\in\mathbb{N}}B_n$ tal que $F(n)\in B_n$ para cada $n\in\mathbb{N}$. Definamos $g_n:=F(n)$ para cada $n\in\mathbb{N}$.

Definamos ahora $G:\mathbb{N}\times\mathbb{N}\to\bigcup_{n\in\mathbb{N}}A_n$ por medio de $G(r,s)=g_s(r)$. Veamos que $G$ es una función. Sean $(a,b),(a,c)\in G$. Luego, $(a,b)=((r,s),g_s(r))$ y $(a,c)=((x,y),g_y(x))$ para algunos $(r,s),(x,y)\in\mathbb{N}\times\mathbb{N}$. Se sigue de lo anterior que $a=(r,s)=(x,y)$ y, por tanto, que $r=x$ y $s=y$. Así pues, como $s=y$, entonces $g_s=F(s)=F(y)=g_y$ debido a que $F$ es función. Por otro lado, también tenemos que $b=g_s(r)$ y $c=g_y(x)$, por lo que $b=c$, ya que $r=x$, $g_s=g_y$ y $g_s$ es función. Esta serie de argumentos muestran que $G$ es efectivamente una función.

Ahora, veamos que $G$ es una función biyectiva. Sean $(r,s),(x,y)\in\mathbb{N}\times\mathbb{N}$ tales que $G(r,s)=G(x,y)$. Entonces, $g_s(r)=g_y(x)$. Como $g_s\in B_s$ y $g_y\in B_y$, entonces $g_s(r)\in A_s$ mientras que $g_y(x)\in A_y$ y, consecuentemente, $A_s\cap A_y\not=\emptyset$, lo cual puede ocurrir si y sólo si $A_s=A_y$, es decir, $s=y$. Dado que $g_s(r)=g_s(x)$ y $g_s$ es biyectiva, entonces $r=x$. Esto muestra que $(r,s)=(x,y)$ y, por lo tanto, $G$ es inyectiva.

Finalmente veamos que $G$ es suprayectiva. Sea $a\in\bigcup_{n\in\mathbb{N}}A_n$. Luego, $a\in A_m$ para algún $m\in\mathbb{N}$ y, por consiguiente, existe $b\in\mathbb{N}$ tal que $g_m(b)=a$, ya que $g_m$ es biyectiva. De modo que tomando al elemento $(b,m)\in\mathbb{N}\times\mathbb{N}$ se sigue que $G(b,m)=g_m(b)=a$, lo que muestra que $G$ es suprayectiva.

Por lo tanto, $G$ es una biyección y, en consecuencia, $\mathbb{N}\times\mathbb{N}$ es equipotente a $\bigcup_{n\in\mathbb{N}}A_n$. Luego, como $\mathbb{N}\times\mathbb{N}$ es equipotente a $\mathbb{N}$, se sigue que $\bigcup_{n\in\mathbb{N}}A_n$ es equipotente a $\mathbb{N}$, es decir, $\bigcup_{n\in\mathbb{N}}A_n$ es numerable.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

  1. Demuestra que la unión numerable de conjuntos finitos es un conjunto numerable.
  2. Otro de los pendientes que teníamos en entradas anteriores es la existencia de conjuntos de representantes para relaciones de equivalencia. Ahora lo podemos demostrar. Prueba que si $X$ es un conjunto y $R$ es una relación de equivalencia en $X$, entonces existe un conjunto completo de representantes de la relación $R$.
  3. Demuestra que el axioma de elección es equivalente a la siguiente proposición: para toda relación $R$ existe una función $f$ tal que $dom\ f$ es igual al dominio activo de $R$ y $f\subseteq R$.
  4. Argumenta axiomáticamente que el conjunto $B_n$ de la demostración del último teorema en efecto es un conjunto.

Más adelante…

En la siguiente entrada veremos otras equivalencias del axioma de elección, ahora relacionadas con órdenes parciales. Posteriormente usaremos eso para mostrar que todo conjunto puede ser bien ordenado.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Aritmética cardinal

Por Gabriela Hernández Aguilar

Introducción

En las entradas anteriores hablamos de conjuntos finitos e infinitos. Además, vimos que hay conjuntos infinitos que no son equipotentes entre sí: $\mathbb{N}$ y $\mathcal{\mathbb{N}}$. Ahora hablaremos un poco sobre qué son los cardinales, asumiremos su existencia y daremos una breve introducción a cómo se puede trabajar con ellos mediante aritmética cardinal.

Introducción a ¿qué es un cardinal?

La idea intuitiva detrás de los cardinales es que a cualquier conjunto $X$ se le pueda asignar un conjunto «canónico» $Y$ con la misma cardinalidad que $X$. Si esto es posible, diremos que la cardinalidad de $X$ es $Y$, y lo escribiremos como $|X|=Y$. A $Y$ le llamamos un cardinal. Recuerda que intuitivamente la noción de «ser equipotentes» es parecida a una relación de equivalencia (aunque estrictamente no lo es). Con esta intuición, puedes pensar a los cardinales como un «conjunto de representantes» de esta relación de equivalencia.

Si bien estamos muy lejos de tener algo así, hemos logrado algo de progreso parcial. Si un conjunto $X$ es finito, entonces es equipotente a un único natural $n$ y en ese caso dijimos que su cardinal es $n$, lo cual denotamos como $|X|=n$. Si $X$ es numerable, entonces dijimos que su cardinal es $\mathbb{N}$ y escribimos $|X|=\mathbb{N}$. Ya vimos que $\mathcal{P}(\mathbb{N})$ no es numerable. Si quisiéramos, podríamos decir que el cardinal de cualquier conjunto equipotente a $\mathcal{P}(\mathbb{N})$ es precisamente $\mathcal{P}(\mathbb{N})$, pero esto ya empieza a volverse algo tedioso y no es claro cómo se formaliza.

La formalización de los cardinales queda fuera del alcance de este curso, y depende de la manera en la que se axiomatiza la teoría de los conjuntos. Una manera de hacer esto es introducir a los números ordinales, lo cual queda como invitación a un curso posterior de teoría de los conjuntos. Sin embargo, si asumimos la existencia de los cardinales, podemos platicar un poco de la aritmética cardinal, lo cual haremos a continuación.

Suma de cardinales

Comenzaremos definiendo la suma de dos cardinales. Dicha operación está motivada en la regla de la suma para conjuntos finitos. Recuerda que esta regla dice que si $A$ y $B$ son conjuntos finitos disjuntos con $m$ y $n$ elementos, respectivamente, entonces $|A\cup B|=m+n$.

Definición. Si $\kappa=|A|$, $\lambda=|B|$ y $A\cap B=\emptyset$, definimos \[\kappa+\lambda=|A\cup B|.\]

La definición anterior da por hecho que existen conjuntos ajenos $A$ y $B$ tales que $\kappa=|A|$ y $\lambda=|B|$, lo cual es cierto, pues si hacemos $A_1=A\times\{0\}$ y $B_1=B\times\{1\}$, entonces $\kappa=|A|=|A_1|$, $\lambda=|B|=|B_1|$ y $A_1\cap B_1=\emptyset$.

La definición también supone que $|A\cup B|$ no depende de la elección de $A$ y $B$. Para comprobar que la definición de suma de cardinales está bien definida tenemos que mostrar que en efecto esto es así; esto es, que si $A,A’,B,B’$ son conjuntos tales que $\kappa=|A|=|A’|$, $\lambda=|B|=|B’|$ y $A\cap B=\emptyset=A’\cap B’$, entonces $|A\cup B|=|A’\cup B’|$.

Lema. Si $A,A’,B,B’$ son conjuntos tales que $|A|=|A’|$, $|B|=|B’|$ y $A\cap B=\emptyset=A’\cap B’$, entonces $|A\cup B|=|A’\cup B’|$.

Demostración.

Dado que $|A|=|A’|$ y $|B|=|B’|$, podemos fijar funciones $f:A\to A’$ y $g:B\to B’$ biyectivas. Luego, $f\cup g:A\cup B\to A’\cup B’$ es una función biyectiva, por lo que $|A\cup B|=|A’\cup B’|$.

$\square$

La definición de suma de cardinales no sólo coincide con la suma ordinaria de números en el caso finito, sino que también se preservan algunas propiedades usuales. Por ejemplo, si $A$ y $B$ son conjuntos ajenos tales que $\kappa=|A|$ y $\lambda=|B|$, entonces $\kappa+\lambda=\lambda+\kappa$. En efecto, como $A\cup B=B\cup A$, entonces $|A\cup B|=|B\cup A|$, y la definición de suma de cardinales implica que $\kappa+\lambda=\lambda+\kappa$. Esto muestra que la suma de cardinales es una operación conmutativa.

Por otro lado, si $\kappa$, $\lambda$ y $\mu$ son cardinales, se satisface por la asociatividad de la unión que $\kappa+(\lambda+\mu)=(\kappa+\lambda)+\mu$. Es decir, la suma de cardinales es también una operación asociativa.

También se puede mostrar que si $\kappa$ y $\lambda$ son cardinales, entonces $\kappa\leq\kappa+\lambda$. En efecto, si $A$ y $B$ son conjuntos ajenos tales que $\kappa=|A|$ y $\lambda=|B|$, entonces $f:A\to A\cup B$ definida por medio de $f(a)=a$ (la inclusión de $A$ en $A\cup B$) es una función inyectiva. Esto muestra que $\kappa=|A|\leq|A\cup B|=\kappa+\lambda$, como queríamos.

Asimismo, si $\kappa_1\leq\kappa_2$ y $\lambda_1\leq\lambda_2$ son cardinales, entonces $\kappa_1+\lambda_1\leq\kappa_2+\lambda_2$. ¿Podrás demostrar esto?

Producto de cardinales

Ya que definimos la suma de cardinales y hemos notado que algunas propiedades de esta nueva operación coinciden con las que ya conocíamos sobre la suma de números naturales, podemos definir la multiplicación de cardinales, la cual, como es de esperarse, estará motivada en la multiplicación ya conocida de números naturales.

Definición. Si $A$ y $B$ son conjuntos tales que $\kappa=|A|$ y $\lambda=|B|$, entonces \[\kappa\cdot\lambda=|A\times B|.\]
Así como con la suma, debemos verificar que esta nueva operación está bien definida.

Lema. Si $A,A’,B,B’$ son conjuntos tales que $|A|=|A’|$ y $|B|=|B’|$, entonces $|A\times B|=|A’\times B’|$.

Demostración.

Dado que $|A|=|A’|$ y $|B|=|B’|$, podemos fijar funciones $f:A\to A’$ y $g:B\to B’$ biyectivas. Luego, si definimos $h:A\times B\to A’\times B’$ por medio de $h(a,b)=(f(a),g(b))$, entonces $h$ es biyectiva. De modo que $|A\times B|=|A’\times B’|$.

$\square$

Así, en efecto el producto de cardinales no depende de los conjuntos elegidos.

Algunas propiedades del producto de números naturales se preservan para el producto de cardinales.

Por ejemplo, si $\kappa$ y $\lambda$ son cardinales, entonces $\kappa\cdot \lambda=\lambda\cdot\kappa$. En efecto, si $\kappa=|A|$ y $\lambda=|B|$, entonces $\kappa\cdot\lambda=|A\times B|$, pero, dado que $|A\times B|=|B\times A|$ (ya que $h:A\times B\to B\times A$ definida mediante $h(a,b)=(b,a)$ es una biyección), entonces $\kappa\cdot\lambda=|A\times B|=|B\times A|=\lambda\cdot\kappa$.

De manera similar, se puede mostrar que:

  1. $\kappa\cdot(\lambda\cdot\mu)=(\kappa\cdot\lambda)\cdot\mu$,
  2. $\kappa\cdot(\lambda+\mu)=\kappa\cdot\lambda+\kappa\cdot\mu$

para cualesquiera cardinales $\kappa$, $\lambda$ y $\mu$. Intenta demostrar esto. Tendrás que usar propiedades de la unión y producto cartesiano. Por ejemplo, para el inciso 2 deberás usar que para cualesquiera conjuntos $A,B,C$ se cumple que $A\times(B\cup C)=(A\times B)\cup(A\times C)$.

También hay algunas propiedades de desigualdad de cardinales que involucran al producto. A continuación discutimos algunas brevemente.

Si $\kappa=|A|$ y $\lambda=|B|$, con $B\not=\emptyset$, entonces, definiendo $f:A\to A\times B$ por medio de $f(a)=(a,b_0)$ donde $b_0\in B$ es un elemento fijo, tenemos que $f$ es una función inyectiva y así $\kappa=|A|\leq|A\times B|=\kappa\cdot\lambda$. Esto muestra que para cualesquiera cardinales $\kappa$ y $\lambda$, con $\lambda\not=0$, $\kappa\leq\kappa\cdot\lambda$.

De manera similar se puede mostrar que si $\kappa_1\leq\kappa_2$ y $\lambda_1\leq\lambda_2$, entonces $\kappa_1\cdot\kappa_2\leq\lambda_1\cdot\lambda_2$. Basta tomar conjuntos $A,A’,B,B’$ tales que $\kappa_1=|A|$, $\kappa_2=|A’|$, $\lambda_1=|B|$ y $\lambda_2=|B’|$. Luego, como $\kappa_1\leq\kappa_2$ y $\lambda_1\leq\lambda_2$, podemos fijar funciones inyectivas $f:A\to A’$ y $g:B\to B’$ y podemos definir $h:A\times B\to A’\times B’$ por medio de $h(a,b)=(f(a),g(b))$, la cual resulta ser una función inyectiva. Esto muestra que $\kappa_1\cdot\lambda_1=|A\times B|\leq|A’\times B’|=\kappa_2\cdot\lambda_2$.

Otra propiedad es que al multiplicar un cardinal por un natural, sucede lo que esperamos: el cardinal «se suma la cantidad apropiada de veces». Veamos un pequeño ejemplo. Si $\kappa$ es un cardinal, entonces $\kappa+\kappa=2\cdot\kappa$.

En efecto, si $\kappa=|A|$, entonces $2\cdot\kappa=|\{0,1\}\times A|$, pues $2=|\{0,1\}|$. Luego, notando que $\{0,1\}\times A=(\{0\}\times A)\cup(\{1\}\times A)$, y dado que $\kappa=|\{0\}\times A|=|\{1\}\times A|$ y $\{0\}\times A$ es ajeno a $\{1\}\times A$, se sigue que $2\cdot\kappa=|\{0,1\}\times A|=|(\{0\}\times A)\cup(\{1\}\times B)|=\kappa+\kappa$. Intenta demostrar que para cualquier natural $n$ y cardinal $\kappa$ se cumple que $(n+1)\times \kappa = n\times \kappa + \kappa$.

Finalmente, ¿cómo se comparan la suma y producto de un cardinal consigo mismo? Usando las propiedades ya comentadas, se sigue que para un cardinal $\kappa\geq2$, se cumple \[\kappa+\kappa=2\cdot\kappa\leq\kappa\cdot\kappa.\]

Exponenciación de cardinales

La última operación que introduciremos para cardinales será la exponenciación de cardinales.

Definición. Si $\kappa=|A|$ y $|B|=\lambda$, entonces $\kappa^\lambda=|A^B|$, donde $A^B$ denota al conjunto de las funciones de $B$ en $A$.

Si has realizado los ejercicios de entradas anteriores, notarás que esta definición también generaliza el caso de $A$ y $B$ finitos, en donde $\kappa$ y $\lambda$ son naturales.

Para verificar que esta operación está bien definida tenemos el siguiente lema.

Lema. Si $|A|=|A’|$ y $|B|=|B’|$, entonces $|A^B|=|{A’}^{B’}|$.

Demostración.

Fijemos funciones biyectivas $f:A\to A’$ y $g:B\to B’$ y definamos $F:A^B\to {A’}^{B’}$ como sigue: si $k\in A^B$, sea $F(k)=h$, donde $h:B’\to A’$ está definida mediante $h(g(b))=f(k(b))$ para cada $b\in B$.

$F$ es una función inyectiva, pues, si $k_1,k_2\in A^B$ son tales que $k_1\not=k_2$, entonces existe $b\in B$ de tal modo que $k_1(b)\not=k_2(b)$. Luego, como $f:A\to A’$ es una biyección y $k_1(b)\not=k_2(b)$, se tiene $f(k_1(b))\not=f(k_2(b))$. De modo que si $F(k_1)=h_1$ y $F(k_2)=h_2$, entonces $h_1(g(b))=f(k_1(b))\not=f(k_2(b))=h_2(g(b))$, lo que implica que $h_1\not=h_2$, es decir, $F(k_1)\not=F(k_2)$.

Por otro lado, $F$ es una función suprayectiva, ya que si $h\in {A’}^{B’}$, entonces considerando las funciones $f^{-1}:A’\to A$ (la cual existe por ser $f$ biyectiva) y $k=f^{-1}\circ h\circ g:B\to A$, se tiene que $F(k)=h’$ donde \[h'(g(b))=f(k(b))=f((f^{-1}\circ h\circ g)(b))=(f\circ f^{-1}\circ h\circ g)(b)=h(g(b)),\]
es decir, $h'(g(b))=h(g(b))$ para todo $b\in B$. Como $B’=\{g(b):b\in B\}$, entonces $h'(b’)=h(b’)$ para todo $b’\in B’$, lo cual nos permite concluir que $h’=h$. Esto muestra que $F(k)=h$ y, por consiguientes, $F$ es suprayectiva. Por tanto, $F$ es una biyección y así $|A^B|=|{A’}^{B’}|$.

$\square$

Platiquemos de algunas de las propiedades de exponenciación.

De la definición de exponenciación tenemos que si $\lambda>0$, entonces $\kappa\leq\kappa^{\lambda}$. Esto se debe a que si $\kappa=|A|$ y $\lambda=|B|$, con $B\not=\emptyset$, entonces definiendo $f:A\to A^B$ por medio de $f(a)=g_a$, donde $g_a:B\to A$ está dada por $g_a(b)=a$ para todo $b\in B$, entonces $f$ es una función inyectiva, lo que muestra que $\kappa=|A|\leq|A^B|=\kappa^\lambda$.

Nota que en este último argumento, implícitamente, supusimos $A\not=\emptyset$, ya que las funciones que definimos resultaban ser funciones constantes y dichas constantes eran elementos de $A$; sin embargo, si $A=\emptyset$ no podemos definir una función constante de $B$ en $A$, ya que no hay elementos en $A$ y, de hecho, al ser $B$ no vacío no existen funciones de $B$ en $A$. De modo que si $A=\emptyset$, entonces $A^B=\emptyset$, por lo que $|A|=0=|A^B|$ y así $|A|=|A|^\lambda=|A|^{|B|}=$. En consecuencia, $\kappa\leq\kappa^\lambda$ aún cuando $\kappa=0$.

Por otro lado, si $\kappa>1$, se puede probar que $\lambda\leq\kappa^\lambda$. Para ello supongamos que $A$ y $B$ son conjuntos tales que $\kappa=|A|$ y $\lambda=|B|$ con $\kappa>1$.

Si $\lambda=0$, entonces $B=\emptyset$ y la única función de $B$ en $A$ sería la función vacía, por lo que $\kappa^\lambda=|A^B|=1$. En consecuencia, $\lambda\leq\kappa^\lambda$. Supongamos ahora que $B\not=\emptyset$. Dado que $\kappa>1$, existen al menos dos elementos distintos $a_0,a_1\in A$. Utilizando a estos dos elementos podemos definir algunas funciones de $B$ en $A$ como sigue: dado $b\in B$, definamos $g_b:B\to A$ por medio de $g_b(x)=\left\{ \begin{array}{lcc}
a_0 & si\ x=b \\
a_1 & si\ x\not=b
\end{array}
\right.$. Podemos considerar entonces la función $\varphi:B\to A^B$ cuya regla de correspondencia es $\varphi(b)=g_b$. Dicha función resulta ser inyectiva, pues si $\varphi(b_1)=\varphi(b_2)$, entonces $g_{b_1}=g_{b_2}$ y por tanto $g_{b_1}(x)=g_{b_2}(x)$ para cada $x\in B$. En particular, para $x=b_1$ tenemos que $a_0=g_{b_1}(b_1)=g_{b_2}(b_1)$. De modo que $b_1=b_2$, pues en caso contrario tendríamos que $g_{b_2}(b_1)=a_1$ lo cual es una contradicción, ya que $g_{b_2}(b_1)=a_0$. De esta manera, si $\varphi(b_1)=\varphi(b_2)$, entonces $b_1=b_2$ y así $\varphi$ es inyectiva.

Esta serie de argumentos muestra que $|B|\leq|A^B|$, es decir, $\lambda\leq\kappa^\lambda$.

A continuación enunciaremos un teorema que nos da una propiedad interesante del estilo «ley de los exponentes» para la exponenciación de cardinales.

Teorema. $\kappa^{\lambda+\mu}=\kappa^{\lambda}\kappa^{\mu}$.

Demostración.

Sean $\kappa=|A|$, $\lambda=|B|$, $\mu=|C|$ con $B\cap C=\emptyset$. Para probar que $\kappa^{\lambda+\mu}=\kappa^\lambda\cdot\kappa^\mu$ vamos a exhibir una función biyectiva entre $A^B\times A^C$ y $A^{B\cup C}$.

Definamos $F:A^B\times A^C\to A^{B\cup C}$ por medio de $F(f,g)=f\cup g$. Para cualesquiera $f\in A^B$ y $g\in A^C$, $f\cup g$ es efectivamente una función de $B\cup C$ en $A$, debido a que $dom(f\cup g)=dom(f)\cup dom(g)=B\cup C$ junto al hecho de que $f$ y $g$ son funciones compatibles ya que $dom(f)\cap dom(g)=B\cap C=\emptyset$.

Ahora, $F$ es una función inyectiva, pues si $F(f,g)=F(h,k)$, entonces $f\cup g=h\cup k$; luego, para cada $b\in B$ se tiene que $f(b)=(f\cup g)(b)=(h\cup k)(b)=h(b)$, lo cual implica que $f=h$ y de manera análoga se sigue que $g=k$. Por tanto, $(f,g)=(h,k)$.
Ahora, si $h\in A^{B\cup C}$, podemos considerar las restricciones $h\upharpoonright_B$ y $h\upharpoonright_C$, las cuales resultan ser funciones de $B$ en $A$ y $C$ en $A$, respectivamente. De modo que $(h\upharpoonright_B,h\upharpoonright_C)\in A^{B}\times A^{C}$ y $F(h\upharpoonright_B,h\upharpoonright_C)=h\upharpoonright_B\cup h\upharpoonright_C=h$, lo que muestra que $F$ es suprayectiva. Por lo tanto, $F$ es una biyección y, en consecuencia, $\kappa^{\lambda+\mu}=\kappa^{\lambda}\cdot\kappa^{\mu}$.

$\square$

Para finalizar con esta entrada sobre aritmética cardinal, tenemos el siguiente resultado sobre el cardinal de un conjunto y su potencia.

Teorema. Si $|A|=\kappa$, entonces $|\mathcal{P}(A)|=2^\kappa$.

Demostración.

Vamos a establecer una función biyectiva entre $\mathcal{P}(A)$ y $\{0,1\}^A$. Para cada $B\subseteq A$, definamos $\chi_B:A\to\{0,1\}$ como sigue \[\chi_B(x)=\left\{\begin{array}{lcc} 1 & si\ x\in B \\ 0 & si\ x\notin B. \end{array} \right.\] Definamos entonces $f:\mathcal{P}(A)\to\{0,1\}^A$ como $f(B)=\chi_B$. Luego, si $B\not=C$, entonces existe $x\in B\setminus C$ o existe $x\in C\setminus B$, de modo que existe $x\in A$ tal que $\chi_B(x)=1$ y $\chi_C(x)=0$ o bien $\chi_{B}(x)=0$ y $\chi_C(x)=1$. En cualquier caso se tiene que $\chi_B\not=\chi_C$, ya que no coinciden en la imagen de un mismo elemento.

Este argumento muestra que $f$ es inyectiva.

Por otro lado, si $g\in\{0,1\}^A$, podemos considerar el conjunto $B=\{x\in A:g(x)=1\}$. Se tiene que $B\in\mathcal{P}(A)$ y $\chi_B=g$, ya que si $x\in B$, entonces $\chi_B(x)=1$ y $g(x)=1$; por otro lado, si $x\notin B$, entonces $\chi_B(x)=0$ y $g(x)=0$. Esto demuestra que $f$ es suprayectiva.

Por lo tanto, $f$ es una biyección y, en consecuencia, $|\mathcal{P}(A)|=|\{0,1\}^A|=|\{0,1\}|^{|A|}=2^\kappa$.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

  1. Muestra que $\kappa^0=1$ para todo $\kappa$ y $\kappa^1=\kappa$ para todo $\kappa>0$.
  2. Muestra que $1^\kappa=1$ para todo $\kappa$ y $0^\kappa=0$ para todo $\kappa>0$.
  3. Demuestra que si $\kappa_1\leq\kappa_2$ y $\lambda_1\leq\lambda_2$, entonces $\kappa_1^{\lambda_1}\leq\kappa_2^{\lambda_2}$.
  4. Prueba que $\kappa^\kappa\leq2^{\kappa\cdot\kappa}$.
  5. ¿Existe un conjunto $A$ tal que $\mathcal{P}(A)$ es numerable? Argumenta tu respuesta.

Más adelante…

En la última unidad del curso hablaremos acerca del axioma de elección. Esto ayudará a cerrar algunos pendientes que hemos dejado a lo largo del curso. A grandes rasgos, el axioma de elección nos permitirá construir un conjunto eligiendo un elemento de cada conjunto de una familia de conjuntos. Como consecuencia, veremos que cualquier conjunto puede ser bien ordenado, así como algunas aplicaciones a otras áreas de las matemáticas.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Conjuntos infinitos

Por Gabriela Hernández Aguilar

Introducción

En esta entrada definiremos qué es un conjunto infinito. Después, probaremos algunos resultados sobre la cantidad de elementos que poseen los conjuntos infinitos.

Conjuntos infinitos

Recordemos que para conjuntos $X$ y $Y$ decimos que $|X|\leq |Y|$ si existe una función inyectiva $f:X\to Y$.

Definición. Sea $A$ un conjunto. Decimos que $A$ es un conjunto infinito si no es finito, es decir, para todo $n\in \mathbb{N}$, no existe una función $f:A\to n$ que sea biyectiva.

Ejemplo.

El conjunto de los números naturales no es finito. En efecto, sea $n\in\mathbb{N}$ cualquier elemento. Ahora, si existiera una función biyectiva $f:n\to\mathbb{N}$, en particular, debería existir $B\subseteq n$ tal que $f[B]=s(n)$. Luego, podemos particionar a $n$ como $n=B\cup(n\setminus B)$, por lo que $s(n)=n\cup\set{n}=B\cup(n\setminus B)\cup\set{n}$ y, por la regla de la suma, tendríamos que $|s(n)|=|B|+|n\setminus B|+1$. Dado que $g:B\to s(n)$ definida por medio de $g(m)=f(m)$ es una biyección, entonces $|B|=|s(n)|$. De este modo, $|s(n)|=|s(n)|+|n\setminus B|+1$, por lo que $0=|n\setminus B|+1$ y esto último es imposible, pues el sucesor de cualquier número natural es distinto de $0$. Así pues, no existe función biyectiva de $n$ en $\mathbb{N}$ y, consecuentemente, $\mathbb{N}$ no es finito.

$\square$

A continuación mostraremos que dado cualquier número natural $n$, existe una función inyectiva de $n$ en cualquier conjunto infinito. Veamos la demostración.

Teorema. Si $X$ es infinito, entonces $|X|\geq n$ para cualquier $n\in \mathbb{N}$.

Demostración. (Por inducción sobre $n$).

Base de inducción. Si $n=0$, por vacuidad la función $\emptyset:n\to X$ es inyectiva.

Hipótesis de inducción. Supongamos que $n\leq |X|$ para algún $n\in \mathbb{N}$.

Paso inductivo. Veamos que $n+1\leq|X|$.

Dado que $n\leq|X|$, entonces existe $f:n\to X$ tal que $f$ es inyectiva. Luego, como $X$ es infinito, $f$ no puede ser suprayectiva y por lo tanto existe $y\in X$ tal que $y\notin Im(f)$.

Definimos $g: n+1\to X$ como $g=f\cup \set{(n,y)}$. Resulta que $g$ es inyectiva. En efecto, sean $n_1, n_2\in n+1$ tales que $g(n_1)=g(n_2)$.

Caso 1: Si $n_1, n_2\in n$, entonces $f(n_1)=g(n_1)=g(n_2)=f(n_2)$ y como $f$ es inyectiva se tiene que $n_1=n_2$.

Caso 2: Si $n_1,n_2=n$, entonces $n_1=n_2$.

No puede ocurrir que $n_1\in n$ y $n_2=n$, pues de ser así tendríamos que $g(n_1)=f(n_1)\not=y$ pues $y\notin Im(f)$, mientras que $g(n_2)=y$, lo cual contradice que $g(n_1)=g(n_2)$. Análogamente, no puede ocurrir que $n_2\in n$ y $n_1=n$.

Por lo tanto $g$ es inyectiva y así, $n+1\leq|X|$.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

  • Muestra que si $X$ es un conjunto infinito, entonces para cada subconjunto finito $A$ de $X$, el conjunto $X\setminus A$ es infinito.
  • Sea $A\subseteq\mathbb{N}$ un conjunto finito. Demuestra que existe una función biyectiva entre $\mathbb{N}$ y $\mathbb{N}\setminus A$.
  • Muestra que si $A$ y $B$ son conjuntos tales que $A\cup B$ es infinito, entonces alguno de los conjuntos $A$ o $B$ es infinito.

Más adelante

El primer conjunto infinito que vimos fue el de los números naturales. En la siguiente entrada hablaremos acerca de conjuntos numerables. El primero de ellos será el de los naturales y veremos que existen muchos conjuntos que tienen la misma cantidad de elementos que el conjunto de números naturales.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Conjuntos numerables

Por Gabriela Hernández Aguilar

Introducción

Ahora que hemos desarrollado una herramienta para comparar conjuntos que tienen más elementos que otros y hemos trabajado con conjuntos finitos e infinitos, hablaremos un poco más acerca de estos últimos, en especifico de aquellos que tienen la misma cantidad de elementos que el conjunto de los números naturales. En esta entrada nos enfocaremos principalmente en exhibir un par de ejemplos de conjuntos numerables dando una función biyectiva explícita en cada caso.

Conjuntos numerables

Definición. Sea $A$ un conjunto, decimos que $A$ es numerable si es equipotente a $\mathbb{N}$, es decir, si existe una función biyectiva $f:\mathbb{N}\to A$. De ser así, lo denotaremos con $|A|=|\mathbb{N}|$.

Ejemplo.

En la entrada de equipotencia vimos que existe una función biyectiva entre el conjunto de los números pares y los números naturales, por lo que podemos concluir que $$|\{2k:k\in \mathbb{N}\}|=|\mathbb{N}|.$$

$\square$

Ejemplo.

El conjunto $\mathbb{Z}$ de los números enteros es un conjunto numberable. (Puedes revisar la construcción del conjunto de los números enteros en el siguiente enlace: Álgebra Superior II: Construcción de los enteros y su suma).

Consideremos $f:\mathbb{N}\to \mathbb{Z}$ dada por:

$f(n)= \left\{ \begin{array}{lcc}
             \overline{(k,0)} &   si  & n=2k\ \text{para algún}\ k\in \mathbb{N} \\
             \\ \overline{(0,k+1)} &  si & n=2k+1\ \text{para algún}\ k\in\mathbb{N}
             \end{array}
   \right.$

Resulta que $f$ es biyectiva. En efecto, veamos primero que $f$ es inyectiva.

Sean $x_1, x_2\in \mathbb{N}$ tales que $f(x_1)=f(x_2)$. Tenemos los siguientes casos:

Caso 1. Si $x_1=2k$ y $x_2=2m$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(k,0)}$ y $f(x_2)=\overline{(m,0)}$ y así, $\overline{(k,0)}=\overline{(m,0)}$, por lo que $k+0=m+0$, es decir, $k=m$ y por lo tanto, $x_1=2k=2m=x_2$.

Caso 2. Si $x_1=2k+1$ y $x_2=2m+1$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(0,k+1)}$ y $f(x_2)=\overline{(0,m+1)}$ y así, $\overline{(0,k+1)}=\overline{(0,m+1)}$, por lo que $0+(m+1)=0+(k+1)$ y así $m=k$. Por tanto, $x_1=2k+1=2m+1=x_2$.

El caso en el que $x_1=2k$ y $x_2=2m+1$ no puede ocurrir, pues de lo contrario se tendría que $\overline{(k,0)}=\overline{(0,m+1)}$ por lo que $k+(m+1)=0+0=0$, lo cual es imposible. De manera análoga, no puede ocurrir que $x_1=2m+1$ y $x_2=2k$ para algunos $m,k\in\mathbb{N}$.

Por lo tanto, $f$ es inyectiva.

Ahora veamos que $f$ es suprayectiva. Sea $y\in \mathbb{Z}$, tenemos los siguientes casos:

Caso 1. Si $y\in \mathbb{Z}^+\cup\set{\overline{(0,0)}}$, entonces $y=\overline{(k,0)}$ para algún $k\in\mathbb{N}$. Así, para $x=2k\in\mathbb{N}$ se tiene $f(x)=y$.

Caso 2: Si $y\in \mathbb{Z}^{-}$, entonces $y=\overline{(0,k)}$ para algún $k\in\mathbb{N}\setminus\{0\}$. Luego, existe $k’\in\mathbb{N}$ tal que $s(k’)=k$, es decir, $k’+1=k$. Luego, tomando $x=2k’+1$ se tiene $f(x)=\overline{(0,k’+1)}=\overline{(0,k)}=y$.

Concluimos que $f$ es suprayectiva.

Por lo tanto $f$ es biyectiva y así, $|\mathbb{N}|=|\mathbb{Z}|$.

$\square$

Antes de pasar al siguiente ejemplo vale la pena introducir la siguiente proposición que nos da una condición suficiente para que un conjunto sea numerable.

Proposición. Sea $A$ un conjunto. Si $f:\mathbb{N}\to A$ es una función sobreyectiva, entonces, $A$ es finito o numerable.

Demostración.

Sea $f:\mathbb{N}\to A$ una función sobreyectiva. Supongamos que $A$ no es finito y veamos que entonces debe ser numerable. Para cada $n\in\mathbb{N}$ definamos el conjunto $A_n:=\{k\in\mathbb{N}:f(k)\not=f(m)\ \textnormal{para cada}\ m\leq n\}$. Dado que $A$ no es finito, $A_n\not=\emptyset$ para cada $n\in\mathbb{N}$ y, por tanto, existe $\textnormal{min}(A_n)$. Definamos $g:\mathbb{N}\to\mathbb{N}$ por medio de $g(n)=\textnormal{min}(A_n)$. Por el teorema de recursión, existe una única función $h:\mathbb{N}\to\mathbb{N}$ tal que $h(0)=0$ y $h(n+1)=g(h(n))$ para cada $n\in\mathbb{N}$. Lo que vamos a probar ahora es que $F:=f\circ h:\mathbb{N}\to A$ es una biyección. Para ello notemos primero que $h(n)<h(n+1)$ para cada $n\in\mathbb{N}$. En efecto, si $n\in\mathbb{N}$, entonces, $h(n+1)=g(h(n))=\textnormal{min}(A_{h(n)})$ y así, en particular, $h(n+1)\in A_{h(n)}=\{k\in\mathbb{N}:f(k)\not=f(m)\ \textnormal{para cada}\ m\leq h(n)\}$, por lo que $h(n)<h(n+1)$. Consecuentemente, $h(m)<h(n)$ si y sólo si $m<n$. Esto último trae como consecuencia también que $n\leq h(n)$ para cada $n\in\mathbb{N}$ y se puede dar una prueba de ello por inducción, pues para $n=0$ se tiene que $h(0)=0\geq0$ y si suponemos que $h(n)\geq n$ para algún $n\in\mathbb{N}$, entonces, $h(n+1)>h(n)\geq n$ y así $h(n+1)\geq n+1$, pues de lo contrario tendríamos que $n+1>h(n+1)>n$ lo cual es imposible.
Una vez mencionado esto, veamos que $F$ es inyectiva. Para ello es suficiente mostrar que para cada $n\in\mathbb{N}$, $F(n+1)\not=F(k)$ para cada $k\leq n$. En efecto, si probamos esto último, y $m,n\in\mathbb{N}$ son naturales tales que $F(n)=F(m)$, entonces, $n=m$, ya que de lo contrario podemos suponer que $m<n$ y así $0<n$ por lo que existe un único $k\in\mathbb{N}$ tal que $k+1=n$; luego, $m\leq k$ y dado que $F(n)=F(k+1)\not=F(s)$ para cada $s\leq k$, en particular $F(n)\not=F(m)$ lo cual contradice la hipótesis de que $F(n)=F(m)$. Por tanto $F$ es inyectiva.
Sea pues $n\in\mathbb{N}$ y veamos que $F(n+1)\not=F(k)$ para cada $k\in\mathbb{N}$ tal que $k\leq n$. Por lo que hemos probado, si $k\leq n$, entonces $h(k)\leq h(n)$. Luego, como $h(n+1)=g(h(n))=\textnormal{min}(A_{h(n)})$, entonces, $f(h(n+1))\not=f(k)$ para cada $k\leq h(n)$; en particular, $f(h(n+1))\not=f(h(k))$ para cada $k\leq n$, es decir, $F(n+1)\not=F(k)$ para cada $k\leq n$. Lo anterior, como lo habíamos mencionado, nos permite concluir que $F$ es inyectiva.

Resta mostrar que $F$ es sobreyectiva. Para ello, veamos por inducción que para cada $n\in\mathbb{N}$ existe $k_n\in\mathbb{N}$ tal que $F(k_n)=f(n)$. Si $n=0$, entonces, para $k_0=0$ tenemos que $F(k_0)=f(0)$. Supongamos que para cada $m\leq n$, con $n\in\mathbb{N}$, existe $k_m\in\mathbb{N}$ tal que $F(k_m)=f(m)$. Veamos que para $n+1$ existe $k_{n+1}\in\mathbb{N}$ tal que $F(k_{n+1})=f(n+1)$. Si $f(n+1)=f(m)$ para algún $m\leq n$, entonces, por hipótesis, $f(n+1)=f(m)=F(k_m)$ para algún $k_m\in\mathbb{N}$. Supongamos ahora que $f(n+1)\not=f(k)$ para cada $k\leq n$. Dado que $n+1\leq h(n+1)$, podemos asegurar que el conjunto $B=\{k\in\mathbb{N}:n+1\leq h(k)\}$ es no vacío y, por consiguiente, existe $m=\textnormal{min}(B)$. Más aún, como $n+1\in B$ tenemos que $m\leq n+1$. Si $n+1=h(m)$, entonces, $F(m)=f(h(m))=f(n+1)$. Supongamos ahora que $n+1<h(m)$. Observemos que esta última desigualdad implica que $m\not=0$, de modo que existe $s\in\mathbb{N}$ tal que $s+1=m$ y dado que $m\leq n+1$, se sigue que $s\leq n$. Ahora bien, por la minimalidad de $m$ en el conjunto $B$, debe ocurrir que $h(s)<n+1$ y por ende $h(s)\leq n$. Finalmente, como $n+1<h(m)$ y $h(m)=h(s+1)=g(h(s))=\textnormal{min}(A_{h(s)})$, donde recordemos que $A_{h(s)}=\{k\in\mathbb{N}:f(k)\not=f(t)\ \textnormal{para cada}\ t\leq h(s)\}$, entonces, existe $t\leq h(s)$ tal que $f(t)=f(n+1)$. Esto muestra que existe $t\leq n$, ya que $t\leq h(s)\leq n$, tal que $f(t)=f(n+1)$ pero esto contradice que $f(n+1)\not=f(t)$ para cada $t\leq n$. De modo que necesariamente debe ocurrir que $n+1=h(m)$. Por tanto, para cada $n\in\mathbb{N}$ existe $k_n\in\mathbb{N}$ tal que $F(k_n)=f(n)$. Como $f$ es sobreyectiva se sigue que $F$ es sobreyectiva.
Por lo tanto, $F$ es una función biyectiva y, consecuentemente, $A$ es numerable.

$\square$

La proposición anterior, además de ser una propiedad interesante de los conjuntos numerables, nos ayuda a obtener una gran cantidad de este tipo de conjuntos. Por ejemplo, si $A\subseteq\mathbb{N}$ es cualquier conjunto infinito, entonces, podemos denotar $a_0=\textnormal{min}(A)$ y definir $g:\mathbb{N}\to A$ por medio de la siguiente regla \[g(n)=\left\{\begin{array}{lcc}
n & \textnormal{si}\ n\in A\\
n_0 & \textnormal{si}\ n\notin A
\end{array}
\right.\]

Ciertamente la función anterior es sobreyectiva y, por tanto, debido a que $A$ no es finito, $A$ es numerable. Más adelante daremos otra prueba de este hecho utilizando resultados distintos.
Otro ejemplo interesante de conjunto numerable que podemos obtener con la proposición anterior lo veremos después de la siguientes observaciones.

En los ejercicios de esta entrada mostrarás que el conjunto $\mathbb{N}\times\mathbb{N}$ es numerable dando una función biyectiva explícita entre $\mathbb{N}\times\mathbb{N}$ y $\mathbb{N}$. Utilizando este hecho y que $\mathbb{Z}$ es numerable, lo cual probamos en el ejemplo precedente, podemos concluir que $\mathbb{Z}\times\mathbb{Z}$ es numerable. En efecto, si $f:\mathbb{N}\to\mathbb{Z}$ es la biyección que dimos en el ejemplo anterior, entonces, $F:\mathbb{N}\times\mathbb{N}\to\mathbb{Z}\times\mathbb{Z}$ definida por medio de $F(n,m)=(f(n),f(m))$ es una biyección y, por tanto, $\mathbb{Z}\times\mathbb{Z}$ es numerable. Este último hecho puede ser generalizado, es decir, es posible demostrar que si $A$ y $B$ son conjuntos numerables, entonces, $A\times B$ es numerable. Tendrás oportunidad de demostrar esto en los ejercicios de esta sección. Una vez mencionado esto pasamos al siguiente ejemplo.

Ejemplo.

El conjunto de números racionales $\mathbb{Q}$ es numerable.

Demostración.

Puedes revisar la construcción del conjunto de los números racionales en el siguiente enlace: Álgebra Superior II: Esbozo de construcción de los números racionales y reales. Como podemos observar en dicho enlace, los números racionales se definen como el conjunto de clases de equivalencia de una relación de equivalencia, $\sim$, definida sobre el conjunto $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$, y sus elementos son de la forma $\overline{(a,b)}$ con $a\in\mathbb{Z}$ y $b\in\mathbb{Z}\setminus\{0\}$. Tal relación se define como sigue: diremos que $(a,b)\sim(c,d)$ si y sólo si $a\cdot d=c\cdot b$, donde este último producto es el producto de los números enteros. Así, $\mathbb{Q}=\{\overline{(a,b)}:a\in\mathbb{Z},b\in\mathbb{Z}\setminus\{0\}\}$ donde $\overline{(a,b)}=\{(c,d)\in\mathbb{Z}\times(\mathbb{Z}\setminus\{0\}):(c,d)\sim(a,b)\}$. Observemos que $\mathbb{Q}$ no es finito, pues contiene al conjunto $\{\overline{(z,1)}:z\in\mathbb{Z}\}$, el cual es infinito.

Para mostrar que $\mathbb{Q}$ es numerable definamos $g:\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})\to\mathbb{Q}$ por medio de $g(a,b)=\overline{(a,b)}$. La función $g$ es sobreyectiva. Luego, como $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ es numerable, existe una función biyectiva $h:\mathbb{N}\to\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ y así $g\circ h:\mathbb{N}\to \mathbb{Q}$ es una función sobreyectiva y por tanto como $\mathbb{Q}$ no es finito debe ser numerable.

$\square$

Si bien hemos mostrado que $\mathbb{Q}$ es numerable, no tenemos aún una función biyectiva explícita de $\mathbb{N}$ en $\mathbb{Q}$. Lo que haremos para finalizar con esta entrada es intentar determinar una función biyectiva explícita entre $\mathbb{N}$ y $\mathbb{Q}$.

A continuación añadiremos un par de definiciones que involucran el concepto de multiplicación de naturales que vimos en la entrada Teoría de los Conjuntos I: Producto en los naturales.

Definición. Dados dos naturales $n$ y $m$, diremos que $m$ divide a $n$ si existe $k\in\mathbb{N}$ tal que $m\cdot k=n$ y lo denotaremos por $m\mid n$.

El algoritmo de la división en $\mathbb{Z}$, cuyo enunciado y demostración se puede consultar en el enlace: Álgebra Superior II: Algoritmo de la división en los enteros, nos permite concluir que, para cualesquiera naturales $n$ y $m$, con $m\not=0$, existen únicos naturales $q$ y $r$ tales que $n=mq+r$, con $0\leq r<m$. Este hecho será utilizado más adelante para probar la sobreyectividad de una función que va de $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ a un subconjunto de los números racionales.

Definición. Dados dos naturales $n$ y $m$, no ambos cero, diremos que el natural $d$ es máximo común divisor de $n$ y $m$ si se satisface lo siguiente:

  1. $d\mid n$ y $d\mid m$.
  2. si $d’$ es otro natural tal que $d’\mid n$ y $d’\mid m$, entonces, $d’\leq d$.

Para una prueba de que el máximo común divisor de dos naturales $n$ y $m$, no ambos cero, siempre existe y además es único, puede consultar el enlace Álgebra Superior II: Máximo común divisor. Debido a esto, es posible otorgar una notación al máximo común divisor de dos naturales $n$ y $m$; tal notación será la siguiente, si $d$ es el máximo común divisor de $n$ y $m$, escribiremos $d:=(n,m)$. Diremos además que $n,m\in\mathbb{N}$ son primos relativos si $(n,m)=1$.

Para finalizar con esta serie de definiciones y observaciones añadimos lo siguiente:

Notación. Dado un natural $n$ distinto de $0$, denotaremos por $E_n$ al conjunto $\{m\in\mathbb{N}:m\leq n\ y\ (m,n)=1\}$. Observemos que dicho conjunto es un subconjunto del número natural $s(n)=n+1$ y, por tanto, es finito, es decir, existe un único natural, que denotaremos por $\varphi(n)$, tal que $E_n\sim\varphi(n)$. Además, para cada $n\in\mathbb{N}$, con $n\not=0$, se tiene que $E_n\not=\emptyset$ pues $1\in E_n$, de modo que $\varphi(n)\not=0$.

Ahora bien, debido al buen orden de los números naturales, nos es posible dar una enumeración fija a cada conjunto $E_n$, es decir, podemos escribir $E_n=\{n_1,n_2,\ldots,n_{\varphi(n)}\}$ de tal forma que $n_1<n_2<\ldots<n_{\varphi(n)}$. No está de más recordar cómo se define el orden en $\mathbb{N}$, por lo que agregamos el siguiente enlace para que pueda ser consultado: Teoría de los Conjuntos I: Principio de inducción. Así, siempre que escribamos $E_n=\{n_1,n_2,\ldots,n_{\varphi(n)}\}$ supondremos que se cumple $n_1<n_2<\ldots<n_{\varphi(n)}$.

Una vez mencionado esto pasamos a dar otra prueba de que $\mathbb{Q}$ es numerable.

Ejemplo.

$\mathbb{Q}$ es numerable.

Por comodidad, en lo siguiente denotaremos al elemento $\overline{(a,b)}\in\mathbb{Q}$ simplemente como $\frac{a}{b}$.

Lo que haremos será exhibir una función biyectiva del conjunto $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ en el conjunto $\mathbb{Q}^{+}\cup\{\frac{0}{1}\}$, donde $\mathbb{Q}^{+}$ se puede describir como el conjunto $\mathbb{Q}^{+}=\{\frac{a}{b}:a,b\in\mathbb{Z}^{+}\}$. Si además abusamos de la notación escribiendo $0=\frac{0}{1}$ y $\mathbb{N}\setminus\{0\}=\mathbb{Z}^{+}$ (pues podemos identificar a los números naturales distintos de cero con los enteros positivos mediante la función biyectiva que envía el natural $n$ al entero $\overline{(n,0)}$), podemos escribir $\mathbb{Q}^{+}\cup\{\frac{0}{1}\}=\{\frac{a}{b}:a,b\in\mathbb{N}\setminus\{0\}\}\cup\{0\}$. Además, dado un natural $k\in\mathbb{N}\setminus\{0\}$ escribiremos $k-1$ para denotar al único natural que satisface $s(k-1)=k$.

En los ejercicios de esta sección probarás que para todo natural $n\in\mathbb{N}\setminus\{0,1\}$ existen únicos $k\in\mathbb{N}\setminus\{0,1\}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n=\sum_{t=1}^{k-1}\varphi(t)+i$. Una vez dicho esto definamos $F^{+}:(\mathbb{N}\setminus\set{0})\times\mathbb{N}\to\mathbb{Q}^{+}\cup\{0\}$ por medio de la siguiente regla:

$F^{+}(n,m)= \left\{ \begin{array}{lcc}
             0 &   si  & n=1,\ m=0 \\
\frac{1}{m} &  si & n=1,\ m\not=0 \\
\frac{k}{km+k_i} & si & n=\sum_{t=1}^{k-1}\varphi(t)+i
             \end{array}
   \right.$

donde en el último renglón, $k$ e $i$ son los únicos naturales que satisfacen la igualdad $n=\sum_{t=1}^{k-1}\varphi(t)+i$, con $i\in\{1,\ldots,\varphi(k)\}$, y $k_i$ es el $i-$ésimo elemento que aparece en la enumeración del conjunto $E_{k}=\{k_1,\ldots,k_i,\ldots,k_{\varphi(k)}\}$, enumeración que acordamos satisface $k_1<k_2<\ldots<k_{\varphi(k)}$.
Debido a la únicidad de los naturales $k$ e $i$ para cada $n\in\mathbb{N}\setminus\{0,1\}$, $F^{+}$ es una función bien definida. Veamos que es biyectiva.

Comprobaremos en primer lugar la inyectividad. Sean $(n,m),(n’,m’)\in(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ elementos distintos. Distinguiremos los siguientes casos:

Caso 1. $n=n’$. Dado que $(n,m)\not=(n’,m’)$ pero $n=n’$, entonces, $m\not=m’$. Sin perder generalidad podemos suponer que $m<m’$. Ahora, podemos considerar los siguientes dos subcasos.
Subcaso 1. $n=1$. Si $m=0$, entonces, $0<m’$ y así $F^{+}(n,m)=0$ mientras que $F^{+}(n’,m’)=\frac{1}{m’}$, por lo que $F^{+}(n,m)\not=F^{+}(n’,m’)$. Si ahora $m\not=0$, entonces, $m’\not=0$ y tenemos que $F^{+}(n,m)=\frac{1}{m}$ y $F^{+}(n’,m’)=\frac{1}{m’}$; luego, $\frac{1}{m}\not=\frac{1}{m’}$, pues $m=1\cdot m\not=1\cdot m’=m’$, de modo que $F^{+}(n,m)\not=F^{+}(n’,m’)$.
Subcaso 2. $n>1$. Sean $k\in\mathbb{N}\setminus\{0,1\}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n’=n=\sum_{t=1}^{k-1}\varphi(t)+i$. Luego, $F^{+}(n,m)=\frac{k}{km+k_i}$ y $F^{+}(n’,m’)=\frac{k}{km’+k_i}$ y como $km’+k_i\not=km+k_i$, pues de lo contrario obtendríamos que $m=m’$, se sigue que $k\cdot(km’+k_i)\not=k\cdot(km+k_i)$, es decir, $F^{+}(n,m)=\frac{k}{km+k_i}\not=\frac{k}{km’+k_i}=F^{+}(n’,m’)$.

Caso 2. $n\not=n’$. Sin pérdida de generalidad podemos suponer $n<n’$. Si $n=1$, entonces, o bien $F^{+}(n,m)=0$ o bien $F^{+}(n,m)=\frac{1}{m}$; por otro lado, como $n’>n=1$, entonces podemos elegir $k\in\mathbb{N}\setminus\set{0,1}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n’=\sum_{t=1}^{k-1}\varphi(t)+i$ y así $F^{+}(n’,m’)=\frac{k}{km’+k_i}$. Luego entonces, $F^{+}(n,m)\not=F^{+}(n’,m’)$ ya que claramente $\frac{k}{km’+k_i}\not=0$, pero también $\frac{k}{km’+k_i}\not=\frac{1}{m}$ pues de darse la igualdad se tendría que $m\cdot k=1\cdot(km’+k_i)$, lo cual implicaría que $k$ divide a $k_i$ y eso es imposible, pues $k>1$ y $(k,k_i)=1$.
Si ahora $n>1$, podemos fijar $k’\in\mathbb{N}\setminus\{0,1\}$ y $j\in\{1,\ldots,\varphi(k’)\}$ tales que $n=\sum_{t=1}^{k’-1}\varphi(t)+j$. Luego, suponiendo también, como en el párrafo anterior, $n’=\sum_{t=1}^{k-1}\varphi(t)+i$, tenemos que $F^{+}(n,m)=\frac{k’}{k’m+k’_j}$ y $F^{+}(n’,m’)=\frac{k}{km’+k_i}$. Si $k=k’$, entonces, $j<i$, pues de lo contrario tendríamos que $\sum_{t=1}^{k-1}\varphi(t)+i=n’\leq\sum_{t=1}^{k-1}\varphi(t)+j=\sum_{t=1}^{k’-1}\varphi(t)+j=n$, lo cual es una contradicción; en consecuencia, $k’_j=k_j<k_i$ y, más aún, $\frac{k’}{k’m+k’_j}=\frac{k}{km+k_j}\not=\frac{k}{km’+k_i}$, pues en caso contrario se seguiría que $k\cdot(km’+k_i)=k\cdot(km+k_j)$ y, por tanto, que $km’+k_i=km+k_j$ lo cual es imposible pues se seguiría que, en $\mathbb{Z}$, $k$ divide a $k_i-k_j$ el cual es un entero que satisface $0<k_i-k_j<k$.
Para concluir el caso $2$ supongamos que $k\not=k’$. Dado que $(k’,k’m+k’_j)=1=(k,km’+k_i)$, pues de lo contrario $k’$ no sería primo relativo con $k’_j$ así como $k$ no lo sería con $k_i$, entonces, $\frac{k’}{k’m+k’_j}\not=\frac{k}{km’+k_i}$, es decir, $F^{+}(n,m)\not=F^{+}(n’,m’)$. Esto demuestra que $F^{+}$ es una función inyectiva.

Probemos ahora que $F^{+}$ es sobreyectiva. Sea $\frac{p}{q}\in\mathbb{Q}^{+}\cup\{0\}$. Si $\frac{p}{q}=0$, entonces, $\frac{p}{q}=F^{+}(1,0)$. Si $\frac{p}{q}=\frac{1}{m}$, entonces, $\frac{p}{q}=F^{+}(1,m)$. Supongamos ahora que $\frac{p}{q}\not=0$ y que $\frac{p}{q}\not=\frac{1}{m}$ para cada $m\in\mathbb{N}\setminus\set{0}$. Podemos suponer que $(p,q)=1$. Luego, existen únicos naturales $m$ y $r$ tales que $q=pm+r$ con $0\leq r<p$. Nótese que $r\not=0$, pues en caso contrario se tendría que $p$ divide a $q$, pero como $(p,q)=1$ se seguiría que $p=1$, lo cual contradice que $\frac{p}{q}\not=\frac{1}{m}$ para cada $m\in\mathbb{N}\setminus\set{0}$. Así pues, $1\leq r<p$. Ahora bien, $(r,p)=1$, pues de lo contrario, $p$ y $q=pm+r$ compartirían un factor distinto de $1$; es decir, existiría un natural $k$ mayor a $1$ tal que $k$ divide a $p$ y $q$, lo cual contradice que $(p,q)=1$. Por tanto, $(r,p)=1$ y, en consecuencia, $r\in E_p=\{p_1,\ldots,p_{\varphi(p)}\}$. Sea $i\in\{1,\ldots,\varphi(p)\}$ tal que $r=p_i$. Luego, $F^{+}(\sum_{t=1}^{p-1}\varphi(t)+i,m)=\frac{p}{pm+p_i}=\frac{p}{pm+r}=\frac{p}{q}$. Por tanto, $F^{+}$ es sobreyectiva.

Lo anterior prueba que $F^{+}$ es una biyección de $(\mathbb{N}\setminus\{0\})\times\mathbb{N}$ en $\mathbb{Q}^{+}\cup\{0\}$. Luego, como la función $f:\mathbb{N}\times\mathbb{N}\to(\mathbb{N}\setminus\set{0})\times\mathbb{N}$ definida por medio de $f(n,m)=(s(n),m)$ es una biyección entre estos conjuntos, y existe $g:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ función biyectiva (como lo comprobarás en los ejercicios de esta sección), concluimos que $F^{+}\circ f\circ g:\mathbb{N}\to\mathbb{Q}^{+}\cup\{0\}$ es una biyección de $\mathbb{N}$ en $\mathbb{Q}^{+}$. Finalmente, como $\mathbb{Q}=\mathbb{Q}^{+}\cup\set{0}\cup\mathbb{Q}^{-}$, donde $\mathbb{Q}^{-}$ puede ser descrito por el conjunto $\{\frac{a}{b}:a\in\mathbb{Z}^{-},b\in\mathbb{Z}^{+}\}$, y $\mathbb{Q}^{-}$ es equipotente a $\mathbb{Q}^{+}$, entonces, $\mathbb{Q}$ es la unión ajena de dos conjuntos numerables; luego, como probarás en los ejercicios de esta entrada, se sigue que $\mathbb{Q}$ es numerable. Por tanto, $\mathbb{N}$ es equipotente a $\mathbb{Q}$.

$\square$

Aún cuando la función biyectiva que dimos en el último ejemplo no posee una regla de correspondencia agradable, sí es explícita, aunque resulte todavía complicado en la práctica calcular la imagen de la mayoría de los números naturales bajo dicha función.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

  1. Si un conjunto $A$ es numerable y $x\in A$ es un elemento arbitrario, ¿será cierto que $A\setminus\set{x}$ es también numerable?
  2. Sea $\mathbb{N}_0:=\mathbb{N}\setminus\set{0}$. Muestra que $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}_0$ dada por $f(n,m)=2^n(2m+1)$ es una función biyectiva.
  3. Utilizando el ejercicio anterior, muestra que si $A$ y $B$ son conjuntos numerables, entonces $A\times B$ también es numerable.
  4. Sean $A$ y $B$ conjuntos ajenos y numerables. Muestra que $A\cup B$ es numerable . ¿Y si los conjuntos $A$ y $B$ no son ajenos?
  5. Demuestra que para cada $n\in\mathbb{N}\setminus\set{0,1}$, existen únicos $k\in\mathbb{N}\setminus\{0,1\}$ e $i\in\{1,\ldots,\varphi(k)\}$ tales que $n=\sum_{t=1}^{k-1}\varphi(t)+i$.

Más adelante…

En la siguiente entrada concluiremos el contenido acerca de cardinalidad de conjuntos infinitos. Daremos cierre a esta unidad con el tema de aritmética cardinal.

Entradas relacionadas

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»