Archivo de la etiqueta: teoría de conjuntos

Teoría de los Conjuntos I: Teorema de Cantor-Schröder-Bernstein 

Por Gabriela Hernández Aguilar

3 respuestas

Introducción

En esta entrada probaremos que dados dos conjuntos $A$ y $B$, tales que $A\preceq B$ y $B\preceq A$, entonces $A\sim B$. Si bien este resultado es muy intuitivo, matemáticamente hay algunas complicaciones. Las hipótesis nos dan funciones inyectivas de $A$ en $B$ y de $B$ en $A$. Pero necesitamos una única función de $A$ en $B$ que sea biyectiva. ¿Cómo garantizamos la existencia de la segunda a partir de las primeras?

Lema del punto fijo

Primero demostraremos un lema sobre la existencia de un punto fijo, el cual será de utilidad en la demostración del teorema de Cantor-Schröder-Bernstein. Este lema nos dice que dada una función de $\mathcal{P}(X)$ en sí mismo con cierta propiedad de monotonía, ésta cumple que debe fijar a algún elemento de $\mathcal{P}(X)$. Veamos la definición de monotonía que necesitamos.

Definición. Sea $f:\mathcal{P}(X)\to \mathcal{P}(X)$. Diremos que $f$ es una función monótona si siempre que $A\subseteq A’\subseteq X$, se cumple que $f(A)\subseteq f(A’)$. Es decir, se preserva la contención bajo $f$.

Ejemplo.

Sea $X=\set{\emptyset, \set{\emptyset}}$ y sea $f=\set{(\emptyset,\emptyset), (\set{\emptyset}, \set{\emptyset}), (\set{\set{\emptyset}}, \emptyset), (\set{\emptyset, \set{\emptyset}},\set{\emptyset})}$. Consideremos $A=\emptyset$ y $A’=\set{\emptyset}$. Tenemos que $f(A)=\emptyset$ y $f(A’)=\set{\emptyset}$, de modo que $f(A)\subseteq f(A’)$. Para cualquier otra elección de $A$ y $A’$ con $A\subseteq A’$ también se puede verificar que $f(A)\subseteq f(A’)$. Por ello, decimos que $f$ es monótona.

$\square$

Lema. Sea $\varphi:\mathcal{P}(X)\to \mathcal{P}(X)$ función monótona. Entonces existe $E\subseteq X$ tal que $\varphi(E)=E$, es decir, $\varphi$ deja fijo a algún elemento de $\mathcal{P}(X)$.

Demostración:

Sea $\varphi:\mathcal{P}(X)\to \mathcal{P}(X)$ función monótona y sea $\mathcal{L}=\set{A\in \mathcal{P}(X): \varphi(A)\subseteq A}$.

Veremos que $\mathcal{L}\not= \emptyset$. Para ello, probaremos que $X\in \mathcal{L}$. Para empezar, $X\in \mathcal{P}(X)$ pues para cualquier conjunto $X$, $X\subseteq X$. Además, se tiene que $\varphi(X)\in \mathcal{P}(X)$, por lo que $\varphi(X)\subseteq X$.

Como $\mathcal{L}$ no es vacío, podemos considerar $E=\bigcap \mathcal{L}$. Veremos que $\varphi(E)=E$, lo cual mostaremos viendo la doble contención.

$\subseteq$) Sea $K\in \mathcal{L}$. Tenemos que $E\subseteq K$. Como $\varphi$ es monotona, entonces $\varphi(E)\subseteq \varphi(K)$. Además, como $K\in \mathcal{L}$ se tiene que $\varphi(K)\subseteq K$ y por transitividad de la contención se tiene que $\varphi(E)\subseteq K$. Como esto sucede para cualquier $K\in \mathcal{L}$, se cumple entonces $\varphi(E)\subseteq E$.

$\supseteq$) Dado que $\varphi(E)\subseteq E$ y $\varphi$ es monótona se tiene que $\varphi(\varphi(E))\subseteq \varphi(E)$. Por ello, $\varphi(E)\in \mathcal{L}$ y por lo tanto, $E\subseteq \varphi(E)$.

Por lo tanto, $\varphi(E)=E$.

$\square$

Teorema de Cantor-Schröder-Bernstein1

Antes de demostrar el teorema de Cantor-Schröder-Bernstein, enunciemos los siguientes recordatorios que usaremos en la demostración:

Recordatorio 1. Si $f:X\to Y$ es una función y se tiene $Z\subseteq Z’\subseteq X$, entonces $f[Z]\subseteq f[Z’]$.

Recordatorio 2. Sean $A,B\subseteq X$. Si $A\subseteq B$, entonces $X\setminus B\subseteq X\setminus A$.

Teorema (Cantor-Schröder-Bernstein). Si $A\preceq B$ y $B\preceq A$, entonces $A\sim B$.

Demostración:

Supongamos que $A\preceq B$ y $B\preceq A$, esto es, existe $f:A\to B$ inyectiva y existe $g:B\to A$ inyectiva.

Sea $\varphi:\mathcal{P}(A)\to \mathcal{P}(A)$ dada por $\varphi(X)=A\setminus g[B\setminus f[X]]$. Veamos que $\varphi$ es monótona.

Sean $X,X’\in \mathcal{P}(A)$ tales que $X\subseteq X’$, por el recordatorio $1$, tenemos que $f[X]\subseteq f[X´]$, luego por el recordatorio 2 tenemos que $B\setminus f[X’]\subseteq B\setminus f[X]$. Luego, por el recordatorio 1 $g[B\setminus f[X’]]\subseteq g[B\setminus f[X]]$. Finalmente, por el recordatorio $2$ se tiene que $A\setminus g[B\setminus f[X]]\subseteq A\setminus g[B\setminus f[X’]]$. Por lo tanto, $\varphi(X)\subseteq \varphi(X’)$ y así, $\varphi$ es monótona.

Luego, por el lema del punto fijo tenemos que existe $E\in \mathcal{P}(X)$ tal que $\varphi(E)=E$. De este modo:

