Para cada um dos itens abaixo, defina (indicando domínio e contradomínio) e determine se é injetiva, sobrejetiva ou bijetiva uma função que a cada:
dois números naturais associa seu MDC;
dois números naturais associa seu MDC;
Passo 1
O enunciado pede: definir (com domínio e contradomínio) e determinar se é injetiva, sobrejetiva ou bijetiva uma função que a cada dois números naturais associa seu MDC.\n
Informações relevantes dadas (implícitas no enunciado): temos pares de números naturais e a operação que associa a cada par o seu máximo divisor comum (MDC). Não foi especificado se contém o zero; vou adotar a convenção usual aqui:
.
Informações relevantes dadas (implícitas no enunciado): temos pares de números naturais e a operação que associa a cada par o seu máximo divisor comum (MDC). Não foi especificado se
Passo 2
Definição do que é MDC (para garantir que entendemos a função): dado
, chamamos
(ou MDC) o maior número natural
tal que
divide
e
divide
. Aqui “divide” significa:
divide
se existe
com
. Exemplos simples para fixar a ideia:
porque
é o maior natural que divide tanto
quanto
;
porque não têm divisores comuns maiores que
.
Passo 3
Definição da função pedida (indicando domínio e contradomínio): defino
por
para todo
. Aqui o domínio é
(pares ordenados de naturais) e o contradomínio é
.
Passo 4
Conceito de injetividade (explicação didática):
é injetiva se pares distintos no domínio nunca têm a mesma imagem; formalmente,
Teste prático para ver se
é injetiva: basta encontrar dois pares diferentes que têm a mesma imagem. Vou dar um exemplo geral e depois um exemplo numérico concreto. Para qualquer
temos
porque
é divisor de
e não existe divisor comum maior que
. Também
porque qualquer divisor comum de
e
divide
, e
divide ambos, logo o máximo divisor comum é
. Portanto os pares
e
são distintos (pois
para
) mas têm a mesma imagem
. Exemplo concreto:
e
; os pares
e
são diferentes mas têm a mesma imagem. Conclusão:
não é injetiva.
Passo 5
Conceito de sobrejetividade (explicação didática):
é sobrejetiva se todo elemento do contradomínio é imagem de algum elemento do domínio; formalmente,
Prova de que
é sobrejetiva: tome qualquer
. Basta encontrar um par
com
. Uma escolha óbvia é
. Como já argumentamos,
Logo para cada
existe pelo menos um par
que tem imagem
. Assim
é sobrejetiva.
Passo 6
Conclusão final sobre bijetividade: uma função é bijetiva se for simultaneamente injetiva e sobrejetiva. Aqui vimos que
é sobrejetiva mas não é injetiva. Portanto
não é bijetiva.\n
(Observação curta: se alguém usar a convenção contendo
, convém verificar a definição de
; por segurança escolhemos
para evitar essa sutileza.)
(Observação curta: se alguém usar a convenção