Sejam m, n, p in N. Mostre que:
m+(n+p)=(m+n)+p

Passo 1

O enunciado pede para provar a associatividade da adição em ℕ, ou seja, mostrar que para quaisquer m, n, p ∈ ℕ vale m + (n + p) = (m + n) + p. Vamos usar a definição recursiva de adição e o princípio da indução em p.

Passo 2

Definição recursiva de adição (base para nossa prova):
a + 0 = a
a + S(b) = Sl(a + br)
Aqui S(b) significa o sucessor de b (b + 1).

Passo 3

Base da indução (p = 0): como n + 0 = n, temos
m + (n + 0) = m + n
e também
(m + n) + 0 = m + n
Logo m + (n + 0) = (m + n) + 0, fechando o caso base.

Passo 4

Passo indutivo: suponha que para um p arbitrário a propriedade já valha, isto é,
m + (n + p) = (m + n) + p
Devemos mostrar que ela vale para p + 1.

Passo 5

Provar para p + 1: começamos por m + (n + (p + 1)). Usando a definição,
n + (p + 1) = S(n + p),
então
$$m + (n + (p + 1)) = m + S(n + p) = S\bigl(m + (n + p)\bigr).
$$
Pela hipótese indutiva m + (n + p) = (m + n) + p, logo
$$S\bigl(m + (n + p)\bigr) = S\bigl((m + n) + p\bigr).
$$
Por outro lado,
$$(m + n) + (p + 1) = S\bigl((m + n) + p\bigr).
$$
Concluímos que
m + (n + (p + 1)) = m + S(n + p) = Sl(m + (n + p)r)
fechando o passo indutivo.

Passo 6

Pelo princípio da indução em p, a igualdade m + (n + p) = (m + n) + p vale para todo p ∈ ℕ. Como m e n eram arbitrários, vale para quaisquer m, n, p ∈ ℕ.

Resposta

m + (n + p) = (m + n) + p

Exercícios relacionados