Salhab, sua enumeração existe (assumindo ou que f(n,p) = f(n,n) se p > n), vc a criou, e na forma como vc a criou, não há nenhum problema em sua definição. Vc pode inclusive, quase que facilmente, calcular o valor da sua função para um dado par de naturais.
Se quiser um exemplo de como calcular o valor facilmente (com um computador), se vc conhecer a linguagem de programação F# -- cuja sintaxe é bem parecida com OCaml --, há alguns dias eu escrevi um artigo (em ingles) sobre obtenção de permutações de uma sequencia de símbolos: http://brunoreis.com/tech/nth-permutation-sequence-symbols/ Para criar sua função f, a partir da função que eu defino nesse artigo, é bem fácil, 1 linha de código: let f n p = [ 1 .. n ] |> nthPermutation (bigint p) Pronto. Tá definida em F# (ou OCaml). Dado o algoritmo que defini para nthPermutation, sua função f aí terá complexidade em tempo O(n), onde n é o tamanho da lista. Agora quanto a sua "demonstração" o erro é bem simples na verdade: vamos transformar essa sua função numa família de funções, pq vai ficar mais fácil de vc ver o erro, assim: f_n : N --> N^n f_n(p) = f(n, p) Veja que o contra-domínio de cada f_n é N^n, ou seja, *uma lista com nelementos *. O problema é que isso não tem nada a ver com o que o Lucas queria, ele falava de bijeções de N em N. Uma bijeção de N em N pode ser vista como *uma lista infinita de naturais unicos*, e na sua definição, NENHUM dos f_n produz uma bijeção nesse sentido, pq o "resultado" de uma f_n (e da sua f, consequentemente) será sempre uma *lista finita*. Ou seja: sua função não tem absolutamente nenhuma relação com uma bijeção de N em N. Assim, vc não pode usar sua função para argumentar sobre veracidade ou falsidade de afirmações sobre as bijeções de N em N. Entendeu? Abraço -- 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/23 Marcelo Salhab Brogliato <[email protected]> > Olá Lucas, > então, ainda nao vi pq nao criei uma enumeração das bijeções de N em N. > > Veja, posso utilizar f(n, p) para criar essa enumeração. É como se eu > fizesse o seguinte: > - primeiro vem as permutacoes de 1 elemento; > - depois vem as permutacoes de 2 elementos; > - depois vem as permutacoes de 3 elementos; > - depois vem as permutacoes de 4 elementos; > - e assim por diante... > > Sejam os pares ordenados (n, p) \in NxN. > (1, 1), (1, 2), (1, 3), ...., > (2, 1), (2, 2), (2, 2), ...., > > n = quantidade de elementos > p = p-ésima permutação dos n elementos > > Estou começando a achar que f(n, p) não existe... pois se existisse, acho > que minha prova é válida, visto que NxN é enumerável. > > É isso? > > abraços, > Salhab > > > > > 2010/1/22 <[email protected]> > > Oi marcelo, >> >> não, isto não é verdade. O que vc fez foi criar uma enumeração para as >> permutações de conjuntos finitos de n elementos. >> >> []'s Lucas >> >> Citando 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 >>>> >>>> ========================================================================= >>>> >>>> >>> >> >> >> ---------------------------------------------------------------- >> 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 >> ========================================================================= >> > >
