Olá Bruno, dei uma olhada por cima da sua demonstração, mas não entendi de primeira =) Vou tentar novamente em breve e peço ajuda se nao consegui hehehehehe
Não entendi onde usei minha tese. Pela minha mensagem pro Lucas, acho que foi assumindo que f(n, p) existe. É isso? Obrigado pela demonstração e pela correção, Salhab 2010/1/21 Bruno França dos Reis <[email protected]> > 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: [email protected] > 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 <[email protected]> > > 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 <[email protected]> >> >> 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> >>> ========================================================================= >>> >> >> >
