Teorema de Cantor-Bernstein-Schroeder

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 : AB e g : BA entre os conjuntos A e B, então existe uma função bijetiva h : AB. 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[editar | editar código-fonte]

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 n\in\mathbb{N} definimos h_n : A \to A, por h_n=(gof)^n, composição de n fatores iguais a gof. 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; \mbox{ existe } n\in\mathbb{N} \mbox{ com } h_n^{-1}(a)\not\in im(g)\}.

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

Por outro lado, observamos que dado b\in B, se tivermos g(b)\in X, então b\in 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 Im(g). É claro que n\neq 0 e nesse caso podemos escrever

h_n^{-1}(g(b))=h_{n-1}^{-1}o(gof)^{-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 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 Im(g). Logo, h_n^{-1}(h_1^{-1}(a'))\not\in Im(g), ou seja, h_{n+1}^{-1}(a')\not\in 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[editar | editar código-fonte]

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, 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 A1 e A2 sejam bijeções, respectivamente, com B1 e B2.

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[2]

Referências