Re: Bijeção entre NxN e N

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

On Sat, 5 Aug 2000, Ecass Dodebel wrote:

> 
> 
> 
> >From: "Nicolau C. Saldanha" <nicolau@mat.puc-rio.br>
> >Reply-To: obm-l@mat.puc-rio.br
> >To: obm-l@matinta.mat.puc-rio.br
> >Subject: Bijeção entre NxN e N
> >Date: Thu, 3 Aug 2000 14:01:41 -0300 (BRT)
> >
> >
> >Problema clássico:
> >
> >Existe algum polinômio em duas variáveis que defina uma bijeção
> >entre NxN e N?
> >
> >Aqui N = {0,1,2,3,...} é o conjunto dos naturais
> >e NxN é o produto cartesiano de N com N, i.e.,
> >é o conjunto dos pares ordenados de naturais.
> >
> >[]s, N.
> >
> 
> Olá pessoal!
> 
> Para encontrar uma bijeção entre N^2 e N, devemos ordenar os elementos de 
> N^2, um modo de ordená-los é o seguinte:
> - (x,y) vem antes de (z,w) se x#y < z#w
> - (x,y) vem antes de (z,w) quando x#y = z#w se x<z
> 
> Exemplificando, em ordem (do primeiro elemento) temos:
> (0,0) ;
> (0,1) ; (1,0) ;
> (0,2) ; (1,1) ; (2,0) ;
> (0,3) ; (1,2) ; (2,1) ; (3,0) ;
> ...
> De modo que (x,y) é o elemento que vem depois dos elementos (z,w) onde z#w < 
> x#y que são 1 # 2 # 3 # ... # (x#y) e depois de x elementos (z,w) com soma 
> z#w=x#y e x<z, donde:
> (x,y) |-> 1 # 2 # 3 # ... # (x#y) # x = (x#y)(x#y#1)/2 # x
> é uma bijeção da forma pedida, em outras palavras, para o polinômio em duas 
> variáveis P definido por
> P(x,y) = (x#y)(x#y#1)/2 # x
> Não existem dois pares diferentes (x,y); (z,w) de forma que
> P(x,y) = P(z,w)
> E mais, para todo o k dos naturais, existe um par (x,y), tal que
> P(x,y) = k


Boa solução. Pergunta: existem outros polinômios com a mesma propriedade
além deste e da troca trivial de x por y?
> 
> Lanço uma outra questão.
> 
> 
> Existe algum polinômio em duas variáveis que defina uma bijeção
> entre RxR e R? (onde R é o conjunto dos Reais)
> 
Esta é muito mais fácil. E entre QxQ e Q?
> 
> Obrigado!
> 
> Eduardo Casagrande Stabel.
> 
> PS. podemos encontrar bijeções entre N^p e N^q para p e q inteiros 
> positivos, seguindo um raciocínio análogo, mas o polinômio, se é que sempre 
> existe, não deve ser tão simples quanto o caso p=2, q=1.

Acho que uma pergunta primeiro seria para que valores de p e q *existe*
um tal polinômio.
> 
> ________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>