Archivo del Autor: Gabriela Hernández Aguilar

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»

Teoría de los Conjuntos I: Conjuntos infinitos

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada definiremos qué es un conjunto infinito. Después, probaremos algunos resultados sobre la cantidad de elementos que poseen los conjuntos infinitos.

Conjuntos infinitos

Recordemos que para conjuntos $X$ y $Y$ decimos que $|X|\leq |Y|$ si existe una función inyectiva $f:X\to Y$.

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 la regla de la suma, tendríamos que $|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$, por vacuidad la función $\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, $f$ no puede ser suprayectiva y por lo tanto 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$ tales que $g(n_1)=g(n_2)$.

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

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

  • 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$ es un conjunto infinito, entonces para cada subconjunto finito $A$ de $X$, el conjunto $X\setminus A$ es infinito.
  • Retomando el ejercicio anterior, si $X$ es infinito y $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$ infinito, entonces alguno de los conjuntos $A$ o $B$ es infinito.

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.

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: Conjuntos numerables

Por Gabriela Hernández Aguilar

2 respuestas

Introducción

Ahora que hemos desarrollado una herramienta para comparar conjuntos que tienen más elementos que otros y hemos trabajado con conjuntos finitos e infinitos, hablaremos un poco más acerca de estos últimos, en especifico de aquellos que tienen la misma cantidad de elementos que el conjunto de los números naturales.

Conjuntos numerables

Definición. Sea $A$ un conjunto, decimos que $A$ es numerable si es equipotente a $\mathbb{N}$, es decir, si existe una función biyectiva $f:\mathbb{N}\to A$. De ser así, lo denotaremos con $|A|=|\mathbb{N}|$.

Ejemplo.

En la entrada de equipotencia vimos que existe una función biyectiva entre el conjunto de los números pares y los números naturales, por lo que podemos concluir que $$|\{2k:k\in \mathbb{N}\}|=|\mathbb{N}|.$$

$\square$

Ejemplo.

El conjunto $\mathbb{Z}$ de los números enteros es un conjunto numberable. (Puedes revisar la construcción del conjunto de los números enteros en el siguiente enlace: Álgebra Superior II: Construcción de los enteros y su suma).

Consideremos $f:\mathbb{N}\to \mathbb{Z}$ dada por:

$f(n)= \left\{ \begin{array}{lcc}
             \overline{(k,0)} &   si  & n=2k\ \text{para algún}\ k\in \mathbb{N} \\
             \\ \overline{(0,k+1)} &  si & x=2k+1\ \text{para algún}\ k\in\mathbb{N}
             \end{array}
   \right.$

Resulta que $f$ es biyectiva. En efecto, veamos primero que $f$ es inyectiva.

Sean $x_1, x_2\in \mathbb{N}$ tales que $f(x_1)=f(x_2)$. Tenemos los siguientes casos:

Caso 1. Si $x_1=2k$ y $x_2=2m$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(k,0)}$ y $f(x_2)=\overline{(m,0)}$ y así, $\overline{(k,0)}=\overline{(m,0)}$, por lo que $k+0=m+0$, es decir, $k=m$ y por lo tanto, $x_1=2k=2m=x_2$.

Caso 2. Si $x_1=2k+1$ y $x_2=2m+1$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(0,k+1)}$ y $f(x_2)=\overline{(0,m+1)}$ y así, $\overline{(0,k+1)}=\overline{(0,m+1)}$, por lo que $0+(m+1)=0+(k+1)$ y así $m=k$. Por tanto, $x_1=2k+1=2m+1=x_2$.

El caso en el que $x_1=2k$ y $x_2=2m+1$ no puede ocurrir, pues de lo contrario se tendría que $\overline{(k,0)}=\overline{(0,m+1)}$ por lo que $k+(m+1)=0+0=0$, lo cual es imposible. De manera análoga, no puede ocurrir que $x_1=2m+1$ y $x_2=2k$ para algunos $m,k\in\mathbb{N}$.

Por lo tanto, $f$ es inyectiva.

Ahora veamos que $f$ es suprayectiva. Sea $y\in \mathbb{Z}$, tenemos los siguientes casos:

