Re: prove se v ou f

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxx>]

On Wed, 26 May 1999, Carlos Nehab wrote:

> Eu já estava com saudades de você... Mas parece que você anda com um
> fascínio absurdo por números cavalares...!!!!  Tome jeito rapaz. Daqui a
> pouco você terá pesadelos...

Falando em números cavalares...

Defina f(0,n) = f(n,0) = n+1 e f(n+1,m+1) = f(n,f(n+1,m)).
Ache os dois últimos algarismos de f(1999,1999).

> A propósito, as duas questões que eu coloquei na prova do Saldanha (e eu é
> que sou gozador....) e que o Benjamim acertou (:))))), ninguém se
> manifestou.  Será que as questões de Lógica não provocam mais ninguém? -
> são tabú? 
> 
> Apenas mais uma pergunta clássica, que também caiu naquela prova (prá ver
> se cutuco o Nicolau a escrever uma introdução às questões sobre Verdadeiro
> e Falso em uma teoria).
> 
> "Seja R a coleção de todos os conjuntos que pertencem a si próprio. Será
> que R pertence a si próprio?"

Esta questão eu adio, mas queria voltar a falar da prova surpresa.

Se consideramos o conceito de "surpresa" no sentido usual,
psicológico e não matemático, nenhuma demonstração matemática é possível.
Podemos aliás sempre invocar possíveis alunos
distraídos (que esquecem que o professor ameaçou fazer uma prova),
neuróticos (que sempre acham que a prova será *hoje*) ou até
espiões (que leem a agenda do professor pelas costas para saber
para quando ele planeja a prova). É claro que nestes termos não
há paradoxo nenhum.

O raciocício do Benjamin supõe uma situação idealizada e um conceito
matematizado de surpresa. Não *parece* haver nenhuma dificuldade
a primeira vista em formalizar o conceito de surpresa:
dizemos que a prova é surpresa se o aluno não tinha informação
que permitisse a ele *deduzir*
(logicamente, supondo um raciocínio perfeito)
que a prova seria hoje.
E o paradoxo *parece* dizer respeito a esta situação idealizada
e a este conceito matematizado de surpresa.

Mas pensando um pouco mais vemos que há neste exemplo uma dificuldade
séria para definir prova surpresa: a principal informação de que
o aluno dispõe é de que a prova será... surpresa!
Ou seja, para definir prova surpresa é preciso primeiro
tornar claro que raciocínios são corretos usando a
informação que a prova é surpresa.
Ou seja, só podemos definir prova surpresa já tendo definido
prova surpresa...

As dificuldades apontadas no parágrafo anterior são reais,
mas serão elas insuperáveis?
Sim, são insuperáveis, e a prova disso é o próprio paradoxo (!).
O que a anedota demonstra é que um conceito de prova surpresa
que permita ao Benjamin fazer o raciocínio que fez
terá muito pouco a ver com o conceito informal de surpresa.  
Ou seja, não existe conceito matematizável satisfatório
de prova surpresa, pelo menos quando uma das informações
a serem usadas é de que a prova será surpresa.

Este paradoxo me parece semelhante a outro, mais matemático:

Seja N o menor natural que não pode ser descrito
em português com menos de 100 caracteres ASCII.

Bem, como existem só 256 (ou 128?) caracteres ASCII,
existem menos de 256^100 tais sequências de caracteres.
Existem portanto menos de 256^100 naturais que podem ser descritos
com menos de 100 caracteres.
Como existem infinitos naturais, existem muitos que *não* podem
ser descritos com menos de 100 caracteres.
Existe portanto um natural N que é o menor destes.
Ele é descrito pela frase acima.
Mas a frase acima tem menos de 100 caracteres!

A solução do paradoxo é português não é uma linguagem formal e
portanto o conceito de "poder ser descrito com menos de 100 caracteres"
não é um conceito matemático. Nem sequer *pode* ser tornado um conceito
matemático ao mesmo tempo permitindo que a frase acima
seja aceita como uma descrição, pois senão recaimos no paradoxo.

[]s, N.
http://www.mat.puc-rio.br/~nicolau