Utilize o primeiro princípio da indução e a definição de adição em
para demostrar a lei do cancelamento da adição: se
satisfazem
, então
.
Passo 1
O que queremos provar é a seguinte proposição, chamada lei do cancelamento da adição em
:
“Se e
“Se
então
Para isso, vamos usar o princípio da indução sobre o parâmetro
e a definição recursiva da adição em
:
Também precisaremos do fato de que o sucessor é injetivo:
Passo 2
Definimos a propriedade
para todo
como:
Passo 3
Base da indução (
):
Suponha . Pela definição de adição,
e
. Logo
Suponha
diretamente. Assim,
é verdadeira.
Passo 4
Passo indutivo: suponha
verdadeira, ou seja,
Precisamos mostrar
: suponha
Pela definição recursiva da adição temos
Pela injetividade do sucessor concluímos
Então, pela hipótese indutiva
, vem
Isso mostra que
também vale.
Resposta
Pela indução em
, concluímos que para todo
vale
, ou seja, sempre que
então
.