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)^[1]

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

Agora consideramos ${\displaystyle X\subset A}$, dado por

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

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

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

${\displaystyle 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)))}$

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

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

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

Por fim, dado ${\displaystyle b\in B}$ temos duas possibilidades: ${\displaystyle g(b)\not \in X}$ ou ${\displaystyle g(b)\in X}$. No primeiro caso, temos que ${\displaystyle H(g(b))=g^{-1}(g(b))=b}$ e no segundo caso, como foi observado, teremos que ${\displaystyle f^{-1}(b)\in X}$ e daí, ${\displaystyle H(f^{-1}(b))=f(f^{-1}(b))=b}$. Portanto, ${\displaystyle 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.^[2]

Mais precisamente:

Sejam A e B conjuntos, ${\displaystyle f:A\to B\,}$ uma função injetiva e ${\displaystyle G:S\subseteq A\to B\,}$ uma função sobrejetiva. Então é possível particionar ${\displaystyle A=A_{1}\cup A_{2}\,}$, ${\displaystyle B=B_{1}\cup B_{2}\,}$, com ${\displaystyle 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 ${\displaystyle g:B\to A\,}$ injetiva, então ${\displaystyle G:g(A)\to B\,}$ é a função bijetiva definida pela injetividade de g.

A demostração encontra-se na referência^[2]

Referências

1. Ver esta demonstração, exemplificada com gráficos
2. Banach's proof of the Cantor-Bernstein theorem

Ligações externas

• 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

• Portal da matemática