Caso 1. Si $y\in \mathbb{Z}^+\cup\set{\overline{(0,0)}}$, entonces $y=\overline{(k,0)}$ para algún $k\in\mathbb{N}$. Así, para $x=2k\in\mathbb{N}$ se tiene $f(x)=y$.

Caso 2: Si $y\in \mathbb{Z}^{-}$, entonces $y=\overline{(0,k)}$ para algún $k\in\mathbb{N}\setminus\{0\}$. Luego, existe $k’\in\mathbb{N}$ tal que $s(k’)=k$, es decir, $k’+1=k$. Luego, tomando $x=2k’+1$ se tiene $f(x)=\overline{(0,k’+1)}=\overline{(0,k)}=y$.

Concluimos que $f$ es suprayectiva.

Por lo tanto, $f$ es biyectiva y así, $|\mathbb{N}|=|\mathbb{Z}|$.

$\square$

Ejemplo.

El conjunto $\mathbb{N}$ es equipotente al conjunto de los números racionales $\mathbb{Q}$. (Puedes revisar la construcción del conjunto de los números racionales en el siguiente enlace: Álgebra Superior II: Esbozo de construcción de los números racionales y reales).

De momento vamos a dar por hecho que para todo entero $z\in\mathbb{Z}^{+}$ existe un único entero $k\in\mathbb{Z}^{+}$, con $k>1$, y un único $i\in\{1,\ldots,k-1\}$ tal que $\overline{(z,1)}=\overline{(2i+(k-2)(k-1),2)}$. Teniendo esto en cuenta vamos a definir la siguiente función: $f:(\mathbb{Z}^{+}\cup\{0\})\times(\mathbb{Z}^{+}\cup\{0\})\to\mathbb{Q}^{+}$ por medio de $f(z,z’)=\left\{ \begin{array}{lcc}
\overline{(1,z’+1)} & si\ z=0\\
\\ \overline{(k,kz’+i)} & si\ z\in\mathbb{Z}^{+}\ y\ \overline{(z,1)}=\overline{(2i+(k-2)(k-1),2)}\ con\ k\in\mathbb{Z}^{+},\ k>1,\ e\ i\in\{1,\ldots,k-1\}
\end{array}
\right.$

Debido a la unicidad de $k$ e $i$ en el caso $z>0$, la función $f$ está bien definida. Veamos ahora que $f$ es una biyección.

Primero probaremos la inyectividad de $f$. Sean $(z_1,z’_1),(z_2,z’_2)\in(\mathbb{Z}^{+}\cup\{0\})\times(\mathbb{Z}\cup\{0\})$ tales que $f(z_1,z’_1)=f(z_2,z’_2)$. Si $z_1=0$, entonces, $f(z_1,z’_1)=\overline{(1,z’_1+1)}$ y así $\overline{(1,z’_1+1)}=f(z_2,z’_2)$. Luego, si $z_2\not=0$, entonces, existen únicos enteros $k\in\mathbb{Z}^{+}$, con $k>1$, e $i\in\{1,\ldots,k-1\}$ tales que $\overline{(z_2,1)}=\overline{(2i+(k-2)(k-1),2)}$, de modo que $f(z_2,z’_2)=\overline{(k,kz’_2+i)}$. En consecuencia, $\overline{(1,z’_1+1)}=\overline{(k,kz’_2+i)}$, por lo que $kz’_2+i=k(z’_1+1)$ y esto es imposible, pues la expresión de un número entero como $kq+r$ con $q\in\mathbb{Z}$ y $r\in\{0,1,\ldots,k-1\}$ es única. Por tanto, debe ser que $z_2=0$ y así $f(z_2,z’_2)=\overline{(1,z’_2+1)}$. Concluimos entonces que $\overline{(1,z’_1+1)}=\overline{(1,z’_2+1)}$ y por consiguiente $z’_1+1=z’_2+1$, es decir, $z’_1=z’_2$, lo que muestra que $(z_1,z’_1)=(z_2,z’_2)$. Supongamos ahora que $z’_1\not=0$. Luego, $z’_2\not=0$, pues de lo contrario obtenemos la misma contradicción que antes. Sean $k,k’\in\mathbb{Z}^{+}$ con $k,k’>1$ e $i\in\{1,\ldots,k-1\}$, $i’\in\{1,\ldots,k’-1\}$, tales que $\overline{(z_1,1)}=\overline{(2i+(k-2)(k-1),2)}$ y $\overline{(z_2,1)}=\overline{(2i’+(k’-2)(k’-1),2)}$. Entonces, $\overline{(k,kz’_1+i)}=f(z_1,z’_1)=f(z_2,z’_2)=\overline{(k’,k’z’_2+i’)}$ de donde $k(k’z’_2+i’)=k'(kz’_1+i)$.

Tarea moral

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

  1. Si un conjunto $A$ es numerable y $x\in A$ es un elemento arbitrario, ¿será cierto que $A\setminus\set{x}$ es también numerable?
  2. Sea $\mathbb{N}_0:=\mathbb{N}\setminus\set{0}$. Muestra que $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}_0$ dada por $f(n,m)=2^n(2m+1)$ es una función biyectiva.
  3. Utilizando el ejercicio anterior, muestra que si $A$ y $B$ son conjuntos numerables, entonces $A\times B$ también es numerable.
  4. Sean $A$ y $B$ conjuntos ajenos y numerables. Muestra que $A\cup B$ es numerable . ¿Y si los conjuntos $A$ y $B$ no son ajenos?

