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@mat.puc-rio.br
>Subject: Re: Bijeção entre NxN e N
>Date: Mon, 7 Aug 2000 08:31:25 -0300 (BRT)
>
>
>
>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?

Eu ACHO que não. Até por que não existe um polinômio que defina bijeção 
entre N e N, daí esse raciocínio talvez se estenda, mas não sei provar.

> >
> > 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?

Eu consigo mostrar que existe bijeção entre R e RxN, de forma que deveria 
haver bijeção entre RxR e RxN, e para isso, eu ACHO que deveria haver alguma 
bijeção entre R e N, o que sei que não existe, mas não sei demonstrar que 
não existe bijeção entre RxR e R. Quanto ao segundo, eu sei fazer uma 
bijeção entre QxQ e Q, mas sem encontrar um polinômio que defina alguma 
bijeção.

> >
> > 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.

Eu ACHO que *existe* um polinômio que seja bijeção entre N^p e N^q, somente 
nos casos (p,q)=(k,k) ou (k,1), com k natural, também não sei demostrar.
Sem certeza diria que
(z,x,y)|-> (x#y#z)(x#y#z#1)(x#y#z#2)/6 # z(z#1)/2 # z(x#y) # (x)
é uma bijeção entre N^3 e N, definida por um polinômio.

Ajudem-me a solucionar os ACHÔMETROS (não foi falta de pensar que me fez 
fazer essas suposições e mandar para a lista de qualquer jeito, o fato é que 
me falta capacidade para descobrir algo mais).

Obrigado!

Eduardo Casagrande Stabel.

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

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