\begin{align*}
E&= \varphi(E)\\
\text{entonces} \ E&= A\setminus g[B\setminus f[E]]\\
\text{entonces}\ A\setminus E&= g[B\setminus f[E]]
\end{align*}

Consideremos $g_1=g\upharpoonright: B\setminus f[E]\to g[B\setminus f[E]]$. Dado que $g$ es inyectiva, entonces $g_1$ es biyectiva y por lo tanto, $g_1^{-1}$ es función.

Definimos $h:A\to B$ como:

$h(x)= \left\{ \begin{array}{lcc}
             f(x) &   si  & x\in E \\
             \\ g_1^{-1}(x) &  si & x\in A\setminus E= g[B\setminus f[E]]
             \end{array}
   \right. $

Veamos que $h$ es biyectiva.

Primero veamos que $h$ es inyectiva. Sean $x,x’\in A$ tales que $x\not=x’$, veamos que $h(x)\not= h(x’)$.

Caso 1: Si $x, x’\in E$, entonces $h(x)=f(x)\not= f(x’)=h(x’)$ pues $f$ es inyectiva.

Caso 2: Si $x, x’\in A\setminus E$, entonces $h(x)=g_1^{-1}(x)\not=g_1^{-1}(x’)=h(x)$ pues $g_1^{-1}$ es inyectiva.

Caso 3: Si $x\in E$ y $x’\in A\setminus E$, entonces $h(x)=f(x)\in f[E]$ y $h(x’)=g_1^{-1}(x’)\in B\setminus f[E]$, por lo que $h(x)\not= h(x’)$.

Por lo tanto, $h$ es inyectiva.

Ahora, veamos que $h$ es suprayectiva. Consideremos $B$ como $B= (B\setminus f[E])\cup f[E]$.

Sea $y\in B$, entonces $y\in B\setminus f[E]$ o $y\in f[E]$.

Caso 1: Si $y\in B\setminus f[E]$, entonces $g(y)\in g[B\setminus g[E]]$, por lo que $h(g(y))= g_1^{-1}(g(y))= y$.

Caso 2: Si $y\in f[E]$ existe $e\in E$ tal que $f(e)=y$. Así, $h(e)=f(e)=y$.

Por lo tanto, $h$ es suprayectiva.

Concluimos que $h$ es biyectiva y así, $A\sim B$.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

  1. Definamos al conjunto de números pares como $P=\set{2k:\ k\in \mathbb{N}}$. En la entrada anterior ya vimos que $P\sim \mathbb{N}$. Da una demostración alternativa a esto usando el teorema de Cantor-Schröder-Bernstein.
  2. Resuelve los siguientes incisos.
    • Muestra la función $f:\mathbb{N}\to \mathbb{N}\times \mathbb{N}$ dada por $f(x)=(x,1)$ es inyectiva, pero no suprayectiva.
    • Muestra que la función $g:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ dada por $g(a,b)=2^a3^b$ es inyectiva, pero no suprayectiva.
    • ¿Qué dice entonces el teorema de Cantor-Schröder-Bernstein sobre $\mathbb{N}$ y $\mathbb{N}\times \mathbb{N}$?
    • ¿Es sencillo dar una función biyectiva explícita $h:\mathbb{N}\to \mathbb{N}\times \mathbb{N}$?

Más adelante…

En la siguiente entrada definiremos qué es un conjunto finito y hablaremos un poco acerca de lo que entenderemos por cardinal de un conjunto. Daremos los primeros pasos para hablar de conjuntos infinitos. Ya platicamos un poco que intuitivamente $\mathbb{N}$ debe serlo, pero tenemos que probarlo formalmente. Un poco más adelante, veremos que hay conjuntos infinitos que no tienen la misma cardinalidad. Así, nos interesará ver que pasa con las cardinalidades de estos conjuntos.

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. Puedes consultar una demostración diferente del teorema de Cantor-Schröder-Bernstein en el siguiente libro: K. Hrbacek, T. Jech, Introduction to Set Theory, Third Edition, Marcel Dekker Inc., 1999, p. 66-68.
    Y una segunda demostración diferente en: J.A. Amor Montaño, Teoría de conjuntos para estudiantes de ciencias, Segunda edición, Coordinación de Servicios Editoriales, Facultad de Ciencias UNAM, 2005, p. 79-80 ↩︎

Teoría de los Conjuntos I: Buenos órdenes para cualquier conjunto

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada usaremos lo que aprendimos en la entrada anterior sobre el lema de Zorn para demostrar que cualquier conjunto no vacío puede ser bien ordenado.

Ordenando buenos órdenes de subconjuntos

En esta entrada demostraremos que cualquier conjunto no vacío $X$ tiene un buen orden. Si $a\in X$, entonces $(a,a)$ es un buen orden para $\{a\}\subseteq X$, así que podemos darle un buen orden a un elemento de $X$. La intuición de nuestra prueba es que podemos ir «agrandando» un buen orden para «pocos elementos» de $X$ hasta llegar a ordenar todo $X$. Sin embargo, no podemos hacer esto paso a paso. Tendremos que hacerlo de golpe usando el lema de Zorn. Para ello, daremos una noción de cuándo «un buen orden ordena más elementos de $X$ que otro y lo extiende». Nuestro resultado se obtendrá aplicando el lema de Zorn a esta noción. Comencemos con formalizarla.

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 parcial 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_1)\leq(C,R_2)$.

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

$\square$

Ya tenemos el conjunto parcialmente ordenado $(\mathcal{B},\leq)$ al que queremos aplicar el lema de Zorn. Pero tenemos que verificar una hipótesis importante: que cada cadena tiene cota superior. Esto lo hacemos en el siguiente lema.