Más adelante…

En la siguiente entrada concluiremos el contenido acerca de cardinalidad de conjuntos infinitos. Daremos cierre a esta unidad con el tema de aritmética cardinal.

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: Conjuntos finitos (parte II)

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada daremos continuación al tema de conjuntos finitos. Probaremos más resultados que se satisfacen para los conjuntos finitos y veremos cuál es la cardinalidad del conjunto potencia de un conjunto finito dado.

Conjuntos finitos y contención

Teorema. Sean $A$ y $B$ conjuntos tales que $B$ es finito. Si $A\subseteq B$, entonces $A$ es finito. Más aún, $|A|\leq |B|$.

Demostración. (Por inducción sobre $|B|$).

Base de inducción. Supongamos que $|B|=0$. Entonces $B=\emptyset$, por lo que $A=\emptyset$ y así, $A$ es finito y $0=|A|\leq |B|=0$.

Hipótesis de inducción. Supongamos que para $|X|=n$ se cumple que si $Y\subseteq X$, entonces $Y$ es finito y $|Y|\leq |X|$.

Paso inductivo. Sea $B$ un conjunto finito tal que $|B|=n+1$. Veamos que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.

Si $A=B$, entonces $A$ es finito y $|A|=|B|\leq|B|$.

Si $A\not=B$, existe $x\in B\setminus A$. Luego, $A\subseteq B\setminus\set{x}$ y como $|B\setminus \set{x}|=n$, tenemos por hipótesis de inducción que $A$ es finito y $|A|\leq |B\setminus \set{x}|=n\leq n+1 =|B|$. En cualquier caso, $A$ es finito y $|A|\leq |B|$.

$\square$

Cardinalidad del conjunto potencia

Como parte de los ejercicios de la unidad de números naturales, definimos la operación binaria potencia en $\mathbb{N}$, que intuitivamente se realiza como sigue $m^{n}=\underbrace{m\cdot m\cdots m}_{n-veces}$.

Teorema. Si $X$ es finito, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$.

Demostración. (Por inducción sobre $|X|$).

Base de inducción. Si $|X|=0$, entonces $X=\emptyset$ y así, $\mathcal{P}(X)=\set{\emptyset}$, por lo que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=1=2^0=2^{|X|}$.

Hipótesis de inducción. Supongamos que si $A$ es finito tal que $|A|=n$, entonces $\mathcal{P}(A)$ es finito y $|\mathcal{P}(A)|= 2^{|A|}$.

Paso inductivo. Sea $X$ un conjunto finito tal que $|X|=n+1$. Supongamos que $X=\set{X_1,X_2, \dots, X_n, X_{n+1}}$. Luego, consideremos $X’=X\setminus \set{X_1}$, entonces $|X’|=n$ y así, $|\mathcal{P}(X’)|=2^{|X’|}$. Veamos que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$. Para ello veamos primero que $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Procederemos por doble contención.

