Reflexões acerca do argumento de diagonalização de Cantor.

[Rodrigo Pinto]

Boa noite, sou engenheiro eletrônico (computação) mas gosto muito de algumas áreas da matemática e da lógica (Godel, Cantor entre outros).

Acredito que minhas reflexões a respeito do argumento de diagonalização de Cantor não sejam off-topic numa lista de lógica, e espero que meu meu texto atraia um pouco de atenção e receba comentários dos professor e alunos (e outros) da lista. 

Por não ser matemático (nem  lógico) talvez o vocabulário que eu utilize não seja o de uso corrente na área. Espero que me perdoem. 

Usando a definição da wikipedia (https://pt.wikipedia.org/wiki/Argumento_de_diagonaliza%C3%A7%C3%A3o_de_Cantor ) apenas para introduzir a questão:

Seja T o conjunto T de todas as sequências infinitas de dígitos binários.

Se s_1, s_2, ... , s_n, ... é qualquer enumeração dos elementos de T, então existe sempre um elemento s de T que não corresponde a nenhum s_n na enumeração.

Minha ideia é escolher uma sequência específica s_1, s_2, ... , s_n ... de tal maneira que o elemento s que não corresponde a nenhum s_n na enumeração seja um elemento específico (previsível).

Não sei se quebrei alguma regra do jogo no meio do caminho, mas a ideia é bem simples e de fácil exposição.

Digamos que a sequência s_1, s_2, ... , s_n ...  seja construída da seguinte maneira. 

Imaginemos a sequência de números naturais quando representada em binário, entre parênteses o natural em decimal correspondente:

0(0), 1(1), 10(2), 11(3), etc. Vamos escrever os dígitos binários desses números de trás pra frente e complementamos essa sequência de dígitos com uma sequência infinita de zeros. 

Ou seja,

s_1  = 000000...

s_2  = 100000...

s_3  = 010000...

s_4  = 110000...

s_5  = 001000...

s_6  = 101000...

s_7  = 011000...

s_8  = 111000...

s_9  = 000100...

s_10 = 100100...

s_11 = 010100...

s_12 = 110100...

s_13 = 001100...

s_14 = 101100...

s_15 = 011100...

s_16 = 111100...

(...)

Agora contruímos uma sequência s da maneira que Cantor faz, ele constrói a sequência s escolhendo seu n-ésimo dígito como um complemento para o n-ésimo dígito de s_n, para cada n. No exemplo, isso resulta em:

s = 111111...

Ou seja, o número que não aparece na enumeração é a sequência infinita de dígitos 1. 

Por outro lado, dada a regra de formação da sequência podemos estabelecer uma relação direta entre um número natural n e uma sequência s_n. Nesse caso, o número n -> s_m  (onde m=n+1) e a sequência s que não aparece na enumeração é exatamente a sequência que corresponde ao número 'natural" infinito (uma sequência infinita de dígitos 1).

Não sei se estou errando na interpretação, mas me parece que construído dessa maneira, acaba derrubando o ponto central da argumentação do Cantor.

Comentários/correções são benvindos.

Rodrigo

[Alfredo Roque Freire]

Olá Rodrigo.

O problema no argumento que fez é que o modo como enumerou números reais não captura todos os números reais. No argumento de Cantor, supomos (por contradição) que a lista de todos os reais é contável.

O que você fez não foi isso. Você mostrou um modo de listar números reais. Mas note que a sequência 010101010.... não será listada. Mais ainda, note que todos os números listados pelo seu procedimento são racionais, afinal, a partir de um determinado dígito, todos os demais são zero.

De fato, a sequência 111... não será listada no processo que definiu. Mas isso não tem relação com o propósito do argumento: a suposição de que a lista de todos os reais é contável.

Espero ter ajudado,

Alfredo

--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/bb09a1fe-cea3-416e-91ce-fc9cf3e2e375n%40dimap.ufrn.br.

--

Alfredo Roque Freire

[Walter Alexandre Carnielli]

Olá Rodrigo,

 é verdade,  endosso o argumento do Alfredo:  sua lista não tem nenhum número irracional :-)

E mais ainda : que número 'natural" infinito seria essa "sequência infinita de dígitos 1"?

 

Se entendi bem é 0,111...111..?

Mas esse é um racional...

Abraços,  

Walter 

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAHk6N6bR5Lqf3bgPCbOvkC3%3DgbaHqQaB2gw7UqkAhKg%2BQ%3DNaBw%40mail.gmail.com.

