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.