Lema. Sea $X$ un conjunto y $\mathcal{B}$ y $\leq$ definidos como en el lema anterior. Entonces, en $(\mathcal{B}, \leq)$ toda cadena tiene una cota superior.

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 consiguiente, $A\subseteq B$, $R\subseteq R’$ y para cualquier $a\in A$ y $b\in B\setminus A$, se tiene que $(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$

El teorema del buen orden

Ya con los ingredientes anteriores, podemos enfocarnos en el resultado principal de esta entrada.

Teorema. (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 definición 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, $(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 entrada, mostraremos que el teorema del buen orden implica el axioma de elección. La idea intuitiva es sencilla. Para un conjunto $X$, ¿cuál elemento elegimos de cada subconjunto no vacío de $X$? Pues damos un buen orden a $X$ y para cada subconjunto no vacío elegimos el mínimo.

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}$. Esto demuestra que $X$ tiene una función de elección.

$\square$

Resumen de últimas equivalencias

Podemos resumir la serie de resultados probados en esta entrada y la anterior mediante el siguiente teorema.

Teorema. Son equivalentes los siguientes resultados

  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 termnado esl estudio de algunas de las equivalencias más importantes del axioma de elección.

Tarea moral

  1. Sea $(X,\leq)$ un conjunto parcialmente ordenado en el que cualquier cadena tiene una cota superior. Muestra que para cada $a\in X$ existe un elemento $\leq-$maximal $x\in X$ tal que $a\leq x$.
  2. Sea $(L,\leq)$ un conjunto linealmente ordenado. Prueba 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$.
  3. Sea $X$ cualquier conjunto infinito. Prueba que $X$ puede ser bien ordenado de tal forma que $X$ no tenga máximo. Prueba 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 del axioma de elección relevante en álgebra lineal.

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»

Teoría de los Conjuntos I: Bases para cualquier espacio vectorial

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: 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 Álgebra Lineal I disponible aquí en el blog.

Recordatorio de definiciones

Daremos un breve recordatorio sobre qué quiere decir que un subconjunto arbitrario (finito o no) de un espacio vectorial sea generador, linealmente independiente o base.

Definición. Sea $V$ un espacio vectorial sobre un campo $F$ y $S\subseteq V$. Decimos que $S$ es generador si para cualquier $v\in V$ existe una cantidad finita de vectores $v_1,\ldots,v_n$ en $V$ y de escalares $\alpha_1,\ldots,\alpha_n$ en $F$ tales que $$v=\alpha_1v_1+\ldots+\alpha_nv_n.$$

Definición. Sea $V$ un espacio vectorial sobre un campo $F$ y $L\subseteq V$. Decimos que $L$ es linealmente independiente si para cualquier elección finita de vectores distintos $v_1,\ldots,v_n$ en $L$ y escalares $\alpha_1,\ldots,\alpha_n$, la igualdad $$0=\alpha_1v_1+\ldots+\alpha_nv_n$$ implica que $\alpha_1=\ldots=\alpha_n=0$.

Definición. Sea $V$ un espacio vectorial sobre un campo $F$ y $B\subseteq V$. Decimos que $B$ es una base de $V$ si $B$ es generador y linealmente independiente.

Todo espacio vectorial tiene una base

Demostraremos el siguiente resultado

Teorema. Todo espacio vectorial tiene una base.

Demostración.

Sea $V$ un espacio vectorial sobre un campo $F$. Lo que queremos mostrar es que existe un subconjunto $B$ de $V$ que genera a $B$ 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{L\subseteq V:L\ \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 $L$ un conjunto tal que $L\in\mathcal{F}$. Luego, $L$ es linealmente independiente y, por tanto, cualquier subconjunto de $L$ es linealmente independiente, en particular todos los subconjuntos finitos de $L$ son linealmente independientes. En consecuencia, cualquier subconjunto finito de $L$ pertence a $\mathcal{F}$.

Ahora, sea $L$ un conjunto tal que todo subconjunto finito de $L$ pertenece a $\mathcal{F}$. Para cualquier elección de vectores distintos $v_1,\ldots,v_n$ tenemos entonces que $\{v_1,\ldots,v_n\}$ es linealmente independiente. Pero entonces cualquier elección de escalares $\alpha_1,\ldots,\alpha_n$ tales que $$0=\alpha_1v_1+\ldots+\alpha_nv_n$$ cumple que $\alpha_1=\ldots=\alpha_n=0$. Concluimos entonces que $L$ es linealmente independiente. Por tanto, $L\in\mathcal{F}$. Esto demuestra que $\mathcal{F}$ es una familia de conjuntos de carácter finito.

Ahora, por el axioma de elección (en la versión de lema de Tukey-Teichmüller) toda familia no vacía de carácter finito tiene un elemento $\subseteq$-maximal. Sea $B$ un elemento $\subseteq$-maximal en $\mathcal{F}$. Afirmamos que $B$ es una base para $V$. Como $B$ es linealmente independiente, sólo basta probar que $B$ genera a $V$.

Procedamos por contradicción y supongamos que $B$ no genera a $V$. Sea $v\in V$ que no esté en el espacio generado por $B$. Entonces $B\cup\set{v}$ sería un subconjunto de $V$ linealmente independiente que contiene propiamente a $B$ (ver, por ejemplo la última proposición en la entrada Conjuntos generadores e independencia lineal). ¡Esto contradice la maximalidad de $B$ con respecto a la contención en $\mathcal{F}$!

Así, $B$ es linealmente independientes y generador, y por lo tanto es una base de $V$.

$\square$

Tarea moral

Los siguientes resultados presentan algunos refinamientos del resultado mencionado. Por ejemplo, enuncian que «cualquier base parcial se puede completar» a una base, o que «de cualquier conjunto generador se puede extraer una base», etc.

  1. Sea $V$ un espacio vectorial sobre un campo $K$. Muestra que todo conjunto linealmente independiente está contenido en una base de $V$.
  2. 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$.
  3. 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$.

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»

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

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada abordaremos un axioma relevante no sólo en teoría de conjuntos sino en muchas ramas de las matemáticas. Distintas proposiciones aparentemente sencillas no podrían demostrarse sin su ayuda y algunas de sus consecuencias son tan poderosas que cuesta trabajo aceptarlas. Es por eso que el llamado axioma de elección ha sido controversial desde su formulación a manos de Ernst Zermelo en 1904.

Funciones de elección

Comenzaremos dando una definición para después enunciar el mencionado axioma.

Definición. Sea $A$ un conjunto. Una función de elección para $A$ es una función $f:\mathcal{P}(A)\setminus\{\emptyset\}\to A$ tal que, para todo $B\in\mathcal{P}(A)\setminus\{\emptyset\}$, se tiene que $f(B)\in B$.

Ejemplo.

Sea $A=\set{0,1}$. Luego, $\mathcal{P}(A)=\{\emptyset,\{0\},\{1\},\{0,1\}\}$. Si definimos $f:\mathcal{P}(A)\setminus\set{\emptyset}\to A$ por medio $f=\set{(\set{0},0),(\set{1},1),(\set{0,1},1)}$, entonces $f$ es una función de elección.

$\square$

El siguiente resultado muestra que existe una gran cantidad de conjuntos que tienen una función de elección.

Proposición. Si $X$ es un conjunto finito no vacío, entonces $X$ tiene una función de elección.

Demostración.

Sea $X$ un conjunto finito y no vacío. Luego, por ser finito, existe un número natural $n$ y una función biyectiva $f:n\to X$ y, además, $n\not=0$ ya que $X$ es no vacío. Ahora, para cada $A\subseteq X$ no vacío consideremos su imagen inversa, $f^{-1}[A]=\set{m\in n:f(m)\in A}$. Dado que $f^{-1}[A]\not=\emptyset$, entonces existe $\min(f^{-1}[A])$. Definamos $F:\mathcal{P}(X)\setminus\set{\emptyset}\to X$ por medio de $F(A)=f(\min(f^{-1}[A]))$. Luego, $F$ es una función de elección para $X$.

$\square$

Axioma de elección y equivalencias

Aunque todos los conjuntos finitos no vacíos tengan función de elección, resultará imposible demostrar lo mismo para todos los conjuntos. Es por ello que necesitaremos agregar un axioma a nuestra teoría.

Axioma de elección. Todo conjunto no vacío tiene una función de elección.

Vamos a discutir varios de los usos de este axioma, pero para ello es conveniente poder pensarlo de muchas maneras. En esta primera entrada enunciaremos una serie de equivalencias a este teorema muy relacionadas con «elegir». En la siguiente entrada enunciaremos equivalencias relacionadas con «ordenar».

Teorema. Las siguientes proposiciones son equivalentes:

  1. El axioma de elección.
  2. Si $\mathcal{A}$ es una familia no vacía de conjuntos no vacíos y ajenos dos a dos, entonces existe un conjunto $B$ tal que para todo $A\in\mathcal{A}$, se tiene que $A\cap B$ es un conjunto unitario.
  3. Toda función suprayectiva tiene al menos una inversa derecha.
  4. Si $\set{A_\alpha}_{\alpha\in\Gamma}$ es tal que $A_\alpha\not= \emptyset$ y $A_\alpha\cap A_\beta=\emptyset$ para cualesquiera $\alpha,\beta\in\Gamma$ con $\alpha\not=\beta$, entonces existe $B\subseteq\cup_{\alpha\in\Gamma}A_\alpha$ tal que $B\cap A_\alpha$ es unitario para cada $\alpha\in\Gamma$.
  5. Si $\set{A_\alpha}_{\alpha\in \Gamma}$ es una famila indizada no vacía de conjuntos no vacíos, entonces existe una función $f:\Gamma\to\cup_{\alpha\in\Gamma}A_\alpha$ tal que para cada $\alpha\in\Gamma$, se cumple que $f(\alpha)\in A_\alpha$.
  6. Si $F:X\to \mathcal{P}(Y)\setminus\set{\emptyset}$ es una función, entonces existe una función $f:X\to Y$ tal que $f(x)\in F(x)$ para todo $x\in X$.

La diferencia entre $2$ y $4$ es que en $5$ se pide que $B$ sea subconjunto de la unión de la familia.

Demostración.

$1)\Rightarrow 2)$ Supogamos que el axioma de elección es válido. Sea $\mathcal{A}$ una familia no vacía de conjuntos no vacíos ajenos dos a dos.

Sea $C=\bigcup\mathcal{A}$. Como $C$ es no vacío, podemos fijar $f:\mathcal{P}(C)\setminus\set{\emptyset}\to C$ una función de elección. Notemos que si $A\in\mathcal{A}$, entonces $A\subseteq C$, por lo que $A\in\mathcal{P}(C)\setminus\set{\emptyset}$. Definamos $B=\set{f(A):A\in\mathcal{A}}$. Veamos ahora que $B\cap A$ es un conjunto unitario para todo $A\in\mathcal{A}$.

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

$2)\Rightarrow 3)$