[Joao Marcos]

> é verdade, endosso o argumento do Alfredo: sua lista não tem nenhum número irracional :-)
>
> E mais ainda : que número 'natural" infinito seria essa "sequência infinita de dígitos 1"?
>
> Se entendi bem é 0,111...111..?
>
> Mas esse é um racional...

Daí já dá para ver também que há um montão de racionais (e inclusive
_números_ racionais, haha) que ficaram de fora.

JM

[Rodrigo Pinto]

Creio entender as argumentações e percebo que minha linha argumentativa se dirige a um precipício, mas gostaria de fazer uma observação.

Em nenhum momento é dito nada sobre real, racional ou imaginário (sim, eu sei que é isso que está por trás). 

T é descrita somente como "Seja T o conjunto T de todas as sequências infinitas de dígitos binários."

e depois desenvolve o argumento como "Se s_1, s_2, ... , s_n, ... é qualquer enumeração dos elementos de T, então existe sempre um elemento s de T que não corresponde a nenhum s_n na enumeração."

O problema me parece ser que ao criar uma regra para enumerar T eu acabo limitando a possibilidade de determinadas sequências aparecerem.

Obrigado

Rodrigo

[Rodrigo Pinto]

quando eu disse "Em nenhum momento é dito nada sobre real, racional ou imaginário ", eu quis dizer "Em nenhum momento é dito nada sobre real, racional ou irracional"

[Joao Marcos]

> T é descrita somente como "Seja T o conjunto T de todas as sequências infinitas de dígitos binários."

Corrigindo: "Seja T o conjunto de todas as sequências infinitas de

dígitos binários."

> e depois desenvolve o argumento como "Se s_1, s_2, ... , s_n, ... é qualquer enumeração dos elementos de T,

Esta é a suposição que inicia o raciocínio por contradição (já
apontado pelo Alfredo).
Sua forma lógica é: suponha que existe uma sobrejeção dos naturais em T.

> então existe sempre um elemento s de T que não corresponde a nenhum s_n na enumeração."

Exato. A alegada sobrejeção deixou alguém de fora. O sonho acabou.

> O problema me parece ser que ao criar uma regra para enumerar T eu acabo limitando a possibilidade de determinadas sequências aparecerem.

A alegada sobrejeção, de fato, poderia ter sido descrita por uma
"regra" criada por alguém... Ou não.

JM

[Alfredo Roque Freire]

Olá Rodrigo,

Você diz que "Em nenhum momento é dito nada sobre real, racional ou irracional". Porém, afirma na sua primeira mensagem que 

"mas me parece que construído dessa maneira, acaba derrubando o ponto central da argumentação do Cantor". 

O que seria, nesse caso, esse ponto central da argumentação de Cantor? Ao que parece, o ponto central do argumento da diagonal é 

determinar se "os reais têm ou não o 'mesmo tamanho' dos naturais" (sendo 'mesmo tamanho' a existência de uma bijeção entre os dois conjuntos).

Quando elabora uma L que lista reais a partir de números naturais, é preciso que essa lista seja exaustiva. Caso contrário, qual é o 

significado de dizer que existe um real fora da lista? A sequência (1,2,3,4,...) lista números reais -- e sabemos que 1,5 não foi listado. Isso parece equivalente 

à construção que tentou fazer.

Abs,

Alfredo.

[Petrucio Viana]

Boa tarde!

Talvez não contribua para uma "solução para esta discussão",

mas esta nota (Leron e Moran) diz respeito a um "aspecto positivo" do Método da Diagonal

que, me parece, é algo que o Rodrigo está querendo enfocar...

https://www.jstor.org/stable/27963787?refreqid=excelsior%3A361824b6beb9d2cd2a4ef5c98450f0fd&seq=1#metadata_info_tab_contents

abraços

P

--

Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAHk6N6b0rzkCrt9Jdpw3eLXLe3mRz5WTwJSMxsc6OVD5cAbPqg%40mail.gmail.com.

[Joao Marcos]

> Talvez não contribua para uma "solução para esta discussão",
> mas esta nota (Leron e Moran) diz respeito a um "aspecto positivo" do Método da Diagonal
> que, me parece, é algo que o Rodrigo está querendo enfocar...
>
> https://www.jstor.org/stable/27963787?refreqid=excelsior%3A361824b6beb9d2cd2a4ef5c98450f0fd&seq=1#metadata_info_tab_contents

