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: Thu, 10 Aug 2000 13:13:22 -0300 (BRT)
>
>
>
>On Thu, 10 Aug 2000, Ecass Dodebel wrote:
>
> > > > >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.
> > > >
> > > > 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.
>
>Bem, esta é difícil, fica para todos pensarem mais.
>
> > > >
> > > > 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.
>
>Os conjuntos N, Z, Q, NxN, N^k, Q^k, ... são todos infinitos enumeráveis.
>Os conjuntos R, RxN, R^k, ... são todos infinitos não enumeráveis com
>o mesmo cardinal.
>Isto é, existe bijeção entre quaisquer dois conjuntos da primeira lista
>ou entre quaisquer dois conjuntos da segunda lista, mas não existe bijeção
>entre um conjunto da primeira e um conjunto da segunda lista.
>
>Os problemas que discutíamos têm a dificuldade extra de exigir que a 
>bijeção
>tenha uma cara muito especial...
>
> > > > 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.
>
>Esta afirmação é falsa.
>
> > 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.
>
>Com este exemplo, f(0,0,1) = f(1,0,0) = 2.
>Mas acho que você tem uma idéia boa; pense mais.
>
>[]s, N.
>

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