Questão 6 Defina f: \mathbb{N} X \mathbb{N}, pondo f(1, n)=2 n-1 e f(m+1, n)=2^{m} \cdot(2 n-1). Mostre que f é uma bijeção.

Passo 1

O enunciado define uma função f com domínio \mathbb{N}\times\mathbb{N} pelas regras
f(1,n)=2n-1
e
f(m+1,n)=2^{m}\cdot(2n-1).
O que o problema pede: mostrar que f é uma bijeção (ou seja, que é injetora e sobrejetora).
Informações relevantes dadas:
  • Para m=1 temos f(1,n)=2n-1, que é um número ímpar positivo.
  • Para m+1 a expressão envolve uma potência de 2 multiplicando um número ímpar: 2^{m}(2n-1).
    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 m=1 temos f(1,n)=2^{0}(2n-1), e a regra geral dada para m+1 é exatamente
f(m+1,n)=2^{m}(2n-1).
Por indução em m (ou por observação direta da recorrência) segue que, para todo m\in\mathbb{N} (assumindo \mathbb{N}=\{1,2,3,\dots\}),
f(m,n)=2^{\,m-1}\bigl(2n-1\bigr).
Ou seja, f envia o par (m,n) no número obtido multiplicando uma potência de 2 por um inteiro ímpar.
Breve explicação didática da indução usada: a base m=1 é verdadeira porque 2^{1-1}(2n-1)=2^{0}(2n-1)=2n-1. Se a fórmula vale para m, então para m+1 a regra do enunciado dá f(m+1,n)=2^{m}(2n-1), que é exatamente o caso m substituído por m+1. Assim a fórmula fechada está provada.

Passo 3

Estratégia para mostrar bijeção: faremos duas coisas separadas (e explicadas com calma)
  1. Provar que f é sobrejetora: todo y\in\mathbb{N} é imagem de algum (m,n).
  2. Provar que f é injetora: se f(m,n)=f(m',n') então (m,n)=(m',n').
A ferramenta-chave que vamos usar (e que explico abaixo) é a decomposição única de um inteiro positivo em uma potência de 2 multiplicada por um número ímpar.
Explicação dessa ferramenta (sem jargões): dado qualquer inteiro positivo y, pode-se dividir repetidamente por 2 até obter um número ímpar. Mais formalmente, existe um inteiro k\ge 0 e um inteiro ímpar s\ge 1 tais que
y = 2^{k}s.
Esse k é o número de vezes que y é divisível por 2. Esse par (k,s) é único: não há duas maneiras diferentes de escrever y como potência de 2 vezes um ímpar, porque se houvesse duas escritas com expoentes diferentes, uma das expressões teria um fator 2 que a outra não teria, o que dá contradição — na prática, o procedimento de “dividir por 2 enquanto possível” produz um único k e um único s. Esse é um caso simples do que chamam de fatorização em potências de 2 (é consequência imediata da fatorização única em primos, mas pode ser visto de forma elementar pelo algoritmo de divisão por 2).

Passo 4

Provar que f é sobrejetora (cada y\in\mathbb{N} tem um antecedente).
Pegue um y\in\mathbb{N}. Pela observação do passo anterior, existe um único k\ge 0 e um único inteiro ímpar s\ge 1 tais que
y=2^{k}s.
Como s é ímpar, existe n\in\mathbb{N} tal que s=2n-1 (basta tomar n=(s+1)/2, que é inteiro porque s é ímpar). Agora escolha m=k+1. Então, usando a fórmula fechada checada no Passo 2:
f(m,n)=f(k+1,n)=2^{(k+1)-1}\bigl(2n-1\bigr)=2^{k}s=y.
Portanto y tem preimagem (m,n)=(k+1,n). Como y foi arbitrário, f é sobrejetora.
Exemplo concreto para fixar a ideia: se y=12, dividir por 2 6 (ainda par), dividir por 2 3 (ímpar). Logo k=2, s=3, e 3=2\cdot 2-1 com n=2. Tomando m=k+1=3 obtemos f(3,2)=2^{2}(2\cdot 2-1)=4\cdot 3=12.

Passo 5

Provar que f é injetora (ou seja, não leva pares distintos a um mesmo valor).
Suponha que
f(m,n)=f(m',n').
Usando a forma fechada, isso é
2^{\,m-1}\bigl(2n-1\bigr)=2^{\,m'-1}\bigl(2n'-1\bigr).
Observe que 2n-1 e 2n'-1 são números ímpares. Sem perda de generalidade suponha m\le m'. Dividindo ambos os lados por 2^{\,m-1} obtemos
2n-1 = 2^{\,m'-m}\bigl(2n'-1\bigr).
Se m'<m o mesmo raciocínio com papéis trocados dá resultado análogo; portanto considerar m\le m' é suficiente. No membro direito, se m'-m\ge 1 então há um fator 2 multiplicando (2n'-1), logo o membro direito é par, mas o membro esquerdo 2n-1 é ímpar — contradição. Portanto não pode ser m'-m\ge 1; temos então m'-m=0, isto é, m'=m. Substituindo de volta:
2n-1=2n'-1,
logo n=n'. Assim (m,n)=(m',n'). Isso prova injetividade.
Intuição simples: a potência de 2 que aparece no fator é determinada pelo número de divisões por 2 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 f é injetora e sobrejetora, f é bijeção. Podemos ainda escrever explicitamente a função inversa f^{-1}:\mathbb{N}\to\mathbb{N}\times\mathbb{N}: dado y\in\mathbb{N}, escreva y=2^{k}s com s ímpar (procedimento: dividir por 2 enquanto possível); então
f^{-1}(y)=\bigl(k+1,\,(s+1)/2\bigr).
Verificar que essa é de fato inversa é imediato calculando f(k+1,(s+1)/2)=2^{k}s=y e usando a unicidade da decomposição para a outra composição.
Portanto ficou provado (com construção explícita da inversa) que f é bijeção.

Resposta

f é bijeção; \displaystyle f^{-1}(y)=\bigl(k+1,\tfrac{s+1}{2}\bigr) onde y=2^{k}s com s ímpar.

Exercícios relacionados