Utilize o primeiro princípio da indução e a definição de adição em N para demostrar a lei do cancelamento da adição: se m, n, p in N satisfazem m+p=n+p, então m=n.

Passo 1

O que queremos provar é a seguinte proposição, chamada lei do cancelamento da adição em N:
“Se m,p,ninN e
m + p ;=; n + p,
então
m = n
Para isso, vamos usar o princípio da indução sobre o parâmetro p e a definição recursiva da adição em N:
m + 0 = m, m + succ(p) = succ(m + p)
Também precisaremos do fato de que o sucessor é injetivo:
succ(a)=succ(b)Longrightarrow a=b

Passo 2

Definimos a propriedade P(p) para todo pinN como:
P(p);: Para todos (m,ninN), se (m+p = n+p) então (m=n) ã

Passo 3

Base da indução ( p=0):
Suponha m+0 = n+0. Pela definição de adição, m+0 = m e n+0 = n. Logo
m = n
diretamente. Assim, P(0) é verdadeira.

Passo 4

Passo indutivo: suponha P(p) verdadeira, ou seja,
se m+p = n+p então m=n ã
Precisamos mostrar P(succ(p)): suponha
m + succ(p) ;=; n + succ(p)
Pela definição recursiva da adição temos
succl(m + pr);=;succl(n + pr)
Pela injetividade do sucessor concluímos
m + p = n + p
Então, pela hipótese indutiva P(p), vem
m = n
Isso mostra que P(succ(p)) também vale.

Resposta

Pela indução em p, concluímos que para todo pinN vale P(p), ou seja, sempre que m+p=n+p então m=n.

Exercícios relacionados