$\subseteq$) Sea $Y\in \mathcal{P}(X)$, entonces $Y\subseteq X$. Si $X_1\in Y$, entonces $Y\in \set{Z\in \mathcal{P}(X): X_1\in Z}$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Si $X_1\notin Y$, entonces $Y\subseteq X\setminus \set{X_1}=X’$, por lo que $Y\in \mathcal{P}(X’)$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Concluimos que $\mathcal{P}(X)\subseteq \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

$\supseteq$) Sea $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Caso 1: Si $Y\in \mathcal{P}(X’)$, entonces $Y\subseteq X’$ y como $X’\subseteq X$, entonces $Y\subseteq X$ y así, $Y\in \mathcal{P}(X)$.

Caso 2: Si $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$, entonces $Y\in \mathcal{P}(X)$.

Por lo tanto, $\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}\subseteq \mathcal{P}(X)$.

Así, $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Luego, por hipótesis de inducción tenemos que $\mathcal{P}(X’)$ es finito y $|\mathcal{P}(X’)|=2^n$.

Resulta que $\set{Z\in \mathcal{P}(X)}$ es finito; más aún, afirmamos que $|\set{Z\in \mathcal{P}(X):X_1\in Z}|=|\mathcal{P}(X’)|$. Para probar este último hecho estableceremos una biyección entre $\mathcal{P}(X’)$ y $\set{Z\in \mathcal{P}(X):X_1\in Z}$.

Consideremos $f:\mathcal{P}(X’)\to \set{Z\in \mathcal{P}(X):X_1\in Z}$ dada por $f(Y)=Y\cup \set{X_1}$. Veamos que $f$ es biyectiva.

Inyectividad. Sean $A,B\in \mathcal{P}(X’)$ tales que $f(A)=f(B)$, esto es $A\cup \set{X_1}=B\cup \set{X_1}$. Luego, $A$ y $\set{X_1}$ son ajenos pues $A\subseteq X’=X\setminus \set{X_1}$; asimismo, $B$ y $\set{X_1}$ son ajenos pues $B\subseteq X’=X\setminus \set{X_1}$. De este modo, debe ocurrir que $A=B$. Por lo tanto, $f$ es inyectiva.

Suprayectividad. Sea $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$. Entonces $Y\subseteq X$ y $X_1\in Y$.

Veamos que existe $W\subseteq X\setminus \set{X_1}$ tal que $f(W)=Y$. Consideremos $W=Y\setminus \set{X_1}$. Tenemos que $f(W)=(Y\setminus \set{X_1})\cup \set{X_1}=Y$. Por lo tanto, $f$ es suprayectiva.

Así, $f$ es biyectiva y $|\set{Z\in \mathcal{P}(X): X_1\in Z}|=2^n$.

Por lo tanto, usando regla de la suma, tenemos que $|\mathcal{P}(X)|=|\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X)}|= 2^n+2^n=2(2^n)= 2^{n+1}$. Esto concluye nuestra prueba.

$\square$

Tarea moral

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

  1. Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
  2. Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
  3. Sean $A$ y $B$ conjuntos finitos. Sea $\mathcal{F}$ el conjunto de todas las posibles funciones de $A$ en $B$. Muestra que $\mathcal{F}$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$?
  4. Sean $A$ y $B$ conjuntos finitos. Muestra que $A\times B$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$?
  5. Demuestra que para cualquier número natural $n$ se tiene que $n<2^n$.

Más adelante…

En la siguiente entrada abordaremos a los conjuntos infinitos. Esto nos acercará a una discusión importante sobre qué son en realidad los cardinales en teoría de los conuntos.

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: Conjuntos finitos

Por Gabriela Hernández Aguilar

2 respuestas

Introducción

Ahora que sabemos el concepto de equipotencia, en esta entrada definiremos qué son los conjuntos finitos y hablaremos de ellos. A grandes rasgos, serán aquellos que tengan tantos elementos como alguno de los números naturales que ya definimos. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.

Conjuntos finitos

