Archivo de la etiqueta: axioma de elección

Teoría de los conjuntos I: Equivalencias del axioma de elección (parte II)

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada continuaremos trabajando el contenido que vimos en la entrada anterior: Teoría de los conjuntos I: Equivalencias del axioma de elección.

Todo conjunto no vacío puede ser bien ordenado.

El siguiente resultado afirma que cualquier conjunto no vacío puede ser bien ordenado. Para probar esta interesante equivalencia del axioma de elección requerimos de un par de lemas.

Lema. Sea $X$ un conjunto y $\mathcal{B}$ la familia de todos los pares ordenados $(A,R)$ donde $A$ es un subconjunto de $X$ y $R$ es un buen orden para $A$. Definimos en $\mathcal{B}$ la relación $\leq$ como sigue: dados $(A,R),(B,R’)\in\mathcal{B}$ diremos que $(A,R)\leq(B,R’)$ si y sólo si $A\subseteq B$, $R\subseteq R’$ y para todo $x\in A$ y $y\in B\setminus A$ se cumple que $(x,y)\in R’$. Entonces, $\leq$ es una relación de orden en $\mathcal{B}$.

Demostración.

Verifiquemos primero la reflexividad. Sea $(A,R)\in\mathcal{B}$. Luego, $A\subseteq A$, $R\subseteq R$ y, por vacuidad, para todo $x\in A$ y $y\in A\setminus A$ se tiene que $(x,y)\in R$, lo que muestra que $(A,R)\leq(A,R)$. Por tanto, $\leq$ es una relación reflexiva.

Verifiquemos ahora la antisimetría. Si $(A,R)\leq (B,R’)$ y $(B,R’)\leq(A,R)$, entonces, como consecuencia de la definición de $\leq$ tenemos que $A\subseteq B$, $R\subseteq R’$ y para todo $x\in A$ y $y\in B\setminus A$ se tiene que $(x,y)\in R’$; pero también, $B\subseteq A$, $R’\subseteq R$ y para todo $x\in B$ y $y\in A\setminus B$ se tiene que $(x,y)\in R$. En particular tenemos que $A\subseteq B$, $B\subseteq A$, $R\subseteq R’$ y $R’\subseteq R$, lo cual implica que $A=B$ y $R=R’$. Por tanto, $(A,R)=(B,R’)$, lo que muestra que $\leq$ es antisimétrica.

Por último mostraremos que la relación $\leq$ es transitiva. Sean $(A,R_0),(B,R_1),(C,R_2)\in\mathcal{B}$ elementos tales que $(A,R_0)\leq(B,R_1)$ y $(B,R_1)\leq(C,R_2)$. Luego, por definición de la relación $\leq$ tenemos que, $A\subseteq B$, $R_0\subseteq R_1$ y para todo $x\in A$ y $y\in B\setminus A$ se cumple que $(x,y)\in R_1$; asimismo, $B\subseteq C$, $R_1\subseteq R_2$ y para todo $x\in B$ y $y\in C\setminus B$ se cumple que $(x,y)\in R_2$. Así, como $A\subseteq B$ y $B\subseteq C$, entonces $A\subseteq C$ y, también, como $R_0\subseteq R_1$ y $R_1\subseteq R_2$, entonces $R_0\subseteq R_2$. Ahora, sean $x\in A$ y $y\in C\setminus A$ cualesquiera elementos. Si $y\in B$, entonces $x\in A$ y $y\in B\setminus A$, por lo que $(x,y)\in R_1$ y, por ende, $(x,y)\in R_2$. Si $y\notin B$, entonces $y\in C\setminus B$ y dado que $x\in A\subseteq B$, entonces $(x,y)\in R_2$. En cualquier caso $(x,y)\in R_2$, lo que demuestra que $(A,R)\leq(C,R_2)$.

Por lo tanto $\leq$ es una relación de orden en $\mathcal{B}$.

$\square$

Lema. Sea $X$ un conjunto y $\mathcal{B}$ el conjunto de todos los pares ordenados $(A,R)$ tales que $A$ es un subconjunto de $X$ y $R$ es un buen orden para $A$. Entonces, toda cadena en el conjunto ordenado $(\mathcal{B},\leq)$ tiene una cota superior, donde $\leq$ es la relación de orden definida en el lema anterior.

Demostración.

