Re: [obm-l] Um tema recorrente.

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

2008/1/16 Fernando A Candeias <facandeias@xxxxxxxxx>:
>
>
>
> Caros colegas de lista.
>
>
>
> "Seriam os números aleatórios os principais responsáveis pela não
> enumerabilidade do conjunto dos números reais?"
>
>
>
> Em agosto do ano passado coloquei essa pergunta na lista, formulada de modo
> um pouco diferente, mas em essência, a mesma. O assunto despertou a atenção
> de alguns colegas, e as sugestões de leitura que recebi do Santa Rita e do
> Nicolau, quanto aos números não computáveis, números de Cantor, normais e
> outros temas se revelaram de grande utilidade.
>
> Quando formulei a questão tinha a impressão de que a resposta seria
> positiva, mas no decorrer da troca de mensagens mudei de opinião.
>
> Entretanto outros argumentos a que tive acesso no decorrer de minha busca
> parecem indicar que as seqüências aleatórias infinitas são, não só os
> principais atores, mas na verdade os únicos responsáveis pela cardinalidade
> do conjunto dos reais.
>
> Submeto ao crivo dos colegas um estudo denominado "Teorias da Aleatoriedade"
> de Carlos A.P. Campani e Paulo Baluth Menezes, da UFRGS que pode ser
> localizado na rede em:
>
>  http://www.inf.ufrgs.br/~revista/docs/rita11/rita_v11_n2_p75a98.pdf.

Oi Fernando, quando você mandou esta pergunta da outra vez eu respondi que NÃO,
que existe um conjunto com a cardinalidade de R de números não aleatórios.
Na ocasião você não propos, se eu bem me lembro, uma definição do que seria
um número aleatório então o meu argumento talvez tenha ficado vago.
Mas agora que você deu esta referência vou enunciar um exemplo rigoroso.

Seja t: N -> N (a função torre binária) definida recursivamente por
t(0) = 0, t(n+1) = 2^t(n)
de tal forma que t(1) = 1, t(2) = 2, t(3) = 4, t(4) = 16, t(5) =
65536, t(6) = 2^65536, ...
Para cada seqüência s: N -> {0,1} defina x_s = SOMA_{k >= 0} s(k) 2^(-1-t(k)).
Analogamente, para cada s consideramos a seqüência ss onde
ss(t(k)) = s(k) e ss(k) = 0 se não existir j com t(j) = k.
Exemplo: seja s = 011001001...
Temos x_s = 2^(-2) + 2^(-3) + 2^(-65537) + 2^(-1-t(8)) + ... e
ss = 011000000.....0000010000....00000100000....
onde o terceiro 1 aparece na posição 65536 e o quarto na posição t(8).

Sejam Kx e Ks os conjuntos de todos os x_s e ss conforme definidos
acima, respectivamente.
Afirmamos que o conjunto Kx é um conjunto de Cantor (i.e., é
homeomorfo ao conjunto de Cantor usual)
e tem portanto a cardinalidade de R; claramente Ks tem a mesma
cardinalidade de Kx.
Afirmamos ainda que nenhuma seq binária ss em Ks é aleatória no
sentido da Def 2, pg 79 (Kollektiv).
Afirmamos ainda que Ks é um conjunto efetivo nulo (no sentida da Def 4, pg 83)
donde nenhuma seq ss em Ks é aleatória no sentido da Def 5, pg 84.

A afirmação sobre Kx ser um conjunto de Cantor é fácil: basta compor a
correspondência s -> x_s
com a inversa da correspondência clássica s -> (2/3) * SOMA_{k >= 0}
s(k) 3^(-k).
A afirmação sobre cardinalidade segue daí pois é um fato bem sabido
que a cardinalidade
de conjunto de Cantor usual é igual à de R.

Quanto à Def 2, é bem fácil ver que ss viola o item 1 pois lim
(SOMA_{0 <= i <= n-1} ss(i))/n = 0.

Quanto à Def 4, o algoritmo é o seguinte. Dado epsilon > 0, tome n tal
que 2^(n-t(n)) < epsilon
(é bem fácil ver que existe tal n e até obter algum tipo de fórmula
para n em termos de epsilon).
As strings binárias serão em número 2^n e terão comprimento t(n).
As posições t(0), t(1), t(2)., ..., t(n-1) assumem todos os valores possíveis;
as demais posições são sempre iguais a 0.

[]s, N.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================