Sean $A$ y $B$ conjuntos y $f:A\to B$ una función suprayectiva. Para cada $x\in B$ definamos $A_x=\set{a\in A:f(a)=x}$. Notemos que para cada $x\in B$, se tiene que $A_x\not=\emptyset$, pues $f$ es suprayectiva. Además, si $x\not=x’$, entonces $A_x\cap A_{x’}=\emptyset$, ya que si existiera un elemento $y\in A_x\cap A_{x’}$, tendríamos que $f(y)=x$ y $f(y)=x’$ y, por consiguiente, $x=x’$ ya que $f$ es una función, pero esto contradice que $x\not=x’$. Así pues, si $x\not=x’$, entonces $A_x\cap A_{x’}=\emptyset$.

Consideremos a la familia de conjuntos $\mathcal{A}=\set{A_x:x\in B}$ la cual consta de conjuntos no vacíos y ajenos dos a dos. Por hipótesis, existe un conjunto $C$ tal que $C\cap A_x$ es un conjunto unitario para cada $A_x\in\mathcal{A}$. Para $x\in B$, denotemos por $a_x$ al único elemento del conjunto $C\cap A_x$. Definamos $g:B\to A$ por medio de $g(x)=a_x$. Expresando a $g$ como un subconjunto de $B\times A$ tenemos que $g=\set{(x,a_x):x\in B}$. Notemos que $g$ es una función, ya que si $(w,v),(w,z)\in g$, entonces $(w,v)=(x,a_x)$ y $(w,z)=(y,a_y)$ para algunos $x,y\in B$. De las iguladades anteriores se sigue que $w=x=y$ y, por tanto, $v=a_x=a_y=z$. Por tanto, $g$ es función. Finalmente, veamos que $g$ es inversa derecha de $f$, es decir, que $f\circ g:B\to B$ es la función identidad; esto es, $f\circ g=Id_B$.

