Use o Principio da Indução Finita para provar a propriedade associativa da adição em N, ou seja:
sejam quais forem
.
Passo 1
O que o problema pede e o que nos foi dado.
- Pede-se provar que a adição é associativa em
; isto é, provar a igualdade
para todos
.
- Informações relevantes que vamos usar (definição de adição via axiomas de Peano / definição usual por recorrência):
- Para todo
, - Para todo
, onde é o sucessor de (isto é, na notação habitual).
- Para todo
- O enunciado pede prova para todos os naturais; portanto vamos usar o Princípio da Indução Finita (indução) em uma das variáveis
. Não vamos ainda decidir qual, só listei as informações que temos.
Passo 2
Breve explicação do Princípio da Indução Finita e como vamos aplicá-lo.
- O Princípio da Indução Finita (forma usual) diz: seja
uma propriedade sobre naturais. Se -
é verdadeira (caso base), e - para todo
, implica (passo indutivo),
entãoé verdadeira para todo .
-
- Estratégia: fixamos
e arbitrários e provaremos a propriedade em por indução. Ou seja, para cada par fixo vamos provar a propriedade para todo por indução em . - Justificativa informal da escolha: a adição está definida recursivamente no segundo parâmetro (pela definição
), então é natural induzir sobre . Isso torna as transformações diretas pela definição de simples de aplicar.
Passo 3
Estabelecendo o caso base
.
- Devemos provar
, isto é: - Usamos a definição
aplicada aos termos: - Primeiro,
porque para todo vale ; aqui . - Segundo,
pela mesma definição; então .
- Primeiro,
- Conclusão do caso base:
logo é verdadeira.
Passo 4
Formulação da hipótese de indução.
- Suponha agora, para um
arbitrário, que é verdadeira; isto é, suponha a hipótese de indução: - A partir dessa hipótese queremos deduzir
, ou seja:
Passo 5
Aplicando a definição de adição ao membro esquerdo no passo indutivo.
- Use a definição recursiva
com e . Assim (Justificação: a definição diz exatamente que somar o sucessor de equivale ao sucessor da soma com .)
Passo 6
Usando a hipótese de indução para substituir dentro do sucessor.
- Pela hipótese de indução sabemos que
. Substituindo essa igualdade dentro do lado direito de Passo 5 obtemos: (Aqui só substituí uma expressão igual por outra igual, coisa válida.)
Passo 7
Transformando o sucessor para obter o membro direito desejado.
- Observe a definição
novamente, agora com e . Essa definição afirma: - Comparando com o que temos em Passo 6, concluímos
- Finalmente, use a identidade
(definição de adição aplicada a e ) para ver que Portanto Isso é exatamente .
Passo 8
Conclusão por indução e comentário final.
- Fomos capazes de provar
(Passo 3) e de mostrar que (Passos 4–7). Pelo Princípio da Indução Finita, segue que é verdadeira para todo . - Como
e eram arbitrários, a igualdade vale para todos . Assim a adição é associativa em .
Passo 9
Exemplo numérico rápido (para fixar a intuição).
- Tome
, , . Então e Igualdade verificada no caso concreto; a prova anterior mostra que isso vale sempre.