Marcelo, eu acho que fiz uma outra prova que mostra que é não-enumerável
(mas nao usa fracoes parciais):
Uma bijeção de N em N é uma lista L \in N^(+oo) na qual todos os elementos
são distintos. Seja K = { bijeções de N em N }
Vamos definir uma função M_2 : K --> {0, 1}^(+oo), isto é, que transforma
uma bijeção de N em N numa lista binária, da seguinte maneira:
A lista B = M_2(L) é definida por
B_i = L_i mod 2
Temos que M_2 é sobrejetiva. Prova: dada uma lista binária B, divida o
conjunto dos naturais em P e I, de pares e ímpares. Se B_i = 1, escolha L_i
de I (sem repetir). Se B_i = 0, escolha L_i de P (sem repetir).
Se uma função é sobrejetiva, significa que para cada elemento do
contradomínio corresponde pelo menos 1 elemento do domínio. Temos o seguinte
teorema:
f : A -> B é sobrejetiva ==> card(A) >= card(B) (mesmo para cardinalidades
"infinitas" -- nao vou demonstrar).
Pois bem, sabemos que {0, 1}^(+oo) é não-enumerável (prova: escreva
0.(B_0)(B_1)..., isso é um numero real entre 0 e 1 escrito em binário;
podemos representar TODOS os reais entre 0 e 1 dessa forma, então há uma
função sobrejetiva (bijetiva até) de {0, 1}^(+oo) em [0, 1], que sabemos ser
não enumerável; pelo mesmo teoreminha que anunciei no parágrafo anterior,
{0, 1}^(+oo) é pelo menos não-enumerável).
Assim, concluímos que *K, o conjunto das bijeções de N em N, é pelo menos
não-enumerável.*
O problema na sua demonstração foi que vc tomou (implicitamente) a sua tese
(equivocada) como hipótese. Isso é comum, e às vezes bem difícil de
perceber.
Talvez essa minha demonstração possa ser adaptada para usar frações
parciais, se conseguirmos criar um conjunto não-enumerável F de frações
parciais tais que exista uma função de K em F sobrejetiva.
Bruno
--
Bruno FRANÇA DOS REIS
msn: brunoreis...@hotmail.com
skype: brunoreis666
tel: +33 (0)6 28 43 42 16
http://brunoreis.com
GPG Key: http://brunoreis.com/bruno-public.key
e^(pi*i)+1=0
2010/1/21 Marcelo Salhab Brogliato <msbro...@gmail.com>
> Isso é verdade?
>
> Pensei na seguinte função:
> f(n, p) = p-ésima função das permutações de n elementos.
>
> Como (n, p) \in NxN, e NxN é enumerável, achei que f era uma enumeração das
> bijeções de N em N.
>
> abraços,
> Salhab
>
>
>
> 2010/1/13 <luc...@impa.br>
>
> Alguém consegue mostrar, usando frações contínuas, que o conjunto das
>> bijeções de N(naturais) em N é não enumenumerável ?
>>
>>
>> []'s
>>
>> Lucas
>>
>> ----------------------------------------------------------------
>> This message was sent using IMP, the Internet Messaging Program.
>>
>>
>>
>> =========================================================================
>> Instruções para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html<http://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html>
>> =========================================================================
>>
>
>