Sea pues $x\in B$ un elemento arbitrario. Luego, $(f\circ g)(x)=f(g(x))=f(a_x)=x$, pues $a_x\in A_x$. Por lo tanto, $f\circ g=Id_B$, lo que muestra que $g$ es inversa derecha de $f$.

$3)\Rightarrow 4)$ Supongamos que $\mathcal{A}=\set{A_\alpha:\alpha\in\Gamma}$ es una familia no vacía de conjuntos no vacíos tales que $A_\alpha\cap A_\beta=\emptyset$ si $\alpha\not=\beta$.

Definamos $f:\bigcup_{\alpha\in\Gamma}A_\alpha\to\Gamma$ por medio de $f(x)=\alpha$ si $x\in A_\alpha$. Podemos describir a $f$ como el siguiente conjunto $f:=\set{(x,\alpha):x\in A_\alpha,\alpha\in\Gamma}\subseteq(\bigcup_{\alpha\in\Gamma}A_\alpha)\times \Gamma$. Nuevamente, lo primero que hay que hacer es verificar que $f$ sea una función. Sean $(a,b),(a,c)\in f$. Luego, $(a,b)=(x,\alpha)$ y $(a,c)=(y,\beta)$ para algunos $x,y\in\bigcup_{\alpha\in \Gamma}A_\alpha$ y $\alpha,\beta\in\Gamma$, tales que $x\in A_\alpha$ y $y\in A_\beta$. Dado que $(a,b)=(x,\alpha)$ y $(a,c)=(y,\beta)$, entonces $a=x=y$ y, en consecuencia, $x\in A_\alpha\cap A_\beta$, lo que muestra que $A_\alpha\cap A_\beta\not=\emptyset$ y, por tanto, $\alpha=\beta$, es decir, $b=\alpha=\beta=c$, lo que muestra que $f$ es una función.

Ciertamente, $f$ es una función suprayectiva, pues si $\alpha\in\Gamma$ es cualquier elemento, entonces, existe $x\in A_\alpha$ pues $A_\alpha\not=\emptyset$, tal que $f(x)=\alpha$, por definición de $f$. Esto muestra que $\alpha$ es la imagen de un elemento en $\bigcup_{\alpha\in \Gamma}A_\alpha$ bajo la función $f$ y, por tanto, $f$ es suprayectiva. Luego, por hipótesis, existe $g:\Gamma\to\bigcup_{\alpha\in\Gamma}A_\alpha$ función inversa derecha de $f$, es decir, $f\circ g=Id_\Gamma$. Sea $B:=g[\Gamma]=\set{g(\alpha):\alpha\in\Gamma}\subseteq\bigcup_{\alpha\in\Gamma}A_\alpha$.

Notemos que para cada $\alpha\in\Gamma$, se tiene que $g(\alpha)\in A_\alpha$. En efecto, si $\alpha\in\Gamma$, entonces $f(g(\alpha))=Id_\Gamma(\alpha)=\alpha$, por lo que $g(\alpha)\in A_\alpha$. Por lo tanto, $\set{g(\alpha)}\subseteq A_\alpha\cap B$ para todo $\alpha\in\Gamma$.

Ahora, si $x\in A_\alpha\cap B$, entonces $x=g(\beta)$ para algún $\beta\in\Gamma$. Luego, $f(x)=f(g(\beta))=Id_\Gamma(\beta)=\beta$. Por otro lado, como $x\in A_\alpha$, también se tiene que $f(x)=\alpha$ y, por consiguiente, $\beta=\alpha$. Así, $x=g(\alpha)$, lo que demuestra que $A_\alpha\cap B=\set{g(\alpha)}$. Por lo tanto, $B$ es subconjunto de $\bigcup_{\alpha\in\Gamma}A_\alpha$ y cumple que $B\cap A_\alpha$ es un conjunto unitario para cada $\alpha\in\Gamma$.

$4)\Rightarrow 5)$ Sea $\set{A_\alpha}_{\alpha\in\Gamma}$ una familia de conjuntos no vacíos. Para cada $\alpha\in\Gamma$ definamos $B_\alpha:=\set{\alpha}\times A_\alpha$. Luego, $\set{B_\alpha:\alpha\in\Gamma}$ es una familia no vacía de conjuntos no vacíos tales que $B_\alpha\cap B_\beta=\emptyset$ si $\alpha\not=\beta$.

