Olá, Bernardo! Muito obrigado! Ficou claro! Essa diagonal é a "diagonal de Cantor"? Um abraço! Luiz
On Sun, Apr 15, 2018, 7:04 AM Bernardo Freitas Paulo da Costa < bernardo...@gmail.com> wrote: > 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 > ========================================================================= > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
