Mostre que N times N=(m, n) ; m, n in N é um conjunto enumerável.

Passo 1

O enunciado pede para mostrar que NtimesN=(m,n);,m,ninN é enumerável, ou seja, que existe uma bijeção entre N e NtimesN. O conteúdo da matéria envolve cardinalidade de conjuntos e definição de conjunto enumerável (contável).

Passo 2

Uma construção clássica é a chamada função de emparelhamento de Cantor. Definimos
fcolon NtimesNtoN, f(m,n)=(m+n)(m+n+1)2+n
Mostraremos que f é bijetora, o que implica que NtimesN tem a mesma cardinalidade de N.

Passo 3

Para provar que f é injetora, suponha
f(m,n)=f(m',n')
Note que o termo tfrac(m+n)(m+n+1)2 cresce estritamente com m+n. Se m+nneq m'+n', teríamos duas somas triangulares distintas, logo f(m,n)neq f(m',n'). Portanto deve ocorrer m+n=m'+n'. Subtraindo dos dois lados a mesma soma triangular, obtemos n=n' e, consequentemente, m=m'. Assim f é injetora.

Passo 4

Para provar que f é sobrejetora, seja kinN. Escolhemos s tal que
s(s+1)2<= k < (s+1)(s+2)2
Definimos então
n = k - s(s+1)2, m = s - n
Pelo modo de escolha de s, ambos m e n são naturais e
f(m,n) = (m+n)(m+n+1)2 + n = s(s+1)2 + l(k - s(s+1)2r) = k
Logo todo k tem um antecessor (m,n), provando que f é sobrejetora.

Resposta

Como f é injetora e sobrejetora, ela é bijetora. Portanto existe bijeção entre N e NtimesN, isto é, NtimesN é enumerável.

Exercícios relacionados