Definición. Sea $X$ un conjunto. Decimos que $X$ es un conjunto finito si y sólo si existe $n\in \mathbb{N}$ tal que $X\sim n$.

Ejemplo.

El conjunto $\emptyset$ es finito, pues existe una biyección entre el conjunto $\emptyset$ y $0$; a saber, la función vacía.

$\square$

Ejemplo.

El conjunto $A=\set{2,4,6,8,10}$ es finito pues $f:A\to 5=\set{0,1,2,3,4}$ definida por medio de $f=\set{(2,0), (4,1), (6,2), (8,3), (10, 4)}$ es una función biyectiva.

$\square$

Principio de las casillas y unicidad de natural equipotente

La definición dice que $X$ es finito cuando hay un natural al que es equipotente pero, ¿este natural es único? La respuesta es que sí. Demostraremos esto a través de algunos resultados auxiliares, que a la vez nos permitirán enunciar y demostrar un par de versiones del principio de las casillas.

Lema (principio de las casillas). No existe ninguna función inyectiva $f:n+1\to n$.

Demostración. Probaremos el resultado por inducción. Para $n=0$ el resultado es cierto pues no existe ninguna función (inyectiva o no) $f:1\to 0$, pues $0=\emptyset$ y $1\neq \emptyset$.

Supongamos que el resultado es cierto para el natural $n$, es decir, que no existe ninguna función inyectiva $f:n+1\to n$. Veremos que no existe ninguna función inyectiva $g:n+2\to n+1$. En busca de una contradicción, supongamos que sí existe tal $g$.

Si $Im(g)\subseteq n$, entonces la restricción de $g$ a $n+1$ es una función inyectiva de $n+1$ en $n$, lo que contradice la hipótesis inductiva. Así, existe un natural $k\leq n+2$ tal que $g(k)=n+1$. Si $k=n+2$, entonces $g\setminus\{(n+2,n+1)\}$ es una función inyectiva de $n+1$ en $n$, que contradice la hipótesis inductiva. Así, $k\leq n+1$. Como $g$ es inyectiva, $g(n+2)=l\neq k$. Pero entonces, $$(g\setminus\{(n+2,l),(k,n+1)\})\cup \{(k,l)\}$$ es una función inyectiva de $n+1$ en $n$, dando una contradicción final a la hipótesis inductiva.

$\square$

Usualmente el principio de las casillas se piensa así: si $f:n+1\to n$ es una función, entonces deben existir $x,y\in n+1$ tales que $f(x)=f(y)$. En términos intuitivos, «si colocamos $n+1$ pelotas en $n$ casillas, entonces por lo menos en alguna casilla quedaron por lo menos dos pelotas». Si son todavía más pelotas, el resultado es cierto, como lo indica el siguiente corolario de manera formal.

Corolario. Sean $m,n$ naturales con $n<m$. Entonces no existen funciones inyectivas $f:m\to n$.

Demostración. Recordemos que si $n<m$, entonces $n\subset m$ y de hecho $n+1\subseteq m$. Si existiera una función inyectiva $f:m\to n$, entonces su restricción a $n+1$ sería una función inyectiva de $n+1$ en $n$, contradiciendo el principio de las casillas.

$\square$

En particular, si $X$ es un conjunto finito, entonces debe haber un único natural $n$ al cual es equipotente. Si hubiera dos distintos $m$ y $n$, sin pérdida de generalidad $n<m$. Tendríamos entonces que $m\sim X$ y $X\sim n$, pero entonces $m\sim n$ y existiría una función biyectiva de $m$ a $n$. En particular, sería una función inyectiva, lo cual contradice el corolario anterior.

Con esto en mente, es conveniente añadir la siguiente notación para conjuntos finitos.

Definición. Sea $X$ un conjunto finito y $n\in\mathbb{N}$ el natural tal que $X\sim n$. Definimos el cardinal de $X$ como $n$ y lo denotaremos por $|X|=n$.

La regla de la suma

La regla de la suma es un resultado muy versátil que nos permite entender exactamente la cardinalidad de la unión de dos conjuntos finitos disjuntos. Además, este resultado motivará posteriormente la definición de suma de cardinales infinitos, cuando hablemos de ellos.

