Teorema de Cantor-Schroeder-Bernstein

Apesar do nome, o teorema de Cantor-Schroeder-Bernstein é simples, além de ser muito conhecido e bastante usado. Dois conjuntos A e B são, por definição, de mesma cardinalidade se existe uma bijeção \phi :A\to B . Quando existe essa bijeção, denota-se card (A) = card (B) .

Antes de enunciar o teorema, será provado o seguinte lema.

Lema 1: Sejam A, B conjuntos não-vazios. Existe uma sobrejeção \gamma : A\to B se, e somente se, existe uma injeção \lambda : B\to A .


Demonstração: Com efeito, se existe uma sobrejeção \gamma : A\to B , segue que, para cada x\in B , podemos escolher um único y_x\in A tal que \gamma (y_x) = x . Então definimos \lambda : B\to A , \lambda (x) =y_x .. Note que isso é, evidentemente, uma injeção.

Reciprocamente, se existe \lambda :B\to A injetivo, fixando a\in B qualquer, define-se \gamma : A\to B tal que:

\gamma (x) = \lambda ^{-1} (x) , se x\in \lambda (B) ;

\gamma (x) = a , se x\not\in\lambda (B) .

Note que \gamma é evidentemente sobrejetivo.


Diz-se que card(A)\leq card(B) (cardinalidade de A é menor ou igual à cardinalidade de B ) se existe uma injeção \lambda : A\to B .

Proposição 2: Se B\subset A e card(A)\leq card(B) , então A e B tem a mesma cardinalidade. Ou seja, se B\subset A e existe uma injeção f :A\to B , então A  e B tem a mesma cardinalidade.


Demonstração: Com efeito, toma-se a injeção f: A\to B . Como B\subset A , tem-se que f(B)\subset f(A) . E é fácil de verificar por indução que, para todo n\in\mathbb{N} ,

f^n(B)\subset f^n(A) . Define-se

\displaystyle K= \left\{ x\in A : x\in \bigcup_{n\in\mathbb{N}\cup \left\{ 0\right\} } f^n(A)-f^n(B) \right\} .

E, então, define-se h: A\to B tal que

h(x) = f(x) , se x\in K ,

h(x)=x , se x\in (A-K) .

Evidentemente, h|_K e h|_(A-K) são injetivas. Logo, para provar que h é injetiva, basta provar que, dados a\in K e b\in (A-K) , h(a)\neq h(b) . Bom, supõe-se por absurdo que, nessas condições, h(a)=h(b) . Isso implica que f(a)= h(a)=h(b)=b .

Toma-se m\in\mathbb{N} tal que a\in (f^m(A)-f^m(B) ) . Tem-se que f(a)=b\in f^{m+1}(A) . E, como b\not\in K , tem-se que b\in f^{m+1}(B) . Disse segue que existe t\in f^{m}(B) tal que f(t)=b . Mas, pela injetividade de f , a=t\in f^{m}(B) . Portanto a\not\in (f^m(A)-f^m(B) ) . Absurdo. Portanto deve-se ter que h(a)\neq h(b) . E isso completa a prova de que h é injetiva.

Resta provar que h é sobrejetiva. Dado q\in B , se q\in B-K , basta ver que h(q)=q . Caso q\in K\cap B , tem-se que q\in (f^{t}(A)-f^{t}(B)) para algum t\in\mathbb{N} (positivo), afinal q\in B . Note que, então, existe z\in f^{t-1}(A) tal que f(z)=q . E, també, tem-se que z\not\in f^{t-1}(B) , pois o contrário implicaria f(z)= q\in f^{t}(B) e, então, q\not\in (f^{t}(A)-f^{t}(B)) .

Disso segue que \displaystyle z\in (f^{t-1}(A)-f^{t-1}(B)) e, portanto, h(z)=f(z)=q . Isso completa a prova da sobrejetividade de h .

Portanto h é bijeção, donde segue que card(A)=card(B) .


Teorema 3 (Teorema de Cantor-Schroeder-Bernstein): Sejam A, B conjuntos não vazios. Se card(A)\leq card(B) e card(B)\leq card(A) , segue que card(A)=card(B) . Ou seja, se existem injeções f: A\to B e g:B\to A , então existe uma bijeção \phi :A\to B .


Demonstração: Com efeito, tomando as injeções f: A\to B e g:B\to A , tem-se que

f^*: A\to f(A) , onde f^* (x)=f(x) , é uma bijeção entre A e f(A)\subset B .

Logo (f^*\circ g): B\to f(A) é uma injeção. Como f(A)\subset B , pela proposição 2, segue que

card(f(A)) = card(B) , ou, em outras palavras, existe uma bijeção h: f(A)\to B . Note, então, que

\phi = (h\circ f^*): A\to B é composição de bijeções e, portanto, bijeção.


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: