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:P(A){}A tal que, para todo BP(A){}, se tiene que f(B)B.

Ejemplo.

Sea A={0,1}. Luego, P(A)={,{0},{1},{0,1}}. Si definimos f:P(A){}A por medio f={({0},0),({1},1),({0,1},1)}, entonces f es 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:nX y, además, n0 ya que X es no vacío. Ahora, para cada AX no vacío consideremos su imagen inversa, f1[A]={mn:f(m)A}. Dado que f1[A], entonces existe min(f1[A]). Definamos F:P(X){}X por medio de F(A)=f(min(f1[A])). Luego, F es una función de elección para X.

◻

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 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 AA, se tiene que AB es un conjunto unitario.
  3. Toda función suprayectiva tiene al menos una inversa derecha.
  4. Si {Aα}αΓ es tal que Aα y AαAβ= para cualesquiera α,βΓ con αβ, entonces existe BαΓAα tal que BAα es unitario para cada αΓ.
  5. Si {Aα}αΓ es una famila indizada no vacía de conjuntos no vacíos, entonces existe una función f:ΓαΓAα tal que para cada αΓ, se cumple que f(α)Aα.
  6. Si F:XP(Y){} es una función, entonces existe una función f:XY tal que f(x)F(x) para todo xX.

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)2) Supogamos que el axioma de elección es válido. Sea A una familia no vacía de conjuntos no vacíos ajenos dos a dos.

Sea C=A. Como C es no vacío, podemos fijar f:P(C){}C una función de elección. Notemos que si AA, entonces AC, por lo que AP(C){}. Definamos B={f(A):AA}. Veamos ahora que BA es un conjunto unitario para todo AA.

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

2)3)

Sean A y B conjuntos y f:AB una función suprayectiva. Para cada xB definamos Ax={aA:f(a)=x}. Notemos que para cada xB, se tiene que Ax, pues f es suprayectiva. Además, si xx, entonces AxAx=, ya que si existiera un elemento yAxAx, 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 xx. Así pues, si xx, entonces AxAx=.

Consideremos a la familia de conjuntos A={Ax:xB} la cual consta de conjuntos no vacíos y ajenos dos a dos. Por hipótesis, existe un conjunto C tal que CAx es un conjunto unitario para cada AxA. Para xB, denotemos por ax al único elemento del conjunto CAx. Definamos g:BA por medio de g(x)=ax. Expresando a g como un subconjunto de B×A tenemos que g={(x,ax):xB}. Notemos que g es una función, ya que si (w,v),(w,z)g, entonces (w,v)=(x,ax) y (w,z)=(y,ay) para algunos x,yB. De las iguladades anteriores se sigue que w=x=y y, por tanto, v=ax=ay=z. Por tanto, g es función. Finalmente, veamos que g es inversa derecha de f, es decir, que fg:BB es la función identidad; esto es, fg=IdB.

Sea pues xB un elemento arbitrario. Luego, (fg)(x)=f(g(x))=f(ax)=x, pues axAx. Por lo tanto, fg=IdB, lo que muestra que g es inversa derecha de f.

3)4) Supongamos que A={Aα:αΓ} es una familia no vacía de conjuntos no vacíos tales que AαAβ= si αβ.

Definamos f:αΓAαΓ por medio de f(x)=α si xAα. Podemos describir a f como el siguiente conjunto f:={(x,α):xAα,αΓ}(αΓAα)×Γ. Nuevamente, lo primero que hay que hacer es verificar que f sea una función. Sean (a,b),(a,c)f. Luego, (a,b)=(x,α) y (a,c)=(y,β) para algunos x,yαΓAα y α,βΓ, tales que xAα y yAβ. Dado que (a,b)=(x,α) y (a,c)=(y,β), entonces a=x=y y, en consecuencia, xAαAβ, lo que muestra que AαAβ y, por tanto, α=β, es decir, b=α=β=c, lo que muestra que f es una función.

Ciertamente, f es una función suprayectiva, pues si αΓ es cualquier elemento, entonces, existe xAα pues Aα, tal que f(x)=α, por definición de f. Esto muestra que α es la imagen de un elemento en αΓAα bajo la función f y, por tanto, f es suprayectiva. Luego, por hipótesis, existe g:ΓαΓAα función inversa derecha de f, es decir, fg=IdΓ. Sea B:=g[Γ]={g(α):αΓ}αΓAα.

Notemos que para cada αΓ, se tiene que g(α)Aα. En efecto, si αΓ, entonces f(g(α))=IdΓ(α)=α, por lo que g(α)Aα. Por lo tanto, {g(α)}AαB para todo αΓ.