Sea $\mathcal{C}$ una cadena en $\mathcal{B}$. Definamos $f:\mathcal{C}\to\mathcal{P}(X)$ como sigue: si $(A,R)\in\mathcal{C}$, con $A\subseteq X$ y $R$ un buen orden en $A$, entonces $f((A,R))=A$. Ahora, notemos que si $A\subseteq X$ y $R$ es un buen orden en $A$, entonces $R\subseteq A\times A\subseteq X\times X$, es decir, $R$ es también una relación en $X$. Teniendo en cuenta esto definamos $g:\mathcal{C}\to\mathcal{P}(X\times X)$ como sigue: si $(A,R)\in\mathcal{C}$, con $A\subseteq X$ y $R$ un buen orden en $A$, entonces $g((A,R))=R$. Sean $Y_1:=f[\mathcal{C}]$ y $Y_2:=g[\mathcal{C}]$ y definamos $\mathcal{A}=\bigcup Y_1$ y $\mathcal{R}=\bigcup Y_2$.

Lo que haremos será probar que $\mathcal{A}$ es un subconjunto de $X$ y que $\mathcal{R}$ es un buen orden para $\mathcal{A}$, con lo cual tendríamos que $(\mathcal{A},\mathcal{R})\in\mathcal{B}$.

Primero, como $f((A,R))=A\subseteq X$ para cualquier $(A,R)\in\mathcal{C}$, entonces $Y_1=f[\mathcal{C}]$ es una familia de subconjuntos de $X$ y, por tanto, $\mathcal{A}=\bigcup Y_1$ es un subconjunto de $X$. Ahora, veamos que $\mathcal{R}$ es un buen orden en $\mathcal{A}$.

Lo primero que tenemos que mostrar es que $\mathcal{R}$ es efectivamente una relación en $\mathcal{A}$, es decir, que $\mathcal{R}$ es un subconjunto de $\mathcal{A}\times\mathcal{A}$. Sea $u\in\mathcal{R}$ un elemento arbitrario. Luego, $u\in g((A,R))=R$ para algún $(A,R)\in\mathcal{C}$. Dado que $u\in R$ y $R\subseteq A\times A$, entonces $u\in A\times A$. Además, como $(A,R)\in\mathcal{C}$, entonces $A=f((A,R))\in f[\mathcal{C}]$ y, en consecuencia, $A\subseteq\bigcup f[\mathcal{C}]=\mathcal{A}$, por lo que $A\times A\subseteq\mathcal{A}\times\mathcal{A}$. De este modo, como $u\in A\times A$ se sigue que $u\in\mathcal{A}\times\mathcal{A}$. Esto demuestra que $\mathcal{R}\subseteq\mathcal{A}\times\mathcal{A}$, es decir, $\mathcal{R}$ es una relación en $\mathcal{A}$.

Ahora veamos que $\mathcal{R}$ es una relación de orden en $\mathcal{A}$.

Sea $x\in\mathcal{A}$. Luego, $x\in f((A,R))=A$ para algún $(A,R)\in\mathcal{C}$. Como $R$ es un buen orden en $A$, entonces $(x,x)\in R$ y, dado que $R\subseteq\mathcal{R}$, se sigue que $(x,x)\in\mathcal{R}$. Esto prueba que $\mathcal{R}$ es una relación reflexiva.

Ahora, sean $x,y\in\mathcal{A}$ elementos tales que $(x,y)\in\mathcal{R}$ y $(y,x)\in\mathcal{R}$. Luego, $(x,y)\in g((A,R))=R$ y $(y,x)=g((B,R’))=R’$ para algunos $(A,R),(B,R’)\in\mathcal{C}$. Dado que $\mathcal{C}$ es una cadena, entonces $(A,R)\leq(B,R’)$ o $(B,R’)\leq(A,R)$, lo cual implica que $R\subseteq R’$ o $R’\subseteq R$. De modo que $(x,y),(y,x)\in R$ o $(x,y),(y,x)\in R’$. En cualquier caso podemos concluir que $x=y$ ya que tanto $R$ como $R’$ son relaciones de orden. Esto prueba que $\mathcal{R}$ es una relación antisimétrica.

