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

Por Gabriela Hernández Aguilar

Introducción

En esta entrada probaremos que dados dos conjuntos $A$ y $B$, tales que $A\lesssim B$ y $B\lesssim 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-Bernstein

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\lesssim B$ y $B\lesssim A$, entonces $A\sim B$.

Demostración:

Supongamos que $A\lesssim B$ y $B\lesssim 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{x\in \mathbb{N}: x=2k\ \text{con}\ 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}$?
  3. Demuestra que el conjunto de los racionales mayores o iguales a cero es equipotente al conjunto de los naturales. (Ve quienés son los racionales en el siguiente enlace Álgebra Superior II: Esbozo de construcción de los números racionales y reales).
  4. Demuestra que el conjunto de los números enteros es equipotente al conjunto de los naturales. (Ve quienés son los enteros en el siguiente enlace Álgebra Superior II: Construcción de los enteros y su suma).

Más adelante…

En la siguiente entrada definiremos qué es un conjunto finito y hablaremos un poco sobre qué queremos que sea el 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»

3 comentarios en “Teoría de los Conjuntos I: Teorema de Cantor-Schröder-Bernstein 

  1. Juan Luis

    hola Leo: soy un nuevo jubilado que después de 50 años vuelve a ser estudiante. Estoy o vuelvo a estar enganchado con las Mates. No dudé en inscribirme en tu blog. Esta muy bueno. Desde hace un par de años he hecho un vuelo de reconocimiento y ampliación de los mismos por el cálculo, la geometría o las geometrías, trigonometría y algébra. En general encantado con todo, y todo por aprender. Pero me cuesta, y me hace recordar mi época de estudiante, las bases, la fundamentación, la teoría, pura y dura. Me animo siguiéndote que me ayudes.
    muchas gracias.

    Juan Luis

    Responder

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.