Introducción

En esta unidad daremos un par de definiciones que formalizarán la idea de que un conjunto sea más grande que otro, es decir, vamos a definir y formalizar la noción de que un conjunto tenga más elementos o la misma cantidad que otro, aún cuando no definamos formalmente qué es lo que entenderemos por cantidad de elementos de un conjunto.

Equipotencia

Definición. Sean $A$ y $B$ conjuntos. Decimos que $A$ es equipotente a $B$ si existe una función biyectiva $f:A\to B$. Denotaremos $A$ es equipotente a $B$ como $A\sim B$ o bien como $|A|=|B|$.

Si podemos establecer una función biyectiva entre $A$ y $B$, diremos que tienen la misma cantidad de elementos.

Ejemplo.

Sea $A=\mathbb{N}$ y $B=\set{2k:\ k\in\mathbb{N}}$.

Afirmación. $A$ y $B$ son equipotentes.

Demostración de la afirmación.

Sea $f:\mathbb{N}\to B$ la función dada por $f(n)=2n$. Veamos que $f$ es biyectiva.

1. Inyectividad.
   Sean $x,y\in \mathbb{N}$ tales que $f(x)= f(y)$, esto es $2x=2y$. Luego, por ley de la cancelación para el producto tenemos que $x=y$ y, por lo tanto, $f$ es inyectiva.
2. Suprayectividad.
   Si $y\in B$, entonces $y=2k$ para algún $k\in \mathbb{N}$. Así, existe $k\in \mathbb{N}$ tal que $f(k)=2k=y$ y, por consiguiente, $f$ es suprayectiva.

Por lo tanto, $f$ es biyectiva, de modo que $A\sim B$.

$\square$

El siguiente teorema seguro te recordará algunas cosas que discutimos cuando hablamos acerca de relaciones de equivalencia.

Teorema. Sean $A$, $B$ y $C$ conjuntos. Entonces se satisfacen los siguientes enunciados:

1. $A$ es equipotente a $A$.
2. Si $A$ es equipotente a $B$, entonces $B$ es equipotente a $A$.
3. Si $A$ es equipotente a $B$ y $B$ es equipotente a $C$, entonces $A$ es equipotente a $C$.

Demostración.

1. La función $Id_A$ es una función biyectiva, por lo que podemos concluir que $A\sim A$.
2. Supongamos que $A\sim B$, entonces existe $f:A\to B$ biyectiva. Luego, $f^{-1}:B\to A$ es una función biyectiva y por lo tanto, $B\sim A$.
3. Supongamos que $A\sim B$ y $B\sim C$, esto es, existe $f:A\to B$ biyectiva y $g:B\to C$ biyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son biyectivas, entonces $g\circ f$ es biyectiva.
   Así, $A\sim C$.

$\square$

De esta manera, la equipotencia se comporta «como una relación de equivalencia». Pero, estrictamente hablando, no es una relación de equivalencia, pues dicha relación tendría que darse en la colección de todos los conjuntos, pero ya sabemos que esta colección no es un conjunto.

Por la simetría, en vez de decir «$A$ es equipontente a $B$» podemos simplemente decir que $A$ y $B$ son equipotentes.

Dominancia

Hemos visto que para que un conjunto sea equipotente a otro se requiere que exista una función biyectiva. Esto «se comporta» como una relación de equivalencia. ¿Hay una noción que se comporte como un orden parcial o un orden estricto? Sí. La siguiente definición establece esta idea.

Definición. Sean $A$ y $B$ conjuntos. Decimos que $B$ domina a $A$ si existe $f: A\to B$ tal que $f$ es inyectiva, pero no existe una función biyectiva de $A$ en $B$. Lo denotaremos como $|A|\preceq|B|$.

Ejemplo.

Sean $A=\set{1,2,3}$ y $B=\mathbb{N}$. Tenemos que $|A|\preceq|B|$ pues $f=\set{(1,1), (2,2), (3,3)}$ es iuna función inyectiva. Sin embargo, no existe $h:A\to B$ tal que $h$ sea suprayectiva.

$\square$

El siguiente teorema formaliza la idea de que $\preceq$ «se comporta» como un orden parcial.

Teorema. Sean $A$, $B$ y $C$ conjuntos. Entonces, se satisfacen los siguientes enunciados:

1. $A\preceq A$.
2. Si $A\preceq B$ y $B\preceq C$, entonces $A\preceq C$.

