Questão 2. Prove as propriedades fundamentais da adição de números naturais. Justifique cada passo utilizando indução matemática ou os resultados provados anteriormente.
a) Prove que 0+b=b para todo número natural b.
b) Prove que s(a)+b=s(a+b) para quaisquer números naturais a e b.
c) (Comutatividade) Para quaisquer números naturais n e m, prove que n+m=m+n.
d) (Associatividade) Para quaisquer números naturais a, b e c, prove que (a+b)+c=a+(b+c).
e) (Lei do Cancelamento) Sejam a, b e c números naturais tais que a+b=a+c. Prove que b=c.

Passo 1

O enunciado pede provar cinco propriedades básicas da adição em \mathbb{N}. Vou listar claramente o que cada item pede e quais definições/axiomas vou usar (essas são as informações dadas do sistema dos números naturais que usaremos):
  • Perguntas a provar:
    (a) Provar que \,0+b=b para todo número natural b.
    (b) Provar que \,s(a)+b=s(a+b) para quaisquer naturais a e b.
    (c) (Comutatividade) Provar que \,n+m=m+n para quaisquer naturais n e m.
    (d) (Associatividade) Provar que \,(a+b)+c=a+(b+c) para quaisquer naturais a,b,c.
    (e) (Lei do Cancelamento) Dado a,b,c\in\mathbb{N} tais que \,a+b=a+c, provar que b=c.
  • Definição/axiomas que usarei (padrão Peano / definição recursiva da adição):
    1. Para todo x\in\mathbb{N}: \,x+0=x.
    2. Para todo x,y\in\mathbb{N}: \,x+s(y)=s(x+y).
    3. Princípio da indução: se uma propriedade é verdadeira para 0 e sua veracidade para n implica a veracidade para s(n), então é verdadeira para todo n\in\mathbb{N}.
    4. Injetividade do sucessor: se s(x)=s(y) então x=y.
  • Observações sobre símbolos: 0 é o zero natural, s(x) é o sucessor de x (ou seja, s(x)=x+1 intuitivamente). As fórmulas acima são as regras de definição da adição que permitiremos usar como pontos de partida.
A partir do Passo 2 começamos as provas, usando indução quando for apropriado e justificando cada passo.

Passo 2

Prova de (a): mostrar que \,0+b=b para todo b\in\mathbb{N}.
Estratégia: usar indução em b.
  • Base ( b=0): aplicar a regra (1) com x=0:
    0+0 = 0.
    Isso coincide com a afirmação \,0+b=b quando b=0.
  • Passo indutivo: suponha como hipótese de indução que para um dado b\in\mathbb{N} vale \,0+b=b. Precisamos mostrar \,0+s(b)=s(b).
    Usamos a regra (2) da definição da adição, com x=0 e y=b:
    0+s(b)=s(0+b).
    Pela hipótese de indução 0+b=b, então s(0+b)=s(b). Portanto
    0+s(b)=s(b).
    Assim o passo indutivo é válido.
Pelo princípio da indução, concluímos que \,0+b=b para todo b\in\mathbb{N}. (Comentário rápido: essa propriedade era plausível intuitivamente — somar zero à esquerda não muda o número — e a indução formaliza isso.)

Passo 3

Prova de (b): mostrar que \,s(a)+b=s(a+b) para quaisquer a,b\in\mathbb{N}.
Estratégia: usar indução em b.
  • Base ( b=0): aplicar a regra (1) com x=s(a):
    s(a)+0 = s(a).
    Por outro lado s(a+0)=s(a) porque a+0=a pela regra (1). Então
    s(a)+0 = s(a+0),
    o que verifica a base.
  • Passo indutivo: suponha que para um dado b valha a hipótese de indução
    s(a)+b = s(a+b).
    Queremos provar
    s(a)+s(b) = s(a+s(b)).
    Começamos transformando a esquerda usando a regra (2) (com x=s(a) e y=b):
    s(a)+s(b) = s\big(s(a)+b\big).
    Pela hipótese de indução s(a)+b = s(a+b), então
    s\big(s(a)+b\big) = s\big(s(a+b)\big).
    Agora observamos a direita que queremos:
    s(a+s(b)) = s\big(a+s(b)\big).
    Mas pela regra (2) aplicada a a e b temos a+s(b)=s(a+b). Substituindo,
    s(a+s(b)) = s\big(s(a+b)\big).
    Portanto tanto a esquerda quanto a direita valem s\big(s(a+b)\big), e então
    s(a)+s(b) = s(a+s(b)).
    Assim o passo indutivo está provado.
Pelo princípio da indução em b, obtemos \,s(a)+b=s(a+b) para todos a,b\in\mathbb{N}. (Comentário: essa propriedade expressa que o operador “somar” com o sucessor do primeiro argumento equivale a aplicar o sucessor depois de somar; é compatibilidade natural do sucessor com a adição.)

