Questão 1. Prove que a adição está definida para todos os pares de números naturais. (Dica: fixe um natural a e use indução sobre a segunda variável).
Passo 1
O enunciado pede para provar que a adição está definida para todos os pares de números naturais. Mais precisamente, devemos mostrar que, dado qualquer par
com
e
naturais, existe um único número natural
tal que
. O enunciado dá uma dica: “fixe um natural
e use indução sobre a segunda variável”. Informações relevantes extraídas do enunciado:
- Queremos provar totalidade e bem-definição da operação adição sobre
: para todo existe e é único o valor . - A sugestão é fixar
e fazer indução em . - Vamos usar a definição recursiva usual da adição (essa definição será explicitada no próximo passo).
Passo 2
Explicando a definição da adição que vamos usar (a versão canônica por recursão sobre o segundo argumento):
- Notação:
é o zero natural e indica o sucessor de . - Definição recursiva da adição (para todo
):
Comentário didático: essa é a definição que aparece nas construções formais (Peano/recursão primitiva). Ela diz que somar zero a
devolve
; somar o sucessor de
a
dá o sucessor do valor
. Repare que a definição de
usa
— por isso a prova por indução em
é a ferramenta natural: mostra que em cada etapa a expressão recursiva realmente produz um natural.
Passo 3
Princípio da indução que usaremos (lembrete didático):
- Para provar que uma propriedade
vale para todo basta mostrar: - Base:
é verdadeira. - Passo indutivo: para todo
, .
- Base:
- Aqui vamos fixar
e tomar como propriedade a afirmação "existe e é único tal que ". Vou primeiro provar existência para todos e depois provar unicidade, ambas por indução em .
Passo 4
Prova da existência (para um
fixo) — passo a passo:
- Defina a propriedade
por: := "existe tal que ". - Base
: pela definição recursiva temos explicitamente Como , existe (escolhendo ) com . Logo é verdadeira. - Passo indutivo: suponha
verdadeira, ou seja, suponha que existe com . Queremos provar , isto é, que existe algum com . - Pela definição recursiva da adição temos
- Pela hipótese indutiva
para algum ; portanto - E
é um natural (sucessor de natural é natural). Logo existe (escolhendo ) com .
- Pela definição recursiva da adição temos
- Conclusão do passo de existência: pelo princípio da indução, para o
fixo vale para todo . Ou seja, para cada existe pelo menos um natural tal que .
Passo 5
Prova da unicidade (para o mesmo
fixo) — por indução:
- Queremos mostrar que o valor de
é único: se e são naturais com e , então . - Defina a propriedade
por: "para todo , se e então ". - Base
: se e , mas pela definição . Logo , portanto . Assim é verdadeira. - Passo indutivo: suponha
verdadeira. Considere tais que e . Pela definição recursiva, mas para que isso faça sentido usamos que as igualdades são construtivas: existem e com e e então , . Pela hipótese indutiva . Então . Logo vale. - Conclusão da unicidade: por indução, para todo
vale . Portanto, para cada o valor é único.
Passo 6
Juntando os resultados e explicando a conclusão final:
- Fixando um
arbitrário, provamos por indução em que para todo existe exatamente um natural com . - Como
foi escolhido arbitrariamente, o argumento vale para todo . Portanto, para todo par existe e é único tal que . - Em linguagem funcional, isso significa que a operação
é uma função total : para cada entrada há exatamente uma saída. - Observação prática para a prova/exame: proceda sempre por reduzir
aplicando as regras até chegar a um natural sem mais envolvendo sucessores. Por exemplo, para calcular com essa definição (escrevendo e ): Isso demonstra concretamente que a recursão termina e produz um natural.