Luego, por hipótesis, existe $B\subseteq\bigcup_{\alpha\in\Gamma}B_\alpha$ tal que $B\cap B_{\alpha}$ es un conjunto unitario para cada $\alpha\in \Gamma$. Ahora bien, el único elemento de $B\cap B_\alpha$ es de la forma $(\alpha,a)$ con $a\in A_\alpha$, pues pertenece, en particular, al conjunto $B_\alpha=\set{\alpha}\times A_\alpha=\set{(\alpha,a):a\in A_\alpha}$. Denotemos por $a_\alpha$ al único elemento de $A_\alpha$ tal que $B\cap B_\alpha=\set{(\alpha,a_\alpha)}$. Definamos $f:\Gamma\to\bigcup_{\alpha\in \Gamma}A_\alpha$ por medio de $f(\alpha)=a_\alpha$. Notemos que $f$ puede ser descrita como el conjunto $\set{(\alpha,a_\alpha):\alpha\in\Gamma}$. Luego, para comprobar que $f$ es una función tomemos $(a,b),(a,c)\in f$. Entonces, $(a,b)=(\alpha,a_\alpha)$ y $(a,c)=(\beta,a_\beta)$ para algunos $\alpha,\beta\in\Gamma$ y $a_\alpha\in A_\alpha$ y $a_\beta\in A_\beta$ tales que $(\alpha,a_\alpha)$ y $(\beta,a_\beta)$ son los únicos elementos de $B\cap B_\alpha$ y $B\cap B_\beta$, respectivamente. A partir de las igualdades $(a,b)=(\alpha,a_\alpha)$ y $(a,c)=(\beta,a_\beta)$ se sigue que $a=\alpha=\beta$ y, por tanto, $b=a_\alpha=a_\beta=c$. Esto que muestra $f$ es una función. Finalmente, para cada $\alpha\in\Gamma$, se tiene que $f(\alpha)\in A_\alpha$.

$5)\Rightarrow 6)$ Sea $F:X\to\mathcal{P}(Y)\setminus\set{\emptyset}$ una función.

Consideremos a la familia de conjuntos no vacíos $\mathcal{F}=\set{F(x):x\in X}$. Luego, por hipótesis, existe una función $f:X\to\bigcup\mathcal{F}$ tal que $f(x)\in F(x)$ para cada $x\in X$. Notemos ahora que $\bigcup\mathcal{F}=\bigcup_{x\in X}F(x)\subseteq Y$. Así, $f$ es una función con dominio $X$ y codominio $Y$. Por lo tanto, existe $f:X\to Y$ tal que $f(x)\in F(x)$ para cada $x\in X$.

$6)\Rightarrow 1)$ Sea $X\not=\emptyset$ un conjunto. Definamos $F:\mathcal{P}(X)\setminus\set{\emptyset}\to\mathcal{P}(X)\setminus\set{\emptyset}$ por medio de $F(B)=B$. Luego, por hipótesis, existe una función $f:\mathcal{P}(X)\setminus\set{\emptyset}\to X$ tal que $f(B)\in F(B)=B$ para todo $B\in\mathcal{P}(X)\setminus\set{\emptyset}$. Por lo tanto, $X$ tiene una función de elección.

$\square$

Una aplicación del axioma de elección a cardinales numerables

Para finalizar esta entrada, enunciaremos y demostraremos 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:\mathbb{N}\to A_n:f \ \text{es función biyectiva}}$. Dado que cada $A_n$ es numerable, entonces, por definición, existe una función $f_n:\mathbb{N}\to A_n$ biyectiva para todo $n\in\mathbb{N}$. Así pues, $B_n\not=\emptyset$ para cada $n\in\mathbb{N}$.

Consideremos la colección de conjuntos no vacíos $\set{B_n:n\in\mathbb{N}}$. Por el teorema anterior, el axioma de elección implica que existe una función $F:\mathbb{N}\to\bigcup_{n\in\mathbb{N}}B_n$ tal que $F(n)\in B_n$ para cada $n\in\mathbb{N}$. Definamos $g_n:=F(n)$ para cada $n\in\mathbb{N}$.

Definamos ahora $G:\mathbb{N}\times\mathbb{N}\to\bigcup_{n\in\mathbb{N}}A_n$ por medio de $G(r,s)=g_s(r)$. Veamos que $G$ es una función biyectiva. Sean $(r,s),(x,y)\in\mathbb{N}\times\mathbb{N}$ tales que $G(r,s)=G(x,y)$. Entonces, $g_s(r)=g_y(x)$. Como $g_s\in B_s$ y $g_y\in B_y$, entonces $g_s(r)\in A_s$ mientras que $g_y(x)\in A_y$ y, consecuentemente, $A_s\cap A_y\not=\emptyset$, lo cual puede ocurrir si y sólo si $A_s=A_y$, es decir, $s=y$. Dado que $g_s(r)=g_s(x)$ y $g_s$ es biyectiva, entonces $r=x$. Esto muestra que $(r,s)=(x,y)$ y, por lo tanto, $G$ es inyectiva.

Finalmente veamos que $G$ es suprayectiva. Sea $a\in\bigcup_{n\in\mathbb{N}}A_n$. Luego, $a\in A_m$ para algún $m\in\mathbb{N}$ y, por consiguiente, existe $b\in\mathbb{N}$ tal que $g_m(b)=a$, ya que $g_m$ es biyectiva. De modo que tomando al elemento $(b,m)\in\mathbb{N}\times\mathbb{N}$ se sigue que $G(b,m)=g_m(b)=a$, lo que muestra que $G$ es suprayectiva.

Por lo tanto, $G$ es una biyección y, en consecuencia, $\mathbb{N}\times\mathbb{N}$ es equipotente a $\bigcup_{n\in\mathbb{N}}A_n$. Luego, como $\mathbb{N}\times\mathbb{N}$ es equipotente a $\mathbb{N}$, se sigue que $\bigcup_{n\in\mathbb{N}}A_n$ es equipotente a $\mathbb{N}$, es decir, $\bigcup_{n\in\mathbb{N}}A_n$ es numerable.

$\square$

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

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

Demostración.

Sea $X$ un conjunto infinito. Definamos $g:\cup_{n\in\mathbb{N}}X^n\to \mathcal{P}(X)$ por medio de $g(h)=X\setminus im(h)$ para cada $h\in\cup_{n\in\mathbb{N}}X^n$, donde $X^n$ denota al conjunto de funciones de $n$ en $X$. Fijemos una función de elección $e:\mathcal{P}(X)\setminus\{\emptyset\}\to X$. Veamos que existe una función $f:\mathbb{N}\to X$ tal que $f(0)=(e\circ g)(\emptyset)$ y $f(n+1)=(e\circ g)(f\upharpoonright_n)$ para cada $n\in\mathbb{N}$. Para ello, probaremos la siguiente afirmación.