O aspecto positivo é relevante para a discussão, sim, Petrúcio: toda
lista desses transeuntes deixa algum deles de fora!

JM


PS: Também isto é relevante, para o lado do humor:
https://xkcd.com/468/

[Rodrigo Pinto]

Obrigado a todos pelas observações.

Meu ponto (ao menos um deles) é que ao escolhermos uma enumeração específica podemos determinar a sequência que não faz parte da enumeração.

Isso ainda me parece ser verdadeiro. Mas isso não me leva a nenhuma outra conclusão.

Um outro ponto que me parece ser interessante e me parece ser verdadeiro (talvez eu esteja equivocado). É o seguinte:

Isso não está diretamente relacionada à questão (diagonalização).

Se estamos usando o sistema binário para representar os números naturais me parece possível dizer que o maior número (o infinito) será representado por uma sequência infinita de dígitos 1. Vocês consideram essa afirmação verdadeira?

Obrigado novamente.

Rodrigo

[Joao Marcos]

> Meu ponto (ao menos um deles) é que ao escolhermos uma enumeração específica podemos determinar a sequência que não faz parte da enumeração.
> Isso ainda me parece ser verdadeiro. Mas isso não me leva a nenhuma outra conclusão.

Bem, para avaliar tal asserção seria necessário determinar o
significado do verbo "determinar". Dependendo do que você quer dizer
com isso, a sua primeira sentença acima pode ser verdadeira... ou,
mais provavelmente, falsa! (Note, por exemplo, que o _complemento_ do
conjunto que contém os números da sua sequência não é um conjunto
enumerável.)

JM

--
http://sequiturquodlibet.googlepages.com/

[samuel]

Oi gente,

Só pra dar um "pitaco",

A prova do Teorema de Cantor não precisa ser por contradição, na verdade quando escolhemos o contradomínio como {0,1} acredito que já estamos embutindo aí possivelmente o Terceiro Excluído quase todo e dá pra fazer uma prova "quase direta", vai ter só uma análise de casos. 

Ou seja, depois de muitos anos fazendo isso com alunos eu não começo com

"Suponha por absurdo que eu tenha uma enumeração de todas as sequências binárias infinitas"

e sim com

"Considere qualquer funcao fixada dos naturais nas sequências binárias infinitas, eu vou mostrar que essa função não é sobrejetora"

pois se não existir funcao sobrejetora, em particular nao vai existir bijecao...

(Aliás, aqui que é o ponto que eu acho que é o mais problemático de "querer prever quem está na diagonal fazendo uma enumeração

esperta", o teorema não fala de enumerações espertas, o teorema fala de TODAS AS ENUMERAÇÕES POSSÍVEIS, ou seja, para

qualquer enumeração que você faça tem uma sequência que não aparece na lista. Eu particularmente não vejo interesse

em ver o que ocorre com uma enumeração fixada, eu quero saber o que ocorre para qualquer uma arbitrária)

Ao invés de fazer a tal prova (que eu acho um pouco mais construtiva) para sequências infinitas de zeros e uns, vou fazer a prova para X e Partes de (X), para qualquer conjunto X (que não precisa ser enumerável, nao precisa ser N, nao preciso pensar em números reais...). Claro que se você pega 

X = N aqui você identifica Partes de N com as sequencias infinitas de zeros e uns e cai no caso anterior, mas isso é outra história...

Teorema: Dado um conjunto X e uma funcao qualquer de X em Partes de X, essa funcao nao é sobrejetora.

dem.  Seja f: X --> Partes de X uma funcao qualquer.

Afirmo que Y = {x em X: x não pertence a f(x)} não está na imagem da função.

Aqui não vou supor por absurdo que Y é f de alguém e chegar numa contradição, o que eu faço é afirmar:

*Dado qualquer x em X, f(x) é diferente de Y.*

Aí que vem a única análise de casos ("uso do Terceiro Excluído", concordo...)

Se x pertence a f(x),  entao x não pertence a Y.

Se x não pertence a f(x), entao x pertence a Y.

Logo, para todo x, eu uso ele mesmo para mostrar que f(x) e Y são diferentes (de um jeito ou de outro, conforme o caso).

Atés,

[]s  Samuel

[Joao Marcos]

> Aí que vem a única análise de casos ("uso do Terceiro Excluído", concordo...)

