Questão 6 Defina
, pondo
e
. Mostre que
é uma bijeção.
Passo 1
O enunciado define uma função
com domínio
pelas regras
e
O que o problema pede: mostrar que
é uma bijeção (ou seja, que é injetora e sobrejetora).
Informações relevantes dadas:
Informações relevantes dadas:
- Para
temos , que é um número ímpar positivo. - Para
a expressão envolve uma potência de multiplicando um número ímpar: .
Não se faz nada de resolução neste passo — apenas listar o que foi dado e o que precisa ser mostrado.
Passo 2
Primeiro simplifico a forma da função para usar uma expressão única. Observando as duas definições: para
temos
, e a regra geral dada para
é exatamente
Por indução em
(ou por observação direta da recorrência) segue que, para todo
(assumindo
),
Ou seja,
envia o par
no número obtido multiplicando uma potência de
por um inteiro ímpar.
Breve explicação didática da indução usada: a base
é verdadeira porque
. Se a fórmula vale para
, então para
a regra do enunciado dá
, que é exatamente o caso
substituído por
. Assim a fórmula fechada está provada.
Passo 3
Estratégia para mostrar bijeção: faremos duas coisas separadas (e explicadas com calma)
- Provar que
é sobrejetora: todo é imagem de algum . - Provar que
é injetora: se então .
A ferramenta-chave que vamos usar (e que explico abaixo) é a decomposição única de um inteiro positivo em uma potência de
multiplicada por um número ímpar.
Explicação dessa ferramenta (sem jargões): dado qualquer inteiro positivo
, pode-se dividir repetidamente por
até obter um número ímpar. Mais formalmente, existe um inteiro
e um inteiro ímpar
tais que
Esse
é o número de vezes que
é divisível por
. Esse par
é único: não há duas maneiras diferentes de escrever
como potência de
vezes um ímpar, porque se houvesse duas escritas com expoentes diferentes, uma das expressões teria um fator
que a outra não teria, o que dá contradição — na prática, o procedimento de “dividir por
enquanto possível” produz um único
e um único
. Esse é um caso simples do que chamam de fatorização em potências de
(é consequência imediata da fatorização única em primos, mas pode ser visto de forma elementar pelo algoritmo de divisão por
).
Passo 4
Provar que
é sobrejetora (cada
tem um antecedente).
Pegue um
. Pela observação do passo anterior, existe um único
e um único inteiro ímpar
tais que
Como
é ímpar, existe
tal que
(basta tomar
, que é inteiro porque
é ímpar). Agora escolha
. Então, usando a fórmula fechada checada no Passo 2:
Portanto
tem preimagem
. Como
foi arbitrário,
é sobrejetora.
Exemplo concreto para fixar a ideia: se
, dividir por
dá
(ainda par), dividir por
dá
(ímpar). Logo
,
, e
com
. Tomando
obtemos
.
Passo 5
Provar que
é injetora (ou seja, não leva pares distintos a um mesmo valor).
Suponha que
Usando a forma fechada, isso é
Observe que
e
são números ímpares. Sem perda de generalidade suponha
. Dividindo ambos os lados por
obtemos
Se
o mesmo raciocínio com papéis trocados dá resultado análogo; portanto considerar
é suficiente. No membro direito, se
então há um fator
multiplicando
, logo o membro direito é par, mas o membro esquerdo
é ímpar — contradição. Portanto não pode ser
; temos então
, isto é,
. Substituindo de volta:
logo
. Assim
. Isso prova injetividade.
Intuição simples: a potência de
que aparece no fator é determinada pelo número de divisões por
que o valor tem; como os outros fatores são ímpares, essa potência não se confunde com o fator ímpar — por isso a representação é única e dois pares diferentes não podem produzir o mesmo número.
Passo 6
Como
é injetora e sobrejetora,
é bijeção. Podemos ainda escrever explicitamente a função inversa
: dado
, escreva
com
ímpar (procedimento: dividir por
enquanto possível); então
Verificar que essa é de fato inversa é imediato calculando
e usando a unicidade da decomposição para a outra composição.
Portanto ficou provado (com construção explícita da inversa) que
é bijeção.