Supongamos que $x,y,z\in\mathcal{A}$ son cualesquiera elementos tales que $(x,y),(y,z)\in\mathcal{R}$. Luego, $(x,y)\in g((A,R))=R$ y $(y,z)\in g((B,R’))=R’$ para algunos $(A,R),(B,R’)\in\mathcal{C}$. Ahora, como $\mathcal{C}$ es una cadena, entonces $(A,R)\leq(B,R’)$ o $(B,R’)\leq(A,R)$, por lo que $R\subseteq R’$ o $R’\subseteq R$. Así, $(x,y),(y,z)\in R$ o $(x,y),(y,z)\in R’$ y, por tanto, $(x,z)\in R$ o $(x,z)\in R’$ pues tanto $R$ como $R’$ son relaciones de orden. En cualquier caso $(x,z)\in\mathcal{R}$, ya que $R,R’\subseteq\mathcal{R}$. Esto prueba que $\mathcal{R}$ es una relación transitiva.

Por lo tanto, $\mathcal{R}$ es una relación de orden en $\mathcal{A}$.

Resta probar que $\mathcal{R}$ es un buen orden en $\mathcal{A}$. Sea pues $D\subseteq\mathcal{A}$ un conjunto no vacío. Luego, como $D\subseteq\mathcal{A}$ y $D\not=\emptyset$, entonces $D\cap f((A,R))=D\cap A\not=\emptyset$ para algún $(A,R)\in\mathcal{C}$. Luego, como $D\cap A\subseteq A$ no vacío, entonces existe el mínimo de $D\cap A$ con respecto a la relación $R$, ya que $R$ es un buen orden en $A$, es decir, existe $a_0\in D\cap A$ tal que $(a_0,x)\in R$ para todo $x\in D\cap A$. Veamos que $a_0$ es el mínimo de $D$ con respecto a la relación $\mathcal{R}$. Sea $x\in D$ cualquier elemento. Si $x\in A$, entonces $(a_0,x)\in R\subseteq\mathcal{R}$. Si ahora $x\notin A$, entonces, como $D\subseteq\mathcal{A}$, existe $(B,R’)\in\mathcal{C}\setminus\set{(A,R)}$ tal que $x\in f((B,R’))=B$. Luego, como $\mathcal{C}$ es una cadena se tiene que $(A,R)\leq(B,R’)$ o $(B,R’)\leq(A,R)$, sin embargo, no puede ocurrir que $(B,R’)\leq(A,R)$ pues de ser así tendríamos que $B\subseteq A$ y, por ende, $x\in A$ lo cual asumimos no ocurre. Así pues, necesariamente, $(A,R)\leq(B,R’)$ y, por consiguiente, $A\subseteq B$, $R\subseteq R’$ y para cualesquiera $a\in A$ y $b\in B\setminus A$ se tiene $(a,b)\in R’$. Debido a que $a_0\in A$ y $x\in B\setminus A$, entonces $(a_0,x)\in R’\subseteq\mathcal{R}$. Por lo tanto, para todo $x\in D$, $(a_0,x)\in\mathcal{R}$, lo que demuestra que $a_0$ es el mínimo de $D$ en la relación $\mathcal{R}$. Consecuentemente, $\mathcal{R}$ es un buen orden para $\mathcal{A}$.

Los argumentos anteriores nos permiten concluir que $(\mathcal{A},\mathcal{R})\in\mathcal{B}$, pues $\mathcal{A}\subseteq X$ y $\mathcal{R}$ es un buen orden para $\mathcal{A}$. Ahora, $(\mathcal{A},\mathcal{R})$ es una cota superior para $\mathcal{C}$. En efecto, si $(A,R)\in\mathcal{C}$ es cualquier elemento, entonces $A=f((A,R))\subseteq\bigcup f[\mathcal{C}]=\mathcal{A}$ y $R=g((A,R))\subseteq\bigcup g[\mathcal{C}]=\mathcal{R}$. Por último, si $x\in A$ y $y\in\mathcal{A}\setminus A$, entonces $y\in f((B,R’))=B$ para algún $(B,R’)\in\mathcal{C}$, pero dado que $\mathcal{C}$ es una cadena, entonces $(A,R)\leq(B,R’)$ o $(B,R’)\leq(A,R)$. Sin embargo, no puede ocurrir que $(B,R’)\leq(A,R)$ pues en ese caso tendríamos, en particular, que $B\subseteq A$ y por ende $y\in A$, lo que contradice la elección de $y$. Así que necesariamente, $(A,R)\leq(B,R’)$. Por consiguietne, $A\subseteq B$, $R\subseteq R’$ y para cualquier $a\in A$ y $b\in B\setminus A$, $(a,b)\in R’$. En consecuencia, $(x,y)\in R’$ y como $R’\subseteq\mathcal{R}$, entonces $(x,y)\in\mathcal{R}$.

