Questão 7. Prove que a multiplicação está definida para todos os pares de números naturais.
Passo 1
O que o enunciado pede e o que nos dá:
- O enunciado pede que se prove que a multiplicação está definida para todos os pares de números naturais.
- Informações que vamos usar (hipóteses padrão que a questão pressupõe):
- Existe o conjunto dos números naturais
(com o sucessor e a propriedade de indução). - A adição está definida para todos os pares de naturais (ou seja, para todo
o número existe e é único).
- Existe o conjunto dos números naturais
- Objetivo preciso a provar: para todo
existe e é único um natural que se chama produto . Em linguagem lógica: provar que existe uma função tal que, para todos , está bem definido (e, usualmente, satisfaz as regras recursivas que vamos definir).
Passo 2
Ideia do método (intuição antes da prova): multiplicação é “soma repetida”. Logo faz sentido defini-la recursivamente em relação a um dos fatores (por exemplo, o segundo): para qualquer
fixo, define-se
Para tornar isso lógico precisamos mostrar duas coisas principais:
- Essa definição fornece, para todo
, um valor (existência). - Esse valor é único — não há ambiguidade (unicidade).
A ferramenta natural para esse tipo de prova é a indução em(provar que para todo a propriedade “para todo , existe e é único” é verdadeira).
Passo 3
Enunciando a propriedade a provar por indução: para cada
consideramos a proposição
Vamos provar
para todo
por indução em
.
Passo 4
Base da indução (
):
- Tomar qualquer
. Definimos Pela hipótese (aditiva) sabemos que . Assim, para todo existe um natural que serve como . - Unicidade no caso
: se alguém propuser outro número como , a definição canônica exige que o produto com seja . Portanto não há ambiguidade: é único e igual a .
Logo
é verdadeira.
Passo 5
Passo indutivo: suponha
verdadeira para algum
; isto é, suponha que para todo
o produto
existe e é único. Vamos provar
: para todo
devemos mostrar que
existe e é único.
-
Construção (existência): para um
fixo, pela hipótese indutiva sabemos que o número existe. Como a adição está definida para todos os pares, o número existe e pertence a. Definimos Assim, para qualquerconstruímos um elemento de que serve como . Isso prova existência. -
Unicidade: suponha que exista algum outro
que também se pretende ser obedecendo à regra recursiva (isto é, suponha que haja uma construção alternativa que dá um número tal que, segundo essa construção, se obtém como com sendo o produto correspondente a ). Pela hipótese indutiva, o valor de é único; pela unicidade da soma (adicionalmente assumida: soma de dois naturais é única), o valor é único. Logo qualquer candidato deve coincidir com . Portanto é único.
Assim
é verdadeira.
Passo 6
Conclusão pela indução: por indução em
,
vale para todo
. Ou seja, para todo
e para todo
existe e é único o produto
definido recursivamente por
Isso fornece, de forma consistente, uma função
(tomando o segundo argumento como parâmetro de recursão). Além disso, um argumento análogo mostra que se houvesse qualquer outra operação que satisfaça as mesmas regras recursivas ela coincide com esta (unicidade da operação inteira), pois os valores coincidem para
e a igualdade é preservada pelo passo sucessor.
Passo 7
Resumo didático e reforço (como usar isso na prova):
- Na prova da questão da prova final basta apresentar a definição recursiva e então aplicar indução no segundo fator
mostrando o caso base e o passo indutivo . - A razão prática: para cada
fixo a multiplicação por é construída passo a passo somando repetidas vezes; a indução garante que esse processo atinge todos os e não deixa ambiguidade. - Se em outro exercício pedirem para provar propriedades (associatividade, comutatividade, distributividade), pode-se usar novamente indução e a definição recursiva que acabamos de fixar.
Resposta
Para todo
existe e é único o produto
definido recursivamente por
e
.