2018-04-15 5:36 GMT-03:00 Luiz Antonio Rodrigues <[email protected]>: > 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 =========================================================================
