Demonstre as propriedades da multiplicação,
.
Associatividade:
Associatividade:
Passo 1
O que o enunciado pede e o que nos é dado.
- Pede: provar que a multiplicação é associativa, ou seja,
- Dados relevantes (definições/hipóteses que usaremos):
- Os números naturais
pertencem a . - A multiplicação está definida recursivamente (definição padrão baseada nos axiomas de Peano):
- Os números naturais
- A adição está definida recursivamente (definição padrão):
- Observação: para provar a associatividade da multiplicação vamos precisar de duas propriedades auxiliares bem conhecidas e prováveis de já serem aceitas ou demonstradas antes: (i) associatividade da adição e (ii) distributividade da multiplicação sobre a adição à esquerda. Vou demonstrar ambas antes de usar na prova final.
Passo 2
Explicando a estratégia: vamos provar a propriedade usando provas por indução (princípio da indução sobre
) e duas lemmas necessárias.
- Princípio da indução (em palavras): para provar uma propriedade
para todo basta provar e provar que . - Plano:
- Provar a associatividade da adição:
. - Provar a distributividade à esquerda:
. - Usar a distributividade e a associatividade da adição para provar, por indução em
, que .
- Provar a associatividade da adição:
Vou desenvolver cada item com detalhes e contas explicadas.
Passo 3
Lemma 1 — associatividade da adição.
Queremos provar:
Prova por indução em
.
-
Base
: usando (A1), eLogo. -
Passo indutivo: suponha que para um
fixo vale para todos . Queremos mostrar . Começamos por usar (A2) para reescrever os lados:ePela hipótese indutiva temos. Substituindo: Agora aplicamos a definição da adição (A2) “ao contrário” para mover o: Assim.
Portanto, por indução, a adição é associativa:
Passo 4
Lemma 2 — distributividade da multiplicação à esquerda.
Queremos provar:
Prova por indução em
(fixando
arbitrários).
-
Base
: usando (A1) e (M1), eLogo. -
Passo indutivo: suponha
para um certo . Queremos provar . Use (A2) para escreverentão por definição da multiplicação (M2),Pela hipótese indutiva, então Pelo lado direito desejado,Agora aplicamos a associatividade da adição (Lemma 1) para reorganizar:Assim.
Portanto, por indução em
,
Passo 5
Agora provamos a associatividade da multiplicação propriamente dita:
Faremos prova por indução em
(fixando
arbitrários).
-
Base
: usando (M1) e o fato de , eLogo. -
Passo indutivo: suponha que para um
fixo vale Queremos mostrarComeçamos transformandopor (M2): Assim, o lado esquerdo éAgora aplicamos a distributividade (Lemma 2) come : Pela hipótese indutiva, então Aplicando a definição da multiplicação (M2) agora ao produto, temos Portanto
Assim, por indução em
, a propriedade vale para todo
. Como
foram arbitrários, concluímos: