Archivo de la etiqueta: teoría de conjuntos

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: Una pequeña aplicación del Axioma de elección.

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción.

Lo que haremos en esta última entrada es utilizar el axioma de elección para probar un resultado muy conocido en Álgebra lineal, específicamente, el hecho de que todo espacio vectorial tiene una base. Para comprender algunos de los términos que utilizaremos en esta sección puedes consultar el curso de https://blog.nekomath.com/al1/

Teorema. Todo espacio vectorial tiene una base.

Demostración.

Sea $V$ un espacio vectorial sobre un campo $K$. Lo que queremos mostrar es que existe un subconjunto $S$ de $V$ que genera a $V$ y que es linealmente independiente.

Si $V=\set{0}$, entonces $\emptyset$ es una base para $V$. Supongamos ahora que $V$ tiene al menos dos vectores distintos. Sea $\mathcal{F}=\set{S\subseteq V:S\ \textnormal{es un conjunto linealmente independiente}}$. Notemos que $\mathcal{F}$ es no vacío. En efecto, sea $v\in V$ un elemento distinto del vector cero. Luego, $\set{v}$ es linealmente independiente, por lo que $\set{v}\in\mathcal{F}$.

Lo que haremos ahora es probar que $\mathcal{F}$ es una familia de conjuntos de carácter finito. Sea $A$ un conjunto tal que $A\in\mathcal{F}$. Luego, $A$ es linealmente independiente y, por tanto, cualquier subconjunto de $A$ es linealmente independiente, en particular todos los subconjuntos finitos de $A$ son linealmente independientes. En consecuencia, cualquier subconjunto finito de $A$ pertence a $\mathcal{F}$. Ahora, sea $A$ un conjunto tal que todo subconjunto finito de $A$ pertenece a $\mathcal{F}$. Si $a\in A$, entonces $\set{a}\in\mathcal{F}$, por lo que $\set{a}$ es un subconjunto de $V$ linealmente independiente. En particular $a\in V$ y, por tanto, $A\subseteq V$. Ahora, sean $a_1,a_2,\ldots,a_n\in A$ cualesquiera elementos y $\alpha_1,\alpha_2,\ldots,\alpha_n$ elementos en $K$ tales que \[\alpha_1a_1+\alpha_2a_2+\cdots+\alpha_na_n=0.\]Luego, como $A_0=\set{a_1,a_2,\ldots,a_n}$ es un subconjunto finito de $A$, entonces $A_0\in\mathcal{F}$, es decir, $A_0$ es un subconjunto de $V$ linealmente independiente y, por tanto, los escalares $\alpha_1,\alpha_2,\ldots,\alpha_n$ deben ser todos $0$, ya que al ser $a_1,a_2,\ldots,a_n$ vectores linealmente independientes, la única combinación lineal de estos vectores que da como resultado al vector $0$ es la combinación lineal trivial, la cual está dada por $0a_1+0a_2+\cdots+0a_n=0$. Así pues, como los elementos $a_1,a_2,\ldots,a_n$ fueron arbitrarios en $A$ concluimos que $A$ es linealmente independiente. Por tanto, $A\in\mathcal{F}$. Esto demuestra que $\mathcal{F}$ es una familia de conjuntos de carácter finito.

Ahora, por el axioma de elección toda familia no vacía de carácter finito tiene un elemento $\subseteq-$maximal. Sea $S$ un elemento $\subseteq-$maximal en $\mathcal{F}$. Resulta que $S$ es una base para $V$. En efecto y, como $S$ es linealmente independiente, sólo basta probar que $S$ genera a $V$.

Sea $v\in V$ cualquier elemento. Si $v$ no es un elemento en el subespacio generado por $S$, entonces $S\cup\set{v}$ sería un subconjunto linealmente independiente que contiene propiamente a $S$, lo cual contradice la maximalidad de $S$ con respecto a la contención en $\mathcal{F}$. Así pues, $v$ debe ser un vector en el subespacio generado por $S$, lo que muestra que $S$ genera a $V$ y, por tanto, $S$ es una base para $V$.

$\square$

Tarea moral

  • Sea $V$ un espacio vectorial sobre un campo $K$. Muestra que todo conjunto linealmente independiente está contenido en una base de $V$.
  • Sea $V$ un espacio vectorial. Muestra que si $S$ es un subconjunto generador de $V$, entonces existe $\beta\subseteq S$ tal que $\beta$ es una base para $V$.
  • Sea $V$ un espacio vectorial con base $\beta$. Si $S$ es un conjunto linealmente independiente, muestra que existe un subconjunto $S_1$ de $\beta$ tal que $S\cup S_1$ es una base para $V$.

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

Por Gabriela Hernández Aguilar

Deja un comentario

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:

  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}$, $A\cap B$ es un conjunto unitario.
  3. Toda función sobreyectiva tiene una inversa derecha.
  4. 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$.
  5. 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$.
  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$.

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

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

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta sección definiremos operaciones aritméticas entre números cardinales y analizaremos algunas de sus propiedades.

Suma de cardinales

Comenzaremos definiendo la suma de dos cardinales. Dicha operación está motivada en conjuntos finitos; esto es, si $A$ y $B$ son conjuntos finitos con $n$ y $m$ elementos, respectivamente, tales que $A\cap B=\emptyset$, entonces $|A\cup B|=n+m$.

Definición: Si $|A|=\kappa$, $|B|=\lambda$ 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_1|$, $\lambda=|B_1|$ y $A_1\cap B_1=\emptyset$.

Para comprobar que la definición de suma de cardinales está bien definida tenemos que mostrar que dicha definición no depende de los conjuntos $A$ y $B$ elegidos; 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 números cardinales es una operación conmutativa.

Por otro lado, si $\kappa$, $\lambda$ y $\mu$ son números cardinales, se satisface que $\kappa+(\lambda+\mu)=(\kappa+\lambda)+\mu$, es decir, la suma de números 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$ es una función inyectiva. Lo que muestra que $\kappa=|A|\leq|A\cup B|=\kappa+\lambda$.

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

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 números 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 $|A|=\kappa$ y $|B|=\lambda$, 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$

El lema anterior muestra que la definición de multiplicación de números cardinales está bien definida, pues no depende de los conjuntos elegidos.

Algunas propiedades de la multiplicación de números naturales se preservan para la multiplicación de números cardinales.

Por ejemplo, si $\kappa$ y $\lambda$ son números 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 números cardinales $\kappa$, $\lambda$ y $\mu$.

Para probar el inciso $2$ basta mostrar que para conjuntos $A$, $B$ y $C$ se cumple que $A\times(B\cup C)=(A\times B)\cup(A\times C)$.

Algunas propiedades sobre desigualdades con números cardinales que involucran la operación multiplicación, son las siguientes:

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$. Lo que muestra que para cualesquiera números 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. Lo que muestra que $\kappa_1\cdot\lambda_1=|A\times B|\leq|A’\times B’|=\kappa_2\cdot\lambda_2$.

Una propiedad más: si $\kappa$ es un número 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$.

Juntando esta última propiedad con el hecho de que $\kappa_1\cdot\lambda_1\leq\kappa_2\cdot\lambda_2$ siempre que $\kappa_1\leq\kappa_2$ y $\lambda_1\leq\lambda_2$, se sigue que para un número cardinal $\kappa\geq2$,\[\kappa+\kappa=2\cdot\kappa\leq\kappa\cdot\kappa.\]

La última operación que introduciremos para números 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$.

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 sobreyectiva, 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 sobreyectiva. Por tanto, $F$ es una biyección y así $|A^B|=|{A’}^{B’}|$.

$\square$

De la definición de exponenciación tenemos que $\kappa\leq\kappa^{\lambda},\ \textnormal{si}\ \lambda>0,$
ya 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$. Note 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|^{|B|}=|A|^\lambda$. 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 sobre 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$. Note que 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 sobreyectiva. Por lo tanto, $F$ es una biyección y, en consecuencia, $\kappa^{\lambda+\mu}=\kappa^{\lambda}\cdot\kappa^{\mu}$.

$\square$

Para finalizar con la sección 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\}$. Note 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 sobreyectiva.

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

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

Más adelante…

En la siguiente entrada hablaremos acerca del axioma de elección.

Enlaces

Teoría de los Conjuntos I: Conjuntos infinitos

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta sección comenzaremos definiendo que es un conjunto infinito para posteriormente probar resultados acerca de la cantidad de elementos que estos poseen, es decir, la cardinalidad de dichos conjuntos.

Concepto previo

Definición: Sean $X$ y $Y$ conjuntos. Decimos que $|X|\leq|Y|$ si existe $f:X\to Y$ tal que $f$ es inyectiva.

La definición anterior nos ayudará a determinar cuándo un conjunto $X$ tiene más elementos que un conjunto $Y$, aún si $X$ y $Y$ son infinitos. A continuación daremos la definición formal de conjunto infinito.

Conjunto infinito

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 tanto, $|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$, entonces se cumple por vacuidad que existe la función $\emptyset$ tal que $\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, 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$ tal que $g(n_1)=g(n_2)$.

Caso 1: Si $n_1, n_2\in n$, entonces $g(n_1)=f(n_1)=f(n_2)=g(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

  • Muestra que si $X$ es un conjunto tal que para cada natural $n$ existe una función inyectiva $f_n:n\to X$, entonces existe una función inyectiva $f$ de $\mathbb{N}$ en $X$.
  • Muestra que si $X$ no es un conjunto finito, entonces para cada subconjunto finito $A$ de $X$, el conjunto $X\setminus A$ no es finito.
  • Retomando el ejercicio anterior, si $a\in X$, ¿existirá una función biyectiva entre $X$ y $X\setminus\set{a}$?
  • Muestra que si $A$ y $B$ son conjuntos tales que $A\cup B$ no es finito, entonces alguno de los conjuntos $A$ o $B$ no es finito.

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.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Conjuntos finitos (parte II)

Siguiente entrada: Teoría de los Conjuntos I: Conjuntos numerables