Archivo de la etiqueta: axioma de eleccion

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

Por Gabriela Hernández Aguilar

Deja un comentario

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 no vacíos 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.

Vamos a 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.1 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}$. Como $C$ es no vacío, 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$.

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\not=\emptyset$ 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 algunos resultados relacionados a conjuntos numerables 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:\mathbb{N}\to 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 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$

Otra aplicación relevante del axioma de elección relacionada a conjuntos numerables es la siguiente.

Teorema. Si $X$ es un conjunto infinito, entonces $X$ contiene un conjunto numerable.

Demostración.

Sea $X$ un conjunto infinito. Definamos $g:S=\cup_{n\in\mathbb{N}}X^n\to \mathcal{P}(X)$ por medio de $g(h)=X\setminus im(h)$ para cada $h\in\cup_{n\in\mathbb{N}}X^n$, donde $X^n$ denota al conjunto de funciones de $n$ en $X$. Observemos que $g(h)\not=\emptyset$ para cada $h\in \cup_{n\in\mathbb{N}}X^n$, pues $X$ es infinito. Sea $e:\mathcal{P}(X)\setminus\{\emptyset\}\to X$ una función de elección. En la entrada Teoría de los Conjuntos I: Teorema de recursión, se dejó como un ejercicio probar que dado un conjunto $A$ y una función $h:\cup_{n\in\mathbb{N}}A^n\to A$, existe una única función $f:\mathbb{N}\to A$ tal que $f(n)=h(f\upharpoonright_n)$ para cada $n\in\mathbb{N}$. De este modo, para la función $e\circ g:S\to X$ existe una única función $f:\mathbb{N}\to X$ tal que $f(n)=(e\circ g)(f\upharpoonright_n)$ para cada $n\in\mathbb{N}$.

Afirmación. $f$ es una función inyectiva.
En efecto, sea $n\in\mathbb{N}$. Luego, $f(n)=(e\circ g)(f\upharpoonright_{n})=e(g(f\upharpoonright_{n}))=e(X\setminus im(f\upharpoonright_{n}))\in X\setminus im(f\upharpoonright_{n})$. Así pues, $f(n)\notin im(f\upharpoonright_{n})$, es decir, $f(n)\not=f(m)$ para cada $m<n$. Lo anterior nos permite concluir que $f$ es inyectiva. Por lo tanto, $f[\mathbb{N}]\subseteq X$ es un subconjunto numerable.

$\square$

Este último resultado, el cual es una consecuencia del axioma de elección, nos permite responder a una pregunta que aparece en la entrada Teoría de los Conjuntos I: Conjuntos infinitos no numerables., la cual busca determinar si cualquier conjunto infinito es un conjunto infinito según Dedekind. La respuesta es afirmativa. Si $X$ es un conjunto infinito, por el resultado previo, $X$ contiene un conjunto numerable; luego, cualquier conjunto que contenga un conjunto numerable es infinito segun Dedekind.

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$.

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»

  1. También puedes consultar la prueba de este teorema en: Hernández, F. (2019). Teoría de Conjuntos. Una introducción. (2.$^a$ ed.). México: Aportaciones Matemáticas No.13, SMM., pp. 166-167. ↩︎