Afirmación. Para cada $m\in\mathbb{N}$ existe una única función $f_m:m+1\to X$ tal que, $f_m(0)=(e\circ g)(\emptyset)$ y $f(n+1)=(e\circ g)(f\upharpoonright_n)$ para cada $n\in m+1$ tal que $n+1\in m+1$.

Demostración de la afirmación.

Para $m=0$, consideremos la función $f_0:1\to X$ definida por $f_0=\{(0,(e\circ g)(\emptyset))\}$. Luego, $f_0(0)=(e\circ g)(\emptyset)$ y, por vacuidad, para cada $n\in 1$ tal que $n+1\in1$, $f_0(n+1)=(e\circ g)(f\upharpoonright_n)$. Ahora bien, si $f’:1\to X$ es otra función que satisface las mismas condiciones que $f_0$, en particular tenemos que $f'(0)=(e\circ g)(\emptyset)$ y, por ello, $f'(0)=f_0(0)$, lo que demuestra que $f’=f_0$. Por tanto, el resultado es válido para $m=0$. Supongamos que para algún $m\in\mathbb{N}$ existe una única función $f_m:m+1\to X$ tal que, $f_m(0)=(e\circ g)(\emptyset)$ y $f_m(n+1)=(e\circ g)(f\upharpoonright_n)$ para cada $n\in m+1$ tal que $n+1\in m+1$.
Definamos ahora $f_{m+1}:m+2\to X$ por medio de $f_{m+1}=f_m\cup\{(m+1,(e\circ g)(f_m))\}$, donde $f_m:m+1\to X$ es la única función de nuestra hipótesis. Notemos que, por definición de $f_{m+1}$, $f_{m+1}(0)=f_m(0)=(e\circ g)(\emptyset)$ y, más aún, $f_{m+1}\upharpoonright_n=f_m\upharpoonright_n$ para cada $n\leq m+1$; por otro lado, si $n\in m+2$ es tal que $n+1\in m+2$, tenemos dos posibilidades: $n+1\in m+1$, en cuyo caso tenemos que $f_{m+1}(n+1)=f_m(n+1)=(e\circ g)(f_m\upharpoonright_n)=(e\circ g)(f_{m+1}\upharpoonright_n)$; o bien, $n+1=m+1$, en cuyo caso tenemos que $f_{m+1}(n+1)=f_{m+1}(m+1)=(e\circ g)(f_m)=(e\circ g)(f_{m+1}\upharpoonright_{m+1})$. Por tanto, $f_{m+1}$ satisface las condiciones deseadas. Veamos ahora que es la única función con tales características. Supongamos que $f’:m+2\to X$ es una función tal que $f'(0)=(e\circ g)(\emptyset)$ y $f'(n+1)=(e\circ g)(f’\upharpoonright_n)$ para cada $n\in m+2$ tal que $n+1\in m+2$. Notemos que $f’\upharpoonright_{m+1}:m+1\to X$ es una función que satisface $f’\upharpoonright_{m+1}(0)=(e\circ g)(\emptyset)$ y para cada $n\in m+1$ tal que $n+1\in m+1$, $f’\upharpoonright_{m+1}(n+1)=f'(n+1)=(e\circ g)(f’\upharpoonright_{n})=(e\circ g)((f’\upharpoonright_{m+1})\upharpoonright_n)$. Así, $f’\upharpoonright_{m+1}=f_{m}$, ya que $f_m:m+1\to X$ es la única función con tales características. Por tanto, $f'(n)=f_m(n)$ para cada $n\in m+1$. Luego, $f'(m+1)=(e\circ g)(f’\upharpoonright_{m})=(e\circ g)(f_m\upharpoonright_m)=(e\circ g)(f_{m+1}\upharpoonright_{m})=f_{m+1}(m+1)$. Por tanto, $f’=f_{m+1}$, lo que demuestra la unicidad de la función $f_{m+1}$. Esto concluye la prueba de la afirmación.

Ahora, consideremos la familia de funciones $\{f_m\}_{m\in\mathbb{N}}$ dadas por la afirmación anterior. Dicha familia de funciones es un sistema compatible de funciones pues, $f_{m+1}\upharpoonright_{m+1}=f_m$ para cualquier $m\in\mathbb{N}$, y por tanto $f:=\bigcup\{f_m\}_{m\in\mathbb{N}}$ es una función cuyo dominio es $\mathbb{N}$ y codominio es $X$. Además, $f(0)=(e\circ g)(\emptyset)$ y $f(n+1)=f_{n+1}(n+1)=(e\circ g)(f_{n+1}\upharpoonright_{n})=(e\circ g)(f\upharpoonright_{n})$ para cada $n\in\mathbb{N}$. Luego, si $n\in\mathbb{N}$, \[f(n+1)=(e\circ g)(f\upharpoonright_n)=e(g(f\upharpoonright_n))\in g(f\upharpoonright_n)=X\setminus im(f\upharpoonright_n). \] Lo anterior implica que $f(n+1)\notin im(f\upharpoonright_n)$ para cada $n\in\mathbb{N}$.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

  1. Demuestra que la unión numerable de conjuntos finitos es un conjunto numerable.
  2. Otro de los pendientes que teníamos en entradas anteriores es la existencia de conjuntos de representantes para relaciones de equivalencia. Ahora lo podemos demostrar. Prueba que si $X$ es un conjunto y $R$ es una relación de equivalencia en $X$, entonces existe un conjunto completo de representantes de la relación $R$.
  3. Demuestra que el axioma de elección es equivalente a la siguiente proposición: para toda relación $R$ existe una función $f$ tal que $dom\ f$ es igual al dominio activo de $R$ y $f\subseteq R$.
  4. Argumenta axiomáticamente que el conjunto $B_n$ de la demostración del último teorema en efecto es un conjunto.

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»

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

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En las entradas anteriores hablamos de conjuntos finitos e infinitos. Además, vimos que hay conjuntos infinitos que no son equipotentes entre sí: $\mathbb{N}$ y $\mathcal{\mathbb{N}}$. Ahora hablaremos un poco sobre qué son los cardinales, asumiremos su existencia y daremos una breve introducción a cómo se puede trabajar con ellos mediante aritmética cardinal.