Por lo tanto, $A\subseteq\mathcal{A}$, $R\subseteq\mathcal{R}$ y para cualesquiera $x\in A$ y $y\in\mathcal{A}\setminus A$, $(x,y)\in\mathcal{R}$, es decir, $(A,R)\leq(\mathcal{A},\mathcal{R})$. Esto demuestra que $(\mathcal{A},\mathcal{R})$ es una cota superior para $\mathcal{C}$.

$\square$

Los lemas anteriores, en particular el último, nos permitirán mostrar que todo conjunto no vacío puede ser bien ordenado.

Teorema. (del buen orden) Todo conjunto no vacío puede ser bien ordenado.

Demostración.

Sea $X$ un conjunto no vacío. Sea $\mathcal{B}$ el conjunto de todos los pares ordenados $(A,R)$ tales que $A\subseteq X$ y $R$ es un buen orden para $A$. Por uno de los lemas anteriores tenemos que $(\mathcal{B},\leq)$ es un conjunto ordenado, donde $\leq$ es la relación definida como $(A,R)\leq(B,R’)$ si y sólo si $A\subseteq B$, $R\subseteq R’$ y para todo $x\in A$ y $y\in B\setminus A$, $(x,y)\in R’$.

Antes de continuar veamos que $\mathcal{B}$ es no vacío. Como $X\not=\emptyset$, entonces existe $a\in X$. Luego, $R=\set{(a,a)}$ es un buen orden para $\set{a}$. Por tanto, $(\set{a},\set{(a,a)})\in\mathcal{B}$ y así $\mathcal{B}$ es no vacío.

Ahora, por el último lema probado, toda cadena en $\mathcal{B}$ está acotada superiormente y, como $\mathcal{B}$ es no vacío, podemos aplicar el lema de Kuratowski-Zorn y concluir que $\mathcal{B}$ tiene un elemento maximal. Sea $(A,R)$ elemento maximal de $\mathcal{B}$. Lo que probaremos es que $A=X$.

Si $X\not=A$, entonces existe $x\in X\setminus A$. Luego, definiendo $B=A\cup\set{x}$ y $R’=R\cup\set{(a,x):a\in A}\cup\set{(x,x)}$ tenemos que $R´$ es un buen orden para $B$. En efecto, primero probaremos que $R’$ es una relación de orden en $B$.

Si $u\in R’$, entonces $u\in R$ o $u\in\set{(a,x):a\in A}$ o $u=(x,x)$. Luego, como $A\subseteq B$ y $R\subseteq A\times A$, entonces $u\in A\times A\subseteq B\times B$ o $u=(a,x)\in A\times B\subseteq B\times B$ para algún $a\in A$ o $u=(x,x)\in B\times B$. En cualquier caso $u\in B\times B$ y, por tanto, $R’\subseteq B\times B$, lo que muestra que $R’$ es una relación en $B$.

Ahora, si $b\in B$, entonces $b\in A$ o $b=x$. Si $b\in A$, entonces $(b,b)\in R$ por ser $R$ una relación de orden en $A$ y, por tanto, $(b,b)\in R’$ pues $R\subseteq R’$. Si $b=x$, entonces $(b,b)\in R’$, por definicipon de $R’$. En cualquier caso se cumple que $(b,b)\in R’$, lo que muestra que $R’$ es una relación reflexiva.

Por otro lado, si $c,b\in B$ son tales que $(c,b)\in R’$ y $(b,c)\in R’$, entonces tenemos algunos casos:

Caso 1. $(c,b)\in R$ y $(b,c)\in R$. Luego, por ser $R$ una relación de orden se cumple que $R$ es antisimétrica, por lo que $c=b$.

Caso 2. $(c,b)\in R$ y $(b,c)\in\set{(a,x):a\in A}$. Luego, $(b,c)=(a,x)$ para algún $a\in A$ y, como $(c,b)\in R\subseteq A\times A$, entonces $(c,b)=(a_1,a_2)$ para algunos $a_1,a_2\in A$. De lo anterior se sigue que $c=a_1\in A$ pero también que $c=x\notin A$ y esto es una contradicción. Así el caso 2 no puede ocurrir.

Caso 3. $(c,b)\in R$ y $(b,c)\in\set{(x,x)}$. Este caso tampoco puede darse por las razones dadas en el caso 2.

