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=I{d}_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}\text{ com }{h}_n^{-1}(a)\in ̸\text{Im}(g)\}$.

Note que se $a\notin \text{Im}(g)$, então tomando $n=0$ segue que $h_0^{-1}(a)\in ̸\text{Im}(g)$, ou seja, $a\in X$. Equivalentemente, se $a\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))\in ̸\text{Im}(g)$. É claro que $n\ne 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))\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\in ̸X$. Note que $H$ está bem definida, pois g é injetiva e se $a\in ̸X$ então $a\in \text{Im}(g)$, como já observamos. Ademais, $H$ é injetiva, haja vista que dados $a,a^{\prime }\in A$ temos as seguintes possibilidades: $a,a^{\prime }\in X$ (os dois estão em X); $a,a^{\prime }\in ̸X$ (os dois estão no complementar de X) ou $a\in X,a^{\prime }\in ̸X$ (um está em X e outro fora). Nos dois primeiros casos a igualdade $H(a)=H(a^{\prime })$ implica $a^{\prime }=a$, devido à injetividade de $f$ e de $g$. No último, tal igualdade implicaria $f(a)=g^{-1}(a^{\prime })$ de onde teríamos $a=f^{-1}(g^{-1}(a^{\prime }))=h_1^{-1}(a^{\prime })$. Porém, como $a\in X$ existe $n\in \mathbb{N}$ tal que $h_n^{-1}(a)\in ̸\text{Im}(g)$. Logo, $h_n^{-1}(h_1^{-1}(a^{\prime }))\in ̸\text{Im}(g)$, ou seja, $h_{n+1}^{-1}(a^{\prime })\in ̸\text{Im}(g)$. Isso implica $a^{\prime }\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)\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

Ligações externas

• Proofs from THE BOOK, p. 90. ISBN 3540404600
• Predefinição:Link
• Predefinição:Link
• Àlgebra para Graduação, Lang, S. Ed. Ciência moderna