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:
- Se
é ímpar, podemos escrever para algum . Então, e . - 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
Por escalonamento
Resolver a equação