Archivo de la etiqueta: lema del punto fijo

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 ↩︎