Archivo de la etiqueta: aritmética cardinal

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

Por Gabriela Hernández Aguilar

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»