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 (a,b) com a e b naturais, existe um único número natural c tal que a+b=c. O enunciado dá uma dica: “fixe um natural a 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 \mathbb{N}: para todo a,b\in\mathbb{N} existe e é único o valor a+b\in\mathbb{N}.
  • A sugestão é fixar a e fazer indução em b.
  • 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: 0 é o zero natural e S(n) indica o sucessor de n.
  • Definição recursiva da adição (para todo a,b\in\mathbb{N}): a+0 = a,
a+S(b)=S(a+b).
Comentário didático: essa é a definição que aparece nas construções formais (Peano/recursão primitiva). Ela diz que somar zero a a devolve a; somar o sucessor de b a a dá o sucessor do valor a+b. Repare que a definição de a+S(b) usa a+b — por isso a prova por indução em b é 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 P(b) vale para todo b\in\mathbb{N} basta mostrar:
    1. Base: P(0) é verdadeira.
    2. Passo indutivo: para todo b, P(b)\Rightarrow P(S(b)).
  • Aqui vamos fixar a\in\mathbb{N} e tomar como propriedade P(b) a afirmação "existe e é único c\in\mathbb{N} tal que a+b=c". Vou primeiro provar existência para todos b e depois provar unicidade, ambas por indução em b.

Passo 4

Prova da existência (para um a fixo) — passo a passo:
  • Defina a propriedade P(b) por: P(b) := "existe c\in\mathbb{N} tal que a+b=c".
  • Base b=0: pela definição recursiva temos explicitamente a+0 = a.Como a\in\mathbb{N}, existe c (escolhendo c:=a) com a+0=c. Logo P(0) é verdadeira.
  • Passo indutivo: suponha P(b) verdadeira, ou seja, suponha que existe c\in\mathbb{N} com a+b=c. Queremos provar P(S(b)), isto é, que existe algum d\in\mathbb{N} com a+S(b)=d.
    • Pela definição recursiva da adição temos a+S(b)=S(a+b).
    • Pela hipótese indutiva a+b=c para algum c\in\mathbb{N}; portanto a+S(b)=S\text{(c)}.
    • E S\text{(c)} é um natural (sucessor de natural é natural). Logo existe d\in\mathbb{N} (escolhendo d:=S\text{(c)}) com a+S(b)=d.
  • Conclusão do passo de existência: pelo princípio da indução, para o a fixo vale P(b) para todo b\in\mathbb{N}. Ou seja, para cada b existe pelo menos um natural c tal que a+b=c.

Passo 5

Prova da unicidade (para o mesmo a fixo) — por indução:
  • Queremos mostrar que o valor de a+b é único: se c e c' são naturais com a+b=c e a+b=c', então c=c'.
  • Defina a propriedade Q(b) por: "para todo c,c'\in\mathbb{N}, se a+b=c e a+b=c' então c=c'".
  • Base b=0: se a+0=c e a+0=c', mas pela definição a+0=a. Logo c=a=c', portanto c=c'. Assim Q(0) é verdadeira.
  • Passo indutivo: suponha Q(b) verdadeira. Considere c,c' tais que a+S(b)=c e a+S(b)=c'. Pela definição recursiva, c = a+S(b)=S(a+b),\qquad c' = a+S(b)=S(a+b),mas para que isso faça sentido usamos que as igualdades são construtivas: existem u e u' com a+b=u e a+b=u' e então c=S(u), c'=S(u'). Pela hipótese indutiva u=u'. Então c=S(u)=S(u')=c'. Logo Q(S(b)) vale.
  • Conclusão da unicidade: por indução, para todo b vale Q(b). Portanto, para cada b o valor a+b é único.

Passo 6

Juntando os resultados e explicando a conclusão final:
  • Fixando um a arbitrário, provamos por indução em b que para todo b existe exatamente um natural c com a+b=c.
  • Como a foi escolhido arbitrariamente, o argumento vale para todo a\in\mathbb{N}. Portanto, para todo par (a,b)\in\mathbb{N}\times\mathbb{N} existe e é único c\in\mathbb{N} tal que a+b=c.
  • Em linguagem funcional, isso significa que a operação + é uma função total +: \mathbb{N}\times\mathbb{N}\to\mathbb{N}: para cada entrada há exatamente uma saída.
  • Observação prática para a prova/exame: proceda sempre por reduzir a+b aplicando as regras a+0=a,\qquad a+S(b)=S(a+b),até chegar a um natural sem mais + envolvendo sucessores. Por exemplo, para calcular 3+2 com essa definição (escrevendo 3=S(S(S(0))) e 2=S(S(0))): 3+2 = 3+S(1)=S(3+1)=S(S(3+0))=S(S(3))=5.Isso demonstra concretamente que a recursão termina e produz um natural.

Resposta

\forall a\in\mathbb{N}\,\forall b\in\mathbb{N}\,\exists!\,c\in\mathbb{N}:\;a+b=c.

Exercícios relacionados