Mostrar que
f: N times N N dada por f((m, n))=2^m-1(2 n-1)
é uma correspondência biunívoca.

Passo 1

O enunciado pede para mostrar que a função
fcolon NtimesNtoN, f((m,n))=2^m-1(2n-1)
é bijetora.
O que vamos usar é o teorema da fatoração única em N: todo número natural k>=1 pode ser escrito de modo único como
k=2^a b,
onde a>=0 é o expoente de 2 e b é um número ímpar.

Passo 2

Mostramos que f é injetiva. Suponha
f((m,n))=f((m',n'))
Então
2^m-1(2n-1)=2^m'-1(2n'-1)
Pela fatoração única, a potência de 2 de um lado deve coincidir com a do outro, ou seja m-1=m'-1, logo m=m'. Dividindo ambos os lados por 2^m-1 obtemos
2n-1=2n'-1,
isto é, n=n'. Logo (m,n)=(m',n') e f é injetiva.

Passo 3

Mostramos que f é sobrejetiva. Seja kinN qualquer. Pela fatoração única, escreve-se
k=2^a b,
com a>=0 e b ímpar. Então coloque
m=a+1, 2n-1=b,
isto é,
n=b+12inN
Dessa forma
f((m,n))=2^(a+1)-1(2cdottfracb+12-1) =2^a,b =k,
mostrando que todo k tem pelo menos uma origem em NtimesN.

Resposta

A função f((m,n))=2^m-1(2n-1) é bijetora, ou seja, estabelece uma correspondência biunívoca entre NtimesN e N.

Exercícios relacionados