Introducción
En esta sección 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.
Concepto
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\}$, $f(B)\in B$.
Veamos el siguiente:
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$
Axioma de elección. Todo conjunto no vacío tiene una función de elección.
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$
Daremos a continuación una serie de equivalencias del axioma de elección.
Teorema. Las siguientes proposiciones son equivalentes:
- El axioma de elección.
- 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}$, $A\cap B$ es un conjunto unitario.
- Toda función sobreyectiva tiene una inversa derecha.
- Si $\set{A_\alpha:\alpha\in\Gamma}$ es tal que $A_\alpha\not= \emptyset$, $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$.
- Si $\set{A_\alpha}_{\alpha\in \Gamma}$ es una famila indizada 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$, $f(\alpha)\in A_\alpha$.
- 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$.
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}$, así que $A\in\mathcal{P}(C)\setminus\set{\emptyset}$ para todo $A\in\mathcal{A}$. 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 pues $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 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’)$ para algún $A’\in\mathcal{A}$. Luego, $x\in A\cap A’$, ya que $x\in A$ porque así fue elegido y $x=f(A’)\in A’$ debido a que $f$ es función de elección en $C$. En consecuencia, $A=A’$ pues los elementos 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 sobreyectiva. Para cada $x\in B$ definamos $A_x=\set{a\in A:f(a)=x}$. Note que para cada $x\in B$, $A_x\not=\emptyset$, pues $f$ es sobreyectiva, es decir, para cada $x\in B$ existe $a\in A$ tal que $f(a)=x$. 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$ y, por definición, debe tenerse que $f(a_x)=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 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 sobreyectiva, 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 sobreyectiva. 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$, $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$, ya que si $g(\alpha)\in A_\beta$ para algún $\beta\in\Gamma\setminus\set{\alpha}$, entonces, por definición de $f$, se tendría que $f(g(\alpha))=\beta$, lo cual es una contradicción. Por lo tanto, $g(\alpha)\in A_\alpha$ para todo $\alpha\in\Gamma$. 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 tanto, existe $B\subseteq\bigcup_{\alpha\in\Gamma}A_\alpha$ tal 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$. Note 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$. Lo que muestra $f$ es una función. Finalmente, para cada $\alpha\in\Gamma$, $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$. Note ahora que $\bigcup\mathcal{F}=\bigcup_{x\in X}F(x)\subseteq Y$. Por lo que $f$ es una función con dominio $X$ y codominio $Y$. Así, 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)$ para todo $B\in\mathcal{P}(X)\setminus\set{\emptyset}$, es decir, existe $f:\mathcal{P}(X)\setminus\set{\emptyset}\to X$ tal que $f(B)\in B$ para todo $B\in\mathcal{P}(X)\setminus\set{\emptyset}$. Por lo tanto, $X$ tiene una función de elección.
$\square$
Para finalizar con esta sección 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}$. Denotemos, para cada $n\in\mathbb{N}$, como $g_n:=F(n)$, la cual es una función biyectiva de $\mathbb{N}$ en $A_n$, pues $g_n\in B_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 tanto, $G$ es inyectiva.
Finalmente veamos que $G$ es sobreyectiva. 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 sobreyectiva.
Por lo tanto, $G$ es una biyeccció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.
- Demuestra que la unión numerable de conjuntos numerables es un conjunto numerable.
- Demuestra 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$.
- 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=dom\ R$ y $f\subseteq R$.
Más adelante
En la siguiente entrada veremos algunas de las equivalencias del axioma de elección junto con la prueba de que en efecto, son equivalentes.
Enlaces
Entrada anterior: Teoría de los Conjuntos I: Aritmética cardinal
Siguiente entrada: Equivalencias del axioma de elección.