Demostración.

1. La función $Id_A$ es una función biyectiva, en paticular es una función inyectiva por lo que podemos concluir que $A\preceq A$.
2. Supongamos que $A\preceq B$ y $B\preceq C$, esto es, existe $f:A\to B$ inyectiva y $g:B\to C$ inyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son inyectivas, entonces $g\circ f$ es inyectiva. Así, $A\preceq C$.

$\square$

A continuación probaremos un teorema importante en este curso. Dicho resultado muestra que, dado un conjunto $A$, no existe una función biyectiva de $A$ en el conjunto potencia de $A$, $\mathcal{P}(A)$. Como consecuencia de este teorema, obtenemos que existen conjuntos infinitos que no son equipotentes. Es cierto que no hemos dicho qué es un conjunto infinito, pero de momento puedes entenderlo (de manera informal) como un conjunto que tiene un subconjunto con $n$ elementos para cada $n\in\mathbb{N}$.

Teorema de Cantor. Sea $A$ un conjunto, entonces $A\preceq \mathcal{P}(A)$ pero $A\not\sim \mathcal{P}(A)$.

Demostración.

Sea $A$ un conjunto. Si $A=\emptyset$, entonces, $\emptyset$ es una función inyectiva de $A$ en $\mathcal{P}(A)$, por lo que $A\preceq\mathcal{P}(A)$. Supongamos ahora que $A\not=\emptyset$. Luego, $f:A\to \mathcal{P}(A)$ dada por $f(a)=\set{a}$ es una función inyectiva y, por tanto, $A\preceq\mathcal{P}(A)$.

Veamos ahora que no existe una biyección entre $A$ y $\mathcal{P}(A)$. Sea $f:A\to\mathcal{P}(A)$ una función. Para mostrar que $f$ no es una biyección, veamos que no es sobreyectiva. Sea $B=\{x\in A: x\notin f(x)\}$. El conjunto $B$ es un elemento en $\mathcal{P}(A)$, pero no es un elemento en la imagen de $f$. En efecto, supongamos que existe $y\in A$ tal que $f(y)=B$. Dado que $y\in A=B\cup(A\setminus B)$, entonces, $y\in B$ o $y\in A\setminus B$. Si $y\in B$, entonces, $y\notin f(y)=B$, de modo que $y\in B$ y $y\notin B$, lo cual es imposible. Ahora bien, si $y\in A\setminus B$, entonces, $y\notin B=f(y)$ y por consiguiente $y\in B$, lo cual, nuevamente, es imposible. Por lo tanto, $B$ no está en la imagen de $f$ y, en consecuencia, $f$ no es sobreyectiva.

$\square$

Lo siguiente que podemos probar es que si $A$ y $B$ son conjuntos tales que $A\preceq B$ y $B\preceq A$, entonces $A\sim B$. Este resultado corresponde al teorema de Cantor-Schröder-Bernstein que demostraremos en la próxima entrada.  

Tarea moral

Los siguientes ejercicios te permitirán aprender más resultados acerca de equipotencia y dominancia.

1. Sean $n$ y $m$ números naturales. Muestra que $n\leq m$ si y sólo si $n \preceq m$.
2. Demuestra que si $n$ y $m$ son números naturales distintos, entonces, o bien $n$ domina a $m$ o bien $m$ domina a $n$.
3. Demuestra que si $A\subseteq B$, entonces $A\preceq B$.
4. Enuncia formalmente un resultado que diga por qué la noción de «domina a» se comporta como un orden estricto.
5. De entre las siguientes afirmaciones, decide cuáles son siempre verdaderas y para cuáles hay contraejemplos.
   • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\cup B|=|C\cup D|$.
   • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\cap B|=|C\cap D|$.
   • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\times B|=|C\times D|$.

Más adelante…

En la siguiente entrada probaremos el teorema de Cantor-Schröder-Bernstein. Este teorema nos será de gran utilidad para averiguar si dos conjuntos tienen la misma cantidad de elementos sin tener que exhibir una función biyectiva, tan sólo bastará con dar dos funciones inyectivas.

Entradas relacionadas

• Ir a Teoría de los Conjuntos I
• Entrada anterior: Teoría de los Conjuntos I: Producto en los naturales
• Siguiente entrada: Teoría de los Conjuntos I: Teorema de Cantor-Schröder-Bernstein 

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»