Defina pondo e . Prove que é uma bijeção (isto mostra que é enumerável).

Passo 1

Beleza, vamos lá! A questão pede pra gente provar que a função , definida por e , é uma bijeção. Isso quer dizer que cada par de números naturais corresponde a um número único e vice-versa. Para provar isso, vamos mostrar que a função é injetora (cada par m, n tem um único f(m, n)) e sobr injectora (cada número natural tem pelo menos um par m, n que mapeia para ele). Vamos precisar entender conceitos básicos de funções e propriedades de bijeções.

Passo 2

Primeiro, vamos provar que é injetora. Isso significa que se , então necessariamente e .
Assumamos que . Segundo a definição da função:
Então temos:
Como e são potências distintas de 2, a única maneira dessa igualdade ser verdadeira é que e . Consequentemente, . Portanto, é injetora.

Passo 3

Agora, vamos mostrar que é sobr injectora, ou seja, que para todo número natural , existe pelo menos um par tal que .
Qualquer número natural ímpar pode ser escrito como para algum . Para números pares, podemos fatorar a potência de 2. Vamos ver isso mais de perto:
  1. Se é ímpar, podemos escrever para algum . Então, e .
  2. Se é par, podemos fatorar a potência de 2. Suponha que , onde é o fator ímpar. Como todo número pode ser fatorado dessa maneira, existe sempre um par tal que .
Portanto, para qualquer , encontramos um par que mapeia para ele através de . Isso mostra que é sobr injectora.

Resposta

Concluímos que a função é tanto injetora quanto sobr injectora, ou seja, uma bijeção. Assim, é enumerável.

Exercícios relacionados

Determine conhecendo os valores de na base de .
© , tal que e
Indicando com card o número de elementos do conjunto finito , prove: Se e são finitos então é finito e .
Resolva o sistema linear:

Por escalonamento
Resolver a equação