Olá, Ronei! Fiz essa pergunta para o Bernardo... Um abraço! Luiz On Sun, Apr 15, 2018, 7:23 AM Ronei Lima Badaró <rlbad...@gmail.com> wrote:
> Não é a tal diagonal de Cantor? > > Em Dom, 15 de abr de 2018 07:05, Bernardo Freitas Paulo da Costa < > bernardo...@gmail.com> escreveu: > >> 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.