2018-04-15 5:36 GMT-03:00 Luiz Antonio Rodrigues <rodrigue...@gmail.com>:
> Olá, amigos!
> Bom dia!
> Estou lendo "Matemática Discreta" da SBM e me deparei com o trecho que eu
> reproduzi abaixo.
>
>
> A principal contribuição de Cantor foi exibir casos em que não é possível
> obter uma bijeção entre dois conjuntos infinitos.
> (...)
> Seja C o conjunto de todas as sequências infinitas em que todos os termos
> são iguais a zero ou um.
> Suponhamos que fosse possível uma função f: N -> C, em que cada sequência de
> C aparecesse exatamente uma vez como imagem. Vamos construir uma sequência s
> formada por 0s e 1s (ou seja, um elemento de C) do seguinte modo: se o
> primeiro termo da sequência f(1) é zero, o primeiro termo de s é 1; senão, é
> zero. Se o segundo termo da sequência f(2) é zero, o segundo termo de s é 1;
> senão, é zero. Prosseguimos, sempre escolhendo o n-ésimo termo s(n) como
> sendo o oposto do n-ésimo termo da sequência f(n). A sequência s assim
> construída difere pelo menos na posição n de cada sequência f(n). Logo, não
> pertence à imagem de f. Mas nossa suposição era de que todos os elementos de
> C aparecessem como imagem!
> Temos, assim, uma contradição, que mostra a impossibilidade de construir uma
> bijeção de N em C.
>
> Já o reli diversas vezes. Eu "travei" na frase "A sequência s assim
> construída difere pelo menos na posição n de cada sequência f(n)."

Acho que ajuda a entender se você fizer um exemplo.  Claro que um
exemplo não prova nada, mas espero que ilumine a construção usada.

Suponha, assim, que f seja da seguinte forma:
1 -> 0100101010101
2 -> 010101010101
3 -> 1111111111001
4 -> 000000000000
5 -> 1110111010101

Agora, vou construir a tal da sequência s, "descobrindo" o valor de
cada um dos elementos, um a um:

O primeiro elemento de s é o "oposto" do primeiro elemento de f(1).
Como o primeiro elemento de f(1) é 0, vai ser um:

s = 1....

O segundo elemento de s é o oposto do segundo elemento de f(2) (que é 1):

s = 10....

O terceiro elemento, oposto do terceiro de f(3), dá s = 100...
O quarto, s = 1001...
O quinto, s = 10010

Agora, repare s não pode ser f(1), nem f(2), nem f(3), nem f(4), ...
Porque o primeiro elemento de s é diferente do primeiro de f(1).  O
segundo de s, diferente do segundo de f(2). E assim por diante.
Muitas vezes, num quadro-negro, o pessoal faz a tabela que eu esbocei
acima, e envolve os elementos da "diagonal descendente", e depois cria
a sequência dos opostos.

Abraços,
-- 
Bernardo Freitas Paulo da Costa

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================

Responder a