Re: Bijeção entre NxN e N

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

On Sun, 13 Aug 2000, Ecass Dodebel wrote:

> >
> >Acho que agora eu achei uma bijeção entre N^3 e N
> >(x,y,z)|-> (x#y#z)(x#y#z-1)(x#y#z#4)/6 # (2x#y#z) # (x#y#z#1)(x#y#z#2)/2 - 
> >(x#y#1)(x#y#2)/2
> >Não está na forma expandida, os primeiros termos são:
> >(0,0,0)
> >(0,0,1);(0,1,0)
> >(1,0,0)
> >(0,0,2);(0,1,1);(0,2,0)
> >(1,0,1);(1,1,0)
> >(2,0,0)
> >(0,0,3);(0,1,2);(0,2,1);(0,3,0)
> >(1,0,2);(1,1,1);(1,2,0)
> >(2,0,1);(2,1,0)
> >(3,0,0)
> >...
> >Estou tentando generalizar o polinômio.
> >
> >Obrigado!
> >
> >Eduardo Casagrande Stabel.
> >________________________________________________________________________
> >Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
> >
> 
> Olá, pessoal!
> 
> Acho que consegui generalizar o polinômio. Vamos à minha idéia:
> P_1(x_1)=x_1, esse nós definimos. E direi que
> Q_n(x)=número de n-uplas naturais (x_1,...,x_n) com x_1+...+x_n=x, de forma 
> que
> Q_n(x)=P_n(x,0,...,0) - P_n(x-1,0,...,0), quando x>0 e
> Q_n(0)=1
> 
> Para ordenarmos os elementos de NxNx...xN = N^n utilizaremos a seguinte 
> regra:
> i) (x_1,...,x_n) vem depois de (y_1,...,y_n) se x_1+...+x_n>y_1+...+y_n
> ii) se x_1+...+x_n = y_1+...+y_n, então (x_1,...,x_n) vem depois de 
> (y_1,...,y_1) se, na ordenação de N^(n-1), (x_2,...,x_n) vier antes de 
> (y_2,...,y_n).
> 
> Com isso, fica fácil de ver por que Q_n(x)=P_n(x,0,...,0) - 
> P_n(x-1,0,...,0), e também podemos construir o P_(n+1) a partir do P_n, 
> vamos à construção:
> 1) Q_(n+1)(x) = Q_n(0)+...+Q_n(x)
> Isso por que os elementos (x_1,...,x_(n+1)) com a soma x_1+...+x_(n+1)=x 
> podem ser entendidos como o número de elementos com x_1=0 (que são Q_n(x)), 
> com x_1=1 (que são Q_n(x-1)),..., com x_1=n (que são Q_n(x)=0), o que mostra 
> a validade da fórmula.
> 2) Seja S=x_1+...+x_(n+1), então
> P_(n+1)(x_1,...,x_(n+1)) = [Q_(n+1)(0) + ... + Q_(n+1)(S)]
>                            - [P_(n)(x_2,...,x_(n+1)) + 1]
> A demonstração é simples, de acordo com i e ii.
> 
> Por 2), aplicando 1), chegamos à fórmula:
> P_(n+1)(x_1,...,x_(n+1)) = [(S+1)Q_n(0) + ... + Q_n(S)]
>                            - [P_(n)(x_2,...,x_(n+1)) + 1]
> Onde S=x_1+...+x_(n+1). E essa é a construção de P_(n+1) a partir de P_n. A 
> prova de que P_(n+1) é polinomial vem do fato que P_n é polinomial e a soma 
> dos Q_(n)'s também é, acho que nào é muito difícil de ver. Logo para 
> qualquer n natural existe um polinômio que defina uma bijeção entre N^n e N, 
> e ainda conseguimos achar o polinômio.
> 
> Obrigado!
> 
> Eduardo Casagrande Stabel.
> 
> PS. eu continuo curioso para saber se existem mais de dois polinômios que 
> definam bijeção entre NxN e N, e algo sobre bijeções por polinômios em QxQ e 
> Q, RxR e R.
> 
> 
> ________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
> 

Não verifiquei os detalhes mas a idéia geral está correta.
Uma outra idéia seria a seguinte:
seja P_2 o polinômio em duas variáveis que define uma bijeção
entre NxN e N.
Defina P_3(x,y,z) = P_2(x,P_2(y,z)) e, mais geralmente,
P_n(x_1,x_2,...,x_n) = P_2(x_1,P_2(x_2,P_2(...P_2(x_{n-1},x_n)...)))
ou, para quem preferir,
P_{n+1}(x_1,x_2,...,x_n,x_{n+1})  = P_2(x_1,P_n(x_2,...,x_{n+1})).

Estas variações mostram que existem muitas bijeções polinomiais
entre N^n e N para n >= 3. Resta o caso n=2...

Para R é fácil ver que não existe se usarmos um pouco de matemática
mais avançada. Por exemplo, mostrarei que uma função contínua f de RxR em R
nunca é injetora. Considere três pontos no plano não colineares,
por exemplo (0,0), (1,0) e (0,1). Suponha sem perda de generalidade
que f(0,0) < f(0,1) < f(1,0). Por continuidade deve existir t, 0 < t < 1,
com f(t,0) = f(0,1). O resultado sobre polinômios é um caso muito especial.

[]s, N.