Passo 4

Prova de (c) Comutatividade: mostrar que \,n+m=m+n para todos n,m\in\mathbb{N}.
Estratégia: usar indução em m (o segundo argumento).
  • Base ( m=0): queremos provar n+0 = 0+n.
    A regra (1) dá n+0=n. Do Passo 2 já provamos 0+n=n. Logo n+0=0+n.
  • Passo indutivo: suponha que para um dado m valha n+m = m+n para todo n fixo. Devemos provar n+s(m) = s(m)+n.
    Calcule a esquerda usando a regra (2):
    n+s(m) = s(n+m).
    Para a direita, aplique a propriedade (b) já provada (Passo 3) com a=m e b=n:
    s(m)+n = s(m+n).
    Pela hipótese de indução temos n+m = m+n. Aplicando o operador s(\,\cdot\,) aos dois lados (isso preserva igualdade), obtemos
    s(n+m) = s(m+n).
    Assim
    n+s(m) = s(n+m) = s(m+n) = s(m)+n.
    Isso mostra o passo indutivo.
Pelo princípio da indução em m, concluímos que \,n+m=m+n para todos n,m\in\mathbb{N}. (Comentário: a comutatividade foi obtida combinando a definição recursiva da adição com as propriedades já provadas.)

Passo 5

Prova de (d) Associatividade: mostrar que \,(a+b)+c = a+(b+c) para todos a,b,c\in\mathbb{N}.
Estratégia: usar indução em c.
  • Base ( c=0): pela regra (1) aplicada a a+b,
    (a+b)+0 = a+b.
    E pela regra (1) aplicada a b,
    a+(b+0) = a+b.
    Portanto (a+b)+0 = a+(b+0).
  • Passo indutivo: suponha que (a+b)+c = a+(b+c) para um dado c. Queremos provar
    (a+b)+s\text{(c)} = a+(b+s\text{(c)}).
    Use a regra (2) na esquerda:
    (a+b)+s\text{(c)} = s\big((a+b)+c\big).
    Use a regra (2) na direita (aplicada a b e c primeiro):
    a+(b+s\text{(c)}) = a+s(b+c).
    Agora aplique a regra (2) em a e b+c (ou observe que a+s(b+c)=s(a+(b+c)) pela definição), então
    a+s(b+c) = s\big(a+(b+c)\big).
    Pela hipótese de indução (a+b)+c = a+(b+c). Aplicando s(\,\cdot\,) aos dois lados obtemos
    s\big((a+b)+c\big) = s\big(a+(b+c)\big).
    Isso mostra que
    (a+b)+s\text{(c)} = s\big((a+b)+c\big) = s\big(a+(b+c)\big) = a+s(b+c) = a+(b+s\text{(c)}).
    Assim o passo indutivo é válido.
Pelo princípio da indução em c, \,(a+b)+c = a+(b+c) para todos a,b,c\in\mathbb{N}. (Comentário: associatividade foi obtida de forma direta pela recursão da adição e indução.)

Passo 6

Prova de (e) Lei do Cancelamento: se a+b=a+c então b=c, para a,b,c\in\mathbb{N}.
Estratégia: usar indução em a. Usaremos também a injetividade do sucessor (axioma Peano 4).
  • Base ( a=0): suponha 0+b = 0+c. Pelo Passo 2 sabemos 0+b=b e 0+c=c. Assim b=c.
  • Passo indutivo: suponha que a propriedade do cancelamento vale para um dado a; isto é, se a+b=a+c então b=c. Queremos provar que se s(a)+b = s(a)+c então b=c.
    Começamos reescrevendo os lados usando a propriedade (b) do Passo 3:
    s(a)+b = s(a+b),\qquad s(a)+c = s(a+c).
    A hipótese s(a)+b = s(a)+c torna-se então
    s(a+b) = s(a+c).
    Pela injetividade do sucessor (axioma) segue que
    a+b = a+c.
    Agora aplicamos a hipótese indutiva (que diz que do igual a+b=a+c se segue b=c) para concluir b=c. Assim o passo indutivo está provado.
Pelo princípio da indução em a, concluímos que se a+b=a+c então b=c para todos a,b,c\in\mathbb{N}. (Comentário: a injetividade do sucessor foi crucial para “remover” um sucessor comum e reduzir ao caso anterior.)

Resposta

(a) 0+b=b para todo b\in\mathbb{N}.\n
(b) s(a)+b=s(a+b) para todos a,b\in\mathbb{N}.\n
(c) n+m=m+n para todos n,m\in\mathbb{N}.\n
(d) (a+b)+c=a+(b+c) para todos a,b,c\in\mathbb{N}.\n
(e) Se a+b=a+c então b=c para todos a,b,c\in\mathbb{N}.

Exercícios relacionados