Caso 4. $(c,b)\in\set{(a,x):a\in A}$ y $(b,c)\in\set{(a,x):a\in A}$. Luego, $(c,b)=(a_1,x)$ y $(b,c)=(a_2,x)$ para algunos $a_1,a_2\in A$. De esto se sigue que $c=a_1\in A$ y $c=x\notin A$ lo cual es una contradicción. Por lo tanto, el caso 5 tampoco pede darse.

Caso 5. $(c,b)\in\set{(a,x):a\in A}$ y $(b,c)\in\set{(x,x)}$. Luego, $(c,b)=(a_1,x)$ para algún $a_1\in A$ y $(c,b)=(x,x)$, por lo que $c=a_1\in A$ y $c=x\notin A$ lo cual es una contradicción. Por tanto, el caso 5 tampoco puede darse.

Caso 6. $(c,b)\in\set{(x,x)}$ y $(b,c)\in\set{(x,x)}$. En este caso se tiene que $b=x=c$.

Los 6 casos anteriores son las únicas posibilidades y, por tanto, concluimos que $b=c$. Esto muestra que $R’$ es una relación antisimétrica.

Ahora, sean $b,c,d\in B$ tales que $(b,c)\in R’$ y $(c,d)\in R’$. Luego, tenemos los siguientes casos:

Caso 1. $(b,c),(c,d)\in R$. En este caso se sigue que $(b,d)\in R\subseteq R’$ pues $R$ es transitiva.

Caso 2. $(b,c)\in R$ y $(c,d)\in\set{(a,x):a\in A}$. Luego, como $(b,c)\in R\subseteq A\times A$, entonces $b\in A$ y, por tanto, $(b,x)\in R’$. Ahora, como $(c,d)\in\set{(a,x):a\in A}$, entonces $d=x$ y, por tanto, $(b,d)\in R’$.

Caso 3. $(b,c)\in R$ y $(c,d)\in\set{(x,x)}$. Así como en el caso 2 se sigue que $(b,d)\in R’$.

Caso 4. $(b,c),(c,d)\in\set{(a,x):a\in A}$. En este caso se sigue que $c=d=x$ y, por tanto, $(b,c)=(b,d)\in R’$.

Caso 5. $(b,c)\in\set{(a,x):a\in A}$ y $(c,d)\in\set{(x,x)}$. Así como en el caso 3 se sigue que $c=d=x$ y, por tanto, que $(b,d)\in R’$.

Caso 6. $(b,c),(c,d)\in\set{(x,x)}$. Se sigue inmediatamente que $b=c=d=x$ y, por tanto, $(b,d)\in R’$.

Estos son los únicos casos posibles, pues no pueden ocurrir los siguientes casos:

Caso i. $(c,d)\in R$ y $(b,c)\in\set{(a,x):a\in A}$. En este caso se tendría que $c=x$ y que $c\in A$, lo cual no ocurre por la elección de $x$.

Caso ii. $(c,d)\in R$ y $(b,c)\in\set{(x,x)}$. Lo mismo que en el caso i.

Caso iii. $(c,d)\in\set{(a,x):a\in A}$ y $(b,c)\in\set{(x,x)}$. Lo mismo que en los casos i y ii.

En los únicos casos posibles se concluye que $(b,d)\in R’$, lo que muestra que $R’$ es una relación transitiva.

Por lo tanto $R’$ es una relación de orden en $B$. Ahora, sea $D\subseteq B$ no vacío. Si $D\cap A\not=\emptyset$, entonces $D\cap A$ tiene un elemento mínimo en $A$ respecto a la relación de orden $R$, es decir, existe $a_0\in D\cap A$ tal que $(a_0,a)\in R$ para todo $a\in D\cap A$. Luego, si $d\in D$ es cualquier elemento, entonces $d\in A$ o $d=x$. Si $d\in A$, entonces $(a_0,d)\in R\subseteq R’$ y, si $d=x$, entonces $(a_0,d)\in R’$ por definición de $R’$. Lo que demuestra que $a_0$ es el mínimo de $D$ con respecto a la relación de orden $R’$. Si ahora $D\cap A=\emptyset$, entonces, necesariamente, $D=\set{x}$ y, ciertamente, $D$ tiene mínimo, el cual es $x$. Por lo tanto, cualquier subconjunto no vacío de $B$ tiene elemento mínimo con respecto a la relación $R’$. Lo que muestra que $R’$ es un buen orden para $B$.

