Mostrar código-fonte de Teorema de Cantor-Bernstein-Schroeder

[[Ficheiro:Theoreme_cantor_bernstein.png|miniaturadaimagem|direita]]
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ção injetiva|funções injetivas]] ''f'' : ''A'' → ''B'' e ''g'' : ''B'' → ''A'' entre os conjuntos ''A'' e ''B'', então existe uma [[bijeção|função bijetiva]] ''h'' : ''A'' → ''B''. Em termos da [[cardinal]]idade 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úmero cardinal|números cardinais]].

Este teorema não depende do [[axioma da escolha]].

== Demonstração ==
Esta demonstração faz uso do conjunto dos [[Número natural|números naturais]], cuja existência é um dos axiomas da Teoria dos Conjuntos (o [[axioma do infinito]])<ref>[http://www.mathpath.org/proof/Sch-Bern/proofofS-B.htm Ver esta demonstração, exemplificada com gráficos]</ref>

Para cada <math>n\in\mathbb{N}</math> definimos <math>h_n : A \to A</math>, por <math>h_n=(g\circ f)^n</math>, composição de <math>n</math>fatores iguais a <math>g\circ f</math>. Observamos que <math>h_0=Id_A</math>. Note que o fato de <math>g</math> e <math>f</math> serem injetivas implica a injetividade de <math>h_n</math>.

Agora consideramos <math>X\subset A</math>, dado por

<math>X=\{a\in A; \text{ existe } n\in\mathbb{N} \mbox{ com } h_n^{-1}(a)\not\in \text{Im}(g)\}</math>.

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

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

<math>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)))
</math>

<math>=h_{n-1}^{-1}(f^{-1}(g^{-1}(g(b))))= h_{n-1}^{-1}(f^{-1}(b))
</math>.

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

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

Por fim, dado <math>b\in B</math> temos duas possibilidades: <math>g(b)\not\in X</math> ou <math>g(b)\in X</math>. No primeiro caso, temos que <math>H(g(b))=g^{-1}(g(b))=b</math> e no segundo caso, como foi observado, teremos que <math>f^{-1}(b)\in X</math> e daí, <math>H(f^{-1}(b))=f(f^{-1}(b))=b</math>. Portanto, <math>H</math> 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<sup>-1</sup>'' transforma (bijetivamente) a outra parte de ''A'' na outra parte de ''B''.<ref name="banach">[http://www.hinkis.org/HTML_pages/..%5CMathematical_papers%5C15_01_Banach_CBT_02.pdf Banach's proof of the Cantor-Bernstein theorem]</ref>

Mais precisamente:
: Sejam ''A'' e ''B'' conjuntos, <math>f: A \to B\,</math> uma função injetiva e <math>G: S \subseteq A \to B\,</math> uma [[Função sobrejectiva|função sobrejetiva]]. Então é possível particionar <math>A = A_1 \cup A_2\,</math>, <math>B = B_1 \cup B_2\,</math>, com <math>A_1 \cap A_2 = B_1 \cap B_2 = \varnothing\,</math> e de forma que ''f'' e ''G'' quando restritas, respectivamente, a ''A<sub>1</sub>'' e ''A<sub>2</sub>'' sejam bijeções, respectivamente, com ''B<sub>1</sub> e ''B<sub>2</sub>''.

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

A demostração encontra-se na referência<ref name="banach" />

{{Referências}}

== Ligações externas ==
* ''Proofs from THE BOOK'', p.&nbsp;90. ISBN 3540404600
* {{Link||2=http://planetmath.org/?op=getobj&from=objects&id=3156 |3=Proof of the Bernstein–Schroeder theorem |4=no [[PlanetMath]]}}
* {{Link||2=http://www.mathpath.org/proof/Sch-Bern/proofofS-B.htm |3=MathPath |4=- Explicação e notas sobre a prova do teorema de Cantor-Bernstein}}
* ''Àlgebra para Graduação'', Lang, S. Ed. Ciência moderna

{{Portal3|Matemática}}

{{DEFAULTSORT:Teorema Cantor Bernstein Schroeder}}
[[Categoria:Teoria dos conjuntos]]
[[Categoria:Teoremas de matemática]]
[[Categoria:Cardinalidade]]