Ahora, si xAαB, entonces x=g(β) para algún βΓ. Luego, f(x)=f(g(β))=IdΓ(β)=β. Por otro lado, como xAα, también se tiene que f(x)=α y, por consiguiente, β=α. Así, x=g(α), lo que demuestra que AαB={g(α)}. Por lo tanto, B es subconjunto de αΓAα y cumple que BAα es un conjunto unitario para cada αΓ.

4)5) Sea {Aα}αΓ una familia de conjuntos no vacíos. Para cada αΓ definamos Bα:={α}×Aα. Luego, {Bα:αΓ} es una familia no vacía de conjuntos no vacíos tales que BαBβ= si αβ.

Luego, por hipótesis, existe BαΓBα tal que BBα es un conjunto unitario para cada αΓ. Ahora bien, el único elemento de BBα es de la forma (α,a) con aAα, pues pertenece, en particular, al conjunto Bα={α}×Aα={(α,a):aAα}. Denotemos por aα al único elemento de Aα tal que BBα={(α,aα)}. Definamos f:ΓαΓAα por medio de f(α)=aα. Notemos que f puede ser descrita como el conjunto {(α,aα):αΓ}. Luego, para comprobar que f es una función tomemos (a,b),(a,c)f. Entonces, (a,b)=(α,aα) y (a,c)=(β,aβ) para algunos α,βΓ y aαAα y aβAβ tales que (α,aα) y (β,aβ) son los únicos elementos de BBα y BBβ, respectivamente. A partir de las igualdades (a,b)=(α,aα) y (a,c)=(β,aβ) se sigue que a=α=β y, por tanto, b=aα=aβ=c. Esto que muestra f es una función. Finalmente, para cada αΓ, se tiene que f(α)Aα.

5)6) Sea F:XP(Y){} una función.

Consideremos a la familia de conjuntos no vacíos F={F(x):xX}. Luego, por hipótesis, existe una función f:XF tal que f(x)F(x) para cada xX. Notemos ahora que F=xXF(x)Y. Así, f es una función con dominio X y codominio Y. Por lo tanto, existe f:XY tal que f(x)F(x) para cada xX.

6)1) Sea X un conjunto. Definamos F:P(X){}P(X){} por medio de F(B)=B. Luego, por hipótesis, existe una función f:P(X){}X tal que f(B)F(B)=B para todo BP(X){}. Por lo tanto, X tiene una función de elección.

◻

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 {An:nN} una familia de conjuntos ajenos dos a dos tal que An es numerable para todo nN. Entonces, nNAn es numerable.

Demostración.

Para cada nN sea Bn:={f:NAn:f es función biyectiva}. Dado que cada An es numerable, entonces, por definición, existe una función fn:NAn biyectiva para todo nN. Así pues, Bn para cada nN.

Consideremos la colección de conjuntos no vacíos {Bn:nN}. Por el teorema anterior, el axioma de elección implica que existe una función F:NnNBn tal que F(n)Bn para cada nN. Definamos gn:=F(n) para cada nN.

Definamos ahora G:N×NnNAn por medio de G(r,s)=gs(r). Veamos que G es una función biyectiva. Sean (r,s),(x,y)N×N tales que G(r,s)=G(x,y). Entonces, gs(r)=gy(x). Como gsBs y gyBy, entonces gs(r)As mientras que gy(x)Ay y, consecuentemente, AsAy, lo cual puede ocurrir si y sólo si As=Ay, es decir, s=y. Dado que gs(r)=gs(x) y gs 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 anNAn. Luego, aAm para algún mN y, por consiguiente, existe bN tal que gm(b)=a, ya que gm es biyectiva. De modo que tomando al elemento (b,m)N×N se sigue que G(b,m)=gm(b)=a, lo que muestra que G es suprayectiva.

Por lo tanto, G es una biyección y, en consecuencia, N×N es equipotente a nNAn. Luego, como N×N es equipotente a N, se sigue que nNAn es equipotente a N, es decir, nNAn es numerable.

◻

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=nNXnP(X) por medio de g(h)=Xim(h) para cada hnNXn, donde Xn denota al conjunto de funciones de n en X. Observemos que g(h) para cada hnNXn, pues X es infinito. Sea e:P(X){}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:nNAnA, existe una única función f:NA tal que f(n)=h(fn) para cada nN. De este modo, para la función eg:SX existe una única función f:NX tal que f(n)=(eg)(fn) para cada nN.

Afirmación. f es una función inyectiva.
En efecto, sea nN. Luego, f(n)=(eg)(fn)=e(g(fn))=e(Xim(fn))Xim(fn). Así pues, f(n)im(fn), es decir, f(n)f(m) para cada m<n. Lo anterior nos permite concluir que f es inyectiva. Por lo tanto, f[N]X es un subconjunto numerable.

◻

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

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. ↩︎

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.