Sejam
. Mostre que:
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):
Aqui S(b) significa o sucessor de b (b + 1).
Passo 3
Base da indução (p = 0): como n + 0 = n, temos
e também
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 é,
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,
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
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 ∈ ℕ.