Teorema (regla de la suma). Si $X$ y $Y$ son conjuntos finitos y disjuntos, con $|X|=m$ y $|Y|=n$, entonces $X\cup Y$ es finito y $|X\cup Y|=m+n$.

Demostración. Sean $f:X\to m$ y $g:Y\to n$ biyecciones. Definimos la función $h:X\cup Y \to m+n$ como sigue: $$h(x)= \begin{cases} f(x) & \text{si $x\in X$}\\ m+g(x) & \text{si $x\in Y$.}\end{cases}$$

Como $X$ y $Y$ son disjuntos, $h$ es una función de dominio $X\cup Y$. Como $f(x)\leq m-1 \leq m+n-1$ y $m+g(x)\leq m+ n-1$, entonces la imagen de $h$ está contenida en $m+n$. Afirmamos que $h$ es una biyección de $X\cup Y$ en $m+n$.

Veamos que $h$ es inyectiva. Supongamos que $x,y$ en $X\cup Y$ son tales que $h(x)=h(y)$. Es imposible que $x\in X$ y $y\in Y$ pues en ese caso $h(x)=f(x)\leq m-1$ y $h(y)=m+g(y)\geq m$. Análogamente, $x\in Y$ y $y\in X$ es imposible. Así, o bien ambos $x$ y $y$ están en $X$, o bien ambos están en $Y$. Si están en $X$, tenemos $f(x)=h(x)=h(y)=f(y)$ y como $f$ es inyectiva, obtenemos $x=y$. Si están en $Y$, tenemos $m+g(x)=h(x)=h(y)=m+g(y)$. Por ley de cancelación de la suma, se tiene $g(x)=g(y)$. Y por inyectividad de $g$ se tendría $x=y$.

Ahora, veamos que $h$ es suprayectiva. Tomemos $k\in m+n$. Si $k\leq m-1$, entonces como $f$ es suprayectiva, existe $x\in X$ tal que $f(x)=k$ y entonces $h(x)=f(x)=k$. Si $k\geq m$, entonces existe $l$ tal que $m+l=k$. Dicha $l$ debe cumplir $l\leq n-1$, pues en otro caso $m+n-1\geq k=m+l \geq m+n$, lo cual sería una contradicción. Como $g$ es biyectiva, existe $r$ tal que $g(r)=l$. Y entonces $h(r)=m+g(r)=m+l=k$.

Como $h$ es inyectiva y suprayectiva, obtenemos que es biyectiva, como queríamos.

$\square$

La regla de la suma tiene varios corolarios como consecuencia.

Corolario. Si $X$ es finito y $y\notin X$, entonces $X\cup\set{y}$ es finito y $|X\cup \set{y}|= |X|+1$.

Demostración. Aplicamos la regla de la suma y $|\set{y}|=1$.

$\square$

Corolario (principio de inclusión-exclusión). Sean $X$ y $Y$ conjuntos finitos. Entonces $X\cup Y$ es finito. Más aún, $|X\cup Y| + |X\cap Y| = |X| + |Y|$.

Demostración. Se tiene que $X=(X\cap Y) \cup (X\setminus Y)$ y que $(X\cap Y) \cap (X\setminus Y)=\emptyset$ (verifica ambas cosas). Así, por regla de la suma se tiene que $$|X|=|X\cap Y| + |X\setminus Y|.$$

De manera similar, se tiene que $X\cup Y = Y \cup (X\setminus Y)$ con $Y\cap (X\setminus Y)=\emptyset$ (verifíca ambas cosas). Así, por la regla de la suma se tiene que $$|Y| + |X\setminus Y| = |X\cup Y|.$$

Sumando las dos igualdades que obtuvimos, tenemos que $$|X|+|Y|+|X\setminus Y| = |X\cap Y| + |X\cup Y| + |X\setminus Y|.$$

Aplicando la ley de cancelación para eliminar $|X\setminus Y|$, obtenemos el resultado deseado.

$\square$

Corolario. Sean $X$ y $Y$ conjuntos finitos, entonces $X\cup Y$ es finito. Más aún, $|X\cup Y|\leq |X|+|Y|$.

