Em 15 de abril de 2018 09:43, Luiz Antonio Rodrigues <[email protected]> escreveu: > Olá, Ronei! > Fiz essa pergunta para o Bernardo... > Um abraço! > Luiz > > > On Sun, Apr 15, 2018, 7:23 AM Ronei Lima Badaró <[email protected]> wrote: >> >> Não é a tal diagonal de Cantor?
Sim, é este o nome. >> >> Em Dom, 15 de abr de 2018 07:05, Bernardo Freitas Paulo da Costa >> <[email protected]> escreveu: >>> >>> 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 >>> ========================================================================= >> >> >> -- >> 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. -- 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 =========================================================================
