Teorema de Cantor-Bernstein-Schroeder

Em teoria de conjuntos, o Teorema de Cantor-Bernstein-Schroeder, assim chamado em homenagem a Georg Cantor, Felix Bernstein e Ernst Schröder, estabelece que se existem funções injetivas f : A → B e g : B → A entre os conjuntos A e B, então existe uma função bijetiva h : A → B. Em termos da cardinalidade dos dois conjuntos, isso significa que se |A| ≤ |B| e |B| ≤ |A|, então |A| = |B|; A e B são ditos "equipolentes". Essa é obviamente uma propriedade muito útil para a ordenação de números cardinais.

Este teorema não depende do axioma da escolha.

Demonstração

Esta demonstração faz uso do conjunto dos números naturais, cuja existência é um dos axiomas da Teoria dos Conjuntos (o axioma do infinito)

Para cada $n\in \mathbb {N}$ definimos $h_{n}:A\to A$, por $h_{n}=(g\circ f)^{n}$, composição de $n$fatores iguais a $g\circ f$. Observamos que $h_{0}=Id_{A}$. Note que o fato de $g$ e $f$ serem injetivas implica a injetividade de $h_{n}$.

Agora consideramos $X\subset A$, dado por

$X=\{a\in A;{\text{ existe }}n\in \mathbb {N} {\mbox{ com }}h_{n}^{-1}(a)\not \in {\text{Im}}(g)\}$.

Note que se $a\notin {\text{Im}}(g)$, então tomando $n=0$ segue que $h_{0}^{-1}(a)\not \in {\text{Im}}(g)$, ou seja, $a\in X$. Equivalentemente, se $a\not \in X$ temos que $a\in {\text{Im}}(g)$.

Por outro lado, observamos que dado $b\in B$, se tivermos $g(b)\in X$, então $b\in {\text{Im}}(f)$ e ocorre $f^{-1}(b)\in X$. De fato, se $g(b)\in X$ então existe $n\in \mathbb {N}$ tal que $h_{n}^{-1}(g(b))\not \in {\text{Im}}(g)$. É claro que $n\neq 0$ e nesse caso podemos escrever

$h_{n}^{-1}(g(b))=((g\circ f)\circ h_{n-1})^{-1}(g(b))=h_{n-1}^{-1}((g\circ f)^{-1}(g(b)))$

$=h_{n-1}^{-1}(f^{-1}(g^{-1}(g(b))))=h_{n-1}^{-1}(f^{-1}(b))$.

Logo $h_{n-1}^{-1}(f^{-1}(b))\not \in Im(g)$, donde segue que $f^{-1}(b)\in X$.

Para concluir definimos $H:A\to B$ pondo $H(a)=f(a)$ se $a\in X$ e $H(a)=g^{-1}(a)$ se $a\not \in X$. Note que $H$ está bem definida, pois g é injetiva e se $a\not \in X$ então $a\in {\text{Im}}(g)$, como já observamos. Ademais, $H$ é injetiva, haja vista que dados $a,a'\in A$ temos as seguintes possibilidades: $a,a'\in X$ (os dois estão em X); $a,a'\not \in X$ (os dois estão no complementar de X) ou $a\in X,a'\not \in X$ (um está em X e outro fora). Nos dois primeiros casos a igualdade $H(a)=H(a')$ implica $a'=a$, devido à injetividade de $f$ e de $g$. No último, tal igualdade implicaria $f(a)=g^{-1}(a')$ de onde teríamos $a=f^{-1}(g^{-1}(a'))=h_{1}^{-1}(a')$. Porém, como $a\in X$ existe $n\in \mathbb {N}$ tal que $h_{n}^{-1}(a)\not \in {\text{Im}}(g)$. Logo, $h_{n}^{-1}(h_{1}^{-1}(a'))\not \in {\text{Im}}(g)$, ou seja, $h_{n+1}^{-1}(a')\not \in {\text{Im}}(g)$. Isso implica $a'\in X$, o que é uma contradição. Portanto, isso conclui a verificação da injetividade de H.

Por fim, dado $b\in B$ temos duas possibilidades: $g(b)\not \in X$ ou $g(b)\in X$. No primeiro caso, temos que $H(g(b))=g^{-1}(g(b))=b$ e no segundo caso, como foi observado, teremos que $f^{-1}(b)\in X$ e daí, $H(f^{-1}(b))=f(f^{-1}(b))=b$. Portanto, $H$ trata-se de uma bijeção.

Demonstração de Banach

Stefan Banach observou que o que a demonstração acima faz é decompor cada conjuntos A e B em duas partes disjuntas, de forma que a função f transforma (bijetivamente) uma parte de A em uma parte de B, e g^-1 transforma (bijetivamente) a outra parte de A na outra parte de B.

Mais precisamente:

Sejam A e B conjuntos, $f:A\to B\,$ uma função injetiva e $G:S\subseteq A\to B\,$ uma função sobrejetiva. Então é possível particionar $A=A_{1}\cup A_{2}\,$, $B=B_{1}\cup B_{2}\,$, com $A_{1}\cap A_{2}=B_{1}\cap B_{2}=\varnothing \,$ e de forma que f e G quando restritas, respectivamente, a A₁ e A₂ sejam bijeções, respectivamente, com B₁ e B₂.

O teorema de Cantor-Bernstein-Schroeder segue imediatamente como corolário, porque sendo $g:B\to A\,$ injetiva, então $G:g(A)\to B\,$ é a função bijetiva definida pela injetividade de g.

A demostração encontra-se na referência

Links externos

• Proofs from THE BOOK, p. 90. ISBN 3540404600
• «Proof of the Bernstein–Schroeder theorem». no PlanetMath 
• «MathPath». - Explicação e notas sobre a prova do teorema de Cantor-Bernstein 
• Àlgebra para Graduação, Lang, S. Ed. Ciência moderna