Introducción a ¿qué es un cardinal?

La idea intuitiva detrás de los cardinales es que a cualquier conjunto $X$ se le pueda asignar un conjunto «canónico» $Y$ con la misma cardinalidad que $X$. Si esto es posible, diremos que la cardinalidad de $X$ es $Y$, y lo escribiremos como $|X|=Y$. A $Y$ le llamamos un cardinal. Recuerda que intuitivamente la noción de «ser equipotentes» es parecida a una relación de equivalencia (aunque estrictamente no lo es). Con esta intuición, puedes pensar a los cardinales como un «conjunto de representantes» de esta relación de equivalencia.

Si bien estamos muy lejos de tener algo así, hemos logrado algo de progreso parcial. Si un conjunto $X$ es finito, entonces es equipotente a un único natural $n$ y en ese caso dijimos que su cardinal es $n$, lo cual denotamos como $|X|=n$. Si $X$ es numerable, entonces dijimos que su cardinal es $\mathbb{N}$ y escribimos $|X|=\mathbb{N}$. Ya vimos que $\mathcal{P}(\mathbb{N})$ no es numerable. Si quisiéramos, podríamos decir que el cardinal de cualquier conjunto equipotente a $\mathcal{P}(\mathbb{N})$ es precisamente $\mathcal{P}(\mathbb{N})$, pero esto ya empieza a volverse algo tedioso y no es claro cómo se formaliza.

La formalización de los cardinales queda fuera del alcance de este curso, y depende de la manera en la que se axiomatiza la teoría de los conjuntos. Una manera de hacer esto es introducir a los números ordinales, lo cual queda como invitación a un curso posterior de teoría de los conjuntos. Sin embargo, si asumimos la existencia de los cardinales, podemos platicar un poco de la aritmética cardinal, lo cual haremos a continuación.

Suma de cardinales

Comenzaremos definiendo la suma de dos cardinales. Dicha operación está motivada en la regla de la suma para conjuntos finitos. Recuerda que esta regla dice que si $A$ y $B$ son conjuntos finitos disjuntos con $m$ y $n$ elementos, respectivamente, entonces $|A\cup B|=m+n$.

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

La definición también supone que $|A\cup B|$ no depende de la elección de $A$ y $B$. Para comprobar que la definición de suma de cardinales está bien definida tenemos que mostrar que en efecto esto es así; 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 cardinales es una operación conmutativa.

Por otro lado, si $\kappa$, $\lambda$ y $\mu$ son cardinales, se satisface por la asociatividad de la unión que $\kappa+(\lambda+\mu)=(\kappa+\lambda)+\mu$. Es decir, la suma de 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$ (la inclusión de $A$ en $A\cup B$) es una función inyectiva. Esto muestra que $\kappa=|A|\leq|A\cup B|=\kappa+\lambda$, como queríamos.

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$. ¿Podrás demostrar esto?

Producto de cardinales

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

Así, en efecto el producto de cardinales no depende de los conjuntos elegidos.

Algunas propiedades del producto de números naturales se preservan para el producto de cardinales.

Por ejemplo, si $\kappa$ y $\lambda$ son 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 cardinales $\kappa$, $\lambda$ y $\mu$. Intenta demostrar esto. Tendrás que usar propiedades de la unión y producto cartesiano. Por ejemplo, para el inciso 2 deberás usar que para cualesquiera conjuntos $A,B,C$ se cumple que $A\times(B\cup C)=(A\times B)\cup(A\times C)$.

También hay algunas propiedades de desigualdad de cardinales que involucran al producto. A continuación discutimos algunas brevemente.

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

Otra propiedad es que al multiplicar un cardinal por un natural, sucede lo que esperamos: el cardinal «se suma la cantidad apropiada de veces». Veamos un pequeño ejemplo. Si $\kappa$ es un 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$. Intenta demostrar que para cualquier natural $n$ y cardinal $\kappa$ se cumple que $(n+1)\times \kappa = n\times \kappa + \kappa$.

Finalmente, ¿cómo se comparan la suma y producto de un cardinal consigo mismo? Usando las propiedades ya comentadas, se sigue que para un cardinal $\kappa\geq2$, se cumple \[\kappa+\kappa=2\cdot\kappa\leq\kappa\cdot\kappa.\]

Exponenciación de cardinales

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

Si has realizado los ejercicios de entradas anteriores, notarás que esta definición también generaliza el caso de $A$ y $B$ finitos, en donde $\kappa$ y $\lambda$ son naturales.

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

$\square$

Platiquemos de algunas de las propiedades de exponenciación.

De la definición de exponenciación tenemos que si $\lambda>0$, entonces $\kappa\leq\kappa^{\lambda}$. Esto se debe a 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$.

Nota 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|^\lambda=|A|^{|B|}=$. 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 del estilo «ley de los exponentes» para 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$. 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 suprayectiva. Por lo tanto, $F$ es una biyección y, en consecuencia, $\kappa^{\lambda+\mu}=\kappa^{\lambda}\cdot\kappa^{\mu}$.

$\square$

Para finalizar con esta entrada 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\}$. Se tiene 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 suprayectiva.

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

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

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

Más adelante…

En la última unidad del curso hablaremos acerca del axioma de elección. Esto ayudará a cerrar algunos pendientes que hemos dejado a lo largo del curso. A grandes rasgos, el axioma de elección nos permitirá construir un conjunto eligiendo un elemento de cada conjunto de una familia de conjuntos. Como consecuencia, veremos que cualquier conjunto puede ser bien ordenado, así como algunas aplicaciones a otras áreas de las matemáticas.

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»