Use o Principio da Indução Finita para provar a propriedade associativa da adição em N, ou seja:
(m+n)+p=m+(n+p)
sejam quais forem m, n, p \in N.

Passo 1

O que o problema pede e o que nos foi dado.
  • Pede-se provar que a adição é associativa em \mathbb{N}; isto é, provar a igualdade
(m+n)+p = m+(n+p)
para todos m,n,p \in \mathbb{N}.
  • Informações relevantes que vamos usar (definição de adição via axiomas de Peano / definição usual por recorrência):
    • Para todo a\in\mathbb{N}, a+0 = a.
    • Para todo a,b\in\mathbb{N}, a+S(b) = S(a+b),onde S(b) é o sucessor de b (isto é, S(b)=b+1 na notação habitual).
  • 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 m,n,p. 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 P(k) uma propriedade sobre naturais. Se
    1. P(0) é verdadeira (caso base), e
    2. para todo k, P(k) implica P(S(k)) (passo indutivo),
      então P(k) é verdadeira para todo k\in\mathbb{N}.
  • Estratégia: fixamos m e n arbitrários e provaremos a propriedade em p por indução. Ou seja, para cada par fixo (m,n) vamos provar a propriedade P(p):\quad (m+n)+p = m+(n+p)para todo p por indução em p.
  • Justificativa informal da escolha: a adição está definida recursivamente no segundo parâmetro (pela definição a+S(b)=S(a+b)), então é natural induzir sobre p. Isso torna as transformações diretas pela definição de + simples de aplicar.

Passo 3

Estabelecendo o caso base p=0.
  • Devemos provar P(0), isto é: (m+n)+0 = m+(n+0).
  • Usamos a definição a+0=a aplicada aos termos:
    • Primeiro, (m+n)+0 = m+n porque para todo x vale x+0=x; aqui x=m+n.
    • Segundo, n+0 = n pela mesma definição; então m+(n+0)=m+n.
  • Conclusão do caso base: (m+n)+0 = m+n = m+(n+0),logo P(0) é verdadeira.

Passo 4

Formulação da hipótese de indução.
  • Suponha agora, para um p arbitrário, que P(p) é verdadeira; isto é, suponha a hipótese de indução: (m+n)+p = m+(n+p).
  • A partir dessa hipótese queremos deduzir P(S(p)), ou seja: (m+n)+S(p) = m+(n+S(p)).

Passo 5

Aplicando a definição de adição ao membro esquerdo no passo indutivo.
  • Use a definição recursiva a+S(b)=S(a+b) com a=(m+n) e b=p. Assim (m+n)+S(p) = S\big((m+n)+p\big).(Justificação: a definição diz exatamente que somar o sucessor de p equivale ao sucessor da soma com p.)

Passo 6

Usando a hipótese de indução para substituir dentro do sucessor.
  • Pela hipótese de indução sabemos que (m+n)+p = m+(n+p). Substituindo essa igualdade dentro do lado direito de Passo 5 obtemos: (m+n)+S(p) = S\big(m+(n+p)\big).(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 a+S(b)=S(a+b) novamente, agora com a=m e b=(n+p). Essa definição afirma: m+S(n+p) = S\big(m+(n+p)\big).
  • Comparando com o que temos em Passo 6, concluímos (m+n)+S(p) = S\big(m+(n+p)\big) = m+S(n+p).
  • Finalmente, use a identidade n+S(p)=S(n+p) (definição de adição aplicada a n e p) para ver que m+S(n+p) = m+(n+S(p)).Portanto (m+n)+S(p) = m+(n+S(p)).Isso é exatamente P(S(p)).

Passo 8

Conclusão por indução e comentário final.
  • Fomos capazes de provar P(0) (Passo 3) e de mostrar que P(p)\Rightarrow P(S(p)) (Passos 4–7). Pelo Princípio da Indução Finita, segue que P(p) é verdadeira para todo p\in\mathbb{N}.
  • Como m e n eram arbitrários, a igualdade vale para todos m,n,p\in\mathbb{N}. Assim a adição é associativa em \mathbb{N}.

Passo 9

Exemplo numérico rápido (para fixar a intuição).
  • Tome m=2, n=3, p=1. Então (m+n)+p = (2+3)+1 = 5+1 = 6,e m+(n+p) = 2+(3+1) = 2+4 = 6.Igualdade verificada no caso concreto; a prova anterior mostra que isso vale sempre.

Resposta

\forall m,n,p\in\mathbb{N}:\quad (m+n)+p = m+(n+p)

Exercícios relacionados