Luego, entonces $(B,R’)\in\mathcal{B}$. Dado que $A\subseteq B$, $R\subseteq R’$ y para cualquier $a\in A$ y $b\in B\setminus A=\set{x}$ se tiene que $(a,b)\in R’$, se sigue que $(A,R)\leq(B,R’)$ y, sin embargo, $(A,R)\not=(B,R’)$, lo cual contradice la maximalidad de $(A,R)$ en $\mathcal{B}$.

Concluimos entonces que $A=X$ y, por tanto, $R$ es un buen orden para $X$. Por lo tanto, $X$ puede ser bien ordenado.

$\square$

Para culminar esta sección mostraremos que el teorema del buen orden implica el axioma de elección.

Teorema. El teorema del buen orden implica el axioma de elección.

Demostración.

Sea $X$ un conjunto no vacío. Luego, por el teorema del buen orden, existe una relación $R$ en $X$ que es un buen orden en $X$. Definamos $e:\mathcal{P}(X)\setminus\set{\emptyset}\to X$ por medio de $e(B)=\min_R(B)$, donde $\min_R(B)$ denota al elemento mínimo del subconjunto no vacío $B$ de $A$ con respecto a la relación $R$. Dado que, por definición, el mínimo de un conjunto pertenece a dicho conjunto, concluimos que $e(B)\in B$ para todo $B\in\mathcal{P}(X)\setminus\set{\emptyset}$. Lo que demuestra que $X$ tiene una función de elección.

$\square$

Podemos enunciar esta serie de resultados como el siguiente:

Teorema. Son equivalentes:

  1. El axioma de elección.
  2. El lema de Tukey-Teichmüller.
  3. Principio maximal de Hausdorff.
  4. El lema de Kuratowski-Zorn.
  5. El teorema del buen orden.

Con esto damos por terminada la sección sobre algunas de las equivalencias más importantes del axioma de elección.

Tarea moral

  • Sea $(X,\leq)$ un conjunto parcialmente ordenado en el que cualquier cadena tiene una cota superior. Muestre que para cada $a\in X$ existe un elemento $\leq-$maximal $x\in X$ tal que $a\leq x$.
  • Sea $(L,\leq)$ un conjunto linealmente ordenado. Pruebe que existe un conjunto $W\subseteq L$ tal que $\leq$ es un buen orden para $W$ y tal que para cada $x\in L$ existe $y\in W$ tal que $x\leq y$.
  • Sea $X$ cualquier conjunto infinito. Pruebe que $X$ puede ser bien ordenado de tal forma que $X$ no tenga máximo. Pruebe también que $X$ puede ser bien ordenado de tal forma que tenga un máximo.

Más adelante…

En la siguiente y última entrada veremos una aplicación relevante del axioma de elección, de hecho es una equivalencia más, pero es un resultado particularmente atractivo ya que interviene en un rama muy importante de las matemáticas: el Álgebra lineal.

Enlaces

Teoría de los conjuntos I: Equivalencias del axioma de elección

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En la sección anterior vimos algunas equivalencias del axioma de elección. En esta nueva sección veremos algunas otras equivalencias del mismo axioma, pero éstas en particular 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 en esta sección, es por ello que es importante tratarlas.
Antes de comenzar con las equivalencias, necesitamos de algunas definiciones.

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$

Para comenzar con una de las primeras equivalencias del axioma de elección necesitamos del siguiente:

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$

Para probar el siguiente teorema debemos asumir que el axioma de elección se cumple.

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 sección 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 bien $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(C)$, pues $A\subset f(A)$. 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 contradice el hecho de que $f(M)\subseteq M$.

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$

A continuación probaremos un resultado que se obtiene rápidamente al aplicar el lema de Tukey-Teichmüller.

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

Demostración.

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$

A continuación enunciaremos y demostraremos una de las versiones más usadas del axioma de elección, el conocido lema de Zorn y para ello utilizaremos 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

  • Prueba que la intersección de un sistema de familias $f-$inductivas es una familia $f-$inductiva.
  • 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$).

Más adelante…

En la siguiente entrada comenzaremos probando un resultado el cual es una de las consecuencias más impresionantes del axioma de elección y, para muchos matemáticos, un resultado difícil de aceptar. El resultado que enunciaremos afirma que cualquier conjunto no vacío puede ser bien ordenado, sin embargo, la prueba no menciona algo referente a la construcción de un buen orden, simplemente nos muestra que en el conjunto de todas las relaciones de un conjunto no vacío hay al menos una que es un buen orden para dicho conjunto.

Enlaces