Demostración. Por el principio de inclusión-exclusión, $$|X\cup Y| \leq |X\cup Y| + |X\cap Y| = |X| + |Y|.$$

$\square$

La regla de la suma por sí misma es muy versátil y tiene una versión más general.

Teorema (regla de la suma generalizada). Sea $n$ un natural y sean $A_1,\ldots,A_n$ conjuntos finitos y tales que $A_j\cap A_i=\emptyset$ para cualesquiera $i,j$ en $\{1,\ldots,n\}$. Entonces $A:=\bigcup \{A_i: i\in \{1,\ldots,n\}\}$ es finito.

En los ejercicios tendrás que probar esta versión.

Un último resultado que demostraremos es el siguiente.

Teorema. Si $\mathcal{F}$ es finito y para cualquier $X\in \mathcal{F}$ pasa que $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.

Demostración. (Por inducción sobre la cardinalidad de $\mathcal{F}$).

Base de inducción. Si $|\mathcal{F}|=0$, entonces $\mathcal{F}=\emptyset$. Así, se cumple por vacuidad, que si cualquier $X\in \mathcal{F}$ es finito, entonces $\bigcup \mathcal{F}$ es finito. Más aún, $\bigcup \mathcal{F}=\emptyset$ y $|\bigcup \mathcal{F}|=0$.

Hipótesis de inducción. Supongamos que si $|\mathcal{G}|=n$ y para cualquier $X\in \mathcal{G}$, $X$ es finito, se cumple que $\bigcup\mathcal{G}$ es finito.

Paso inductivo. Veamos que si $|\mathcal{F}|=n+1$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.

Como $|\mathcal{F}|$ es distinto de $0$, tomeos $X\in\mathcal{F}$ y definamos $\mathcal{F’}:=\mathcal{F}\setminus \{X\}$. Tenemos que cualquier elemento de $\mathcal{F’}$ es finito y que $|\mathcal{F}’|=n$, por lo que por hipótesis de inducción se cumple que $\bigcup\mathcal{F’}$ es finito.

Ahora, por el corolario del principio de inclusión-exclusión, tenemos que $\bigcup\mathcal{F}’\cup X$ es finito.

Afirmación. $\bigcup\mathcal{F}=\bigcup\mathcal{F}’\cup X$.

Demostración de la afirmación.

Sea $x\in\bigcup \mathcal{F}$, entonces existe $Y\in \mathcal{F}$ tal que $x\in Y$.

Caso 1: Si $Y=X$, entonces $x\in X$ y por lo tanto, $x\in \bigcup\mathcal{F}’\cup X$.

Caso 2: Si $Y\not=X$, entonces $Y\in \mathcal{F}’$ y así, $x\in \bigcup\mathcal{F}’$.

Los casos anteriores muestran que $\bigcup\mathcal{F}\subseteq \bigcup\mathcal{F}’\cup X$.

Ahora, como $\mathcal{F’}\subseteq\mathcal{F}$ y $X\in\mathcal{F}$, entonces $\bigcup\mathcal{F’}\cup X\subseteq\bigcup\mathcal{F}$.

Así, $\bigcup \mathcal{F}=\bigcup\mathcal{F}’\cup X$. Por lo tanto, $\bigcup\mathcal{F}$ es finito. Lo que concluye nuestra prueba.

$\square$

,

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección.

  1. Sea $X$ un conjunto finito y $x\in X$. Si $|X|=n+1$, demuestra que $X\setminus\set{x}$ es finito y que $|X\setminus\set{x}|=n$.
  2. Sea $X$ es un conjunto finito. Prueba que si $A\subseteq X$, entonces, $A$ es un conjunto finito.
  3. Demuestra por inducción la regla de la suma generalizada. Como sugerencia, uno de los pasos intermedios es que enuncies formalmente y demustres que para todo natural $n$ se cumple que $(A_1\cup \ldots \cup A_n) \cap B = (A_1 \cap B) \cup \ldots \cup (A_n \cap B)$.

Más adelante…

En la siguiente entrada continuaremos con el contenido de esta sección, probaremos más propiedades sobre los conjuntos finitos y a su vez hablaremos acerca de la cardinalidad del conjunto potencia.

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»