Em 18 de abril de 2018 07:47, Claudio Buffara <[email protected]> escreveu: > Agora, uma pergunta: > > E se fossemos fazer uma lista de todos os racionais (dízimas periódicas) > entre 0 e 1 (por exemplo, escolhendo, quando houver ambiguidade, a versão > que termina por 9999...)? > Neste caso, o método da diagonal deveria falhar, certo, já que Q inter (0,1) > é enumerável?
Sim. > Mas, de cara, me parece possível escolher, para todo i em N, um algarismo > b(i) diferente de a(i,i) (= i-ésimo algarismo do número na i-ésima linha da > lista). > Como pode? > O número gerado por este método de diagonal não pode ser racional. Bem, a demonstração é a mesma: se este número fosse racional, ele apareceria em algum momento, o que é impossível dado que ele nunca será igual a nenhum dos números. Esta é a resposta do seu "deveria falhar". > []s, > Claudio. > > > 2018-04-17 22:52 GMT-03:00 Anderson Torres <[email protected]>: >> >> 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 >> ========================================================================= > > > > -- > 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 =========================================================================
