Re: Bije��o entre NxN e N

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

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.