Re: Bijeção entre NxN e N

["Ecass Dodebel" <ecassdodebel@xxxxxxxxxxx>]

>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

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)


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.

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com