E por falar em Terceiro Excluído, Samuel, você saberia explicar em
termos pedestres até onde conseguiríamos levar o argumento da
diagonalização, digamos, em *CZF*, se assumirmos o axioma segundo
o qual todo conjunto é subcontável?

[]s, Joao Marcos


--
http://sequiturquodlibet.googlepages.com/

[samuel]

... Humm... Nâo tenho muita experiência com Teoria dos Conjuntos construtiva "pra valer" (ir lá dentro e mexer mesmo nesses sistemas, pro tipo

de coisa que eu faço o "construtivo" é simplesmente ZF mas aí eu mantenho o Terceiro Excluído ainda), mas se assumimos que todo subconjunto infinito tem um subconjunto enumerável infinito a idéia seria fazer o argumento de Cantor dentro desse subconjunto enumerável e obter aí o subconjunto que não pertence à imagem da função fixada de X em Partes de X;  agora como eliminar a análise de casos ou a prova

por contradição eu teria que pensar um momento, não vejo como agora. 

Até

[]s  Samuel

[Petrucio Viana]

Boa tarde,

segue uma maneira "intuitiva" (construtiva?), devida a Dijkstra e Misra, de provar o teorema de Cantor.

Ela condensa a ideia usada na prova que o Samuel apresentou, exibindo de maneira natural o conjunto que "estraga" a bijeção.

Teorema: Para todas as funções F de X em P(X) e g de P(X) em X, Fog =/= Id.

Prova:

Sejam F e g tais funções.

Temos que:

Fog =/= Id

é equivalente a 

existe Y em P(X) tal que Y =/= F(g(Y))

é consequência de

existe Y em P(X) tal que [g(Y) pertence a Y não é equivalente a g(Y) pertence a F(g(Y)]

é consequência de

existe Y em P(X) tal que para todo x {[x pertence a Y] é equivalente a [x não pertence a F(x)]} 

tomando (o candidato natural exposto pela passagem acima) Y = { x : x não pertence a F(x) } isto é equivalente a

verdadeiro.

QED

--
Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.

Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAO6j_LghbEJLz_key_MLrks16WSXx%3D4NeYsj%3D08d2NO44HQKdA%40mail.gmail.com.

[Joao Marcos]

Belo exemplo do "raciocínio calculacional" de Dijkstra, Petrucio!

Em um post recente na FOM (do qual eu tirei o link que enviei aqui na
lista esta semana para o arquivo do Dijkstra) o Vladik Kreinovich
escreveu:
"Examples of calculational proofs in Edsger’s writings were so
impressive that I even asked myself whether every possible use of
natural deduction in classical logic can be replaced, in principle, by
calculational reasoning. The answer turned out to be yes (published in
the Annals of Pure and Applied Logic in 2002)."
https://cs.nyu.edu/pipermail/fom/2021-March/022524.html

Você saberia dizer a qual paper no APAL ele se refere?

Abraços,
Joao Marcos

--
http://sequiturquodlibet.googlepages.com/

[Valeria de Paiva]

pra logicos brasileiros que gostam de  brincadeiras de matematicos franceses

http://www.neverendingbooks.org/wheres-bourbakis-tomb

boa sexta!

Valeria

--

Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.

Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/3439ca50-4be9-49ad-b22b-86f5cea76976n%40dimap.ufrn.br.

--

Valeria de Paiva
http://vcvpaiva.github.io/
http://www.cs.bham.ac.uk/~vdp/

[Petrucio Viana]

Oi João,

acredito que o artigo ao qual ele está se referindo seja este aqui:

On calculational proofs

1. Vladimir Lifschitz

Annals of Pure and Applied Logic

Volume 113, Issues 1–3, 27 December 2001, Pages 207-224

Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAO6j_LigzB4LaC3G8h_HtijEHP2-3%3D-wfO03tjETohpEnUir4g%40mail.gmail.com.

[samuel]

... Haha,

Tem um detalhe sutil aí na prova que o Petrúcio apresentou,

Apesar de ser "raciocínio calculacional", pra provar o que ela quer provar, digamos assim, precisa do Axioma da Escolha,

No sentido de que o argumento essencialmente diz que:

"Dada uma funcao de X em Partes de X, ela nao tem inversa à direita"

Só que a implicacao

"não ter inversa à direita" --> "não é sobrejetora"

é equivalente a

"a função é sobrejetora" ----> "tem inversa à direita"

e esta última é uma equivalência do Axioma da Escolha !!!!

Gostei hehe...

Atés, bom final de semana, 

[]s  Samuel