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
para todo número natural
.
b) Prove que
para quaisquer números naturais
e
.
c) (Comutatividade) Para quaisquer números naturais
e
, prove que
.
d) (Associatividade) Para quaisquer números naturais
e
, prove que
.
e) (Lei do Cancelamento) Sejam
e
números naturais tais que
. Prove que
.
a) Prove que
b) Prove que
c) (Comutatividade) Para quaisquer números naturais
d) (Associatividade) Para quaisquer números naturais
e) (Lei do Cancelamento) Sejam
Passo 1
O enunciado pede provar cinco propriedades básicas da adição em
. 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 quepara todo número natural .
(b) Provar quepara quaisquer naturais e .
(c) (Comutatividade) Provar quepara quaisquer naturais e .
(d) (Associatividade) Provar quepara quaisquer naturais .
(e) (Lei do Cancelamento) Dadotais que , provar que . -
Definição/axiomas que usarei (padrão Peano / definição recursiva da adição):
- Para todo
: . - Para todo
: . - Princípio da indução: se uma propriedade é verdadeira para
e sua veracidade para implica a veracidade para , então é verdadeira para todo . - Injetividade do sucessor: se
então .
- Para todo
-
Observações sobre símbolos:
é o zero natural, é o sucessor de (ou seja, 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
para todo
.
Estratégia: usar indução em
.
-
Base (
): aplicar a regra (1) com : Isso coincide com a afirmaçãoquando . -
Passo indutivo: suponha como hipótese de indução que para um dado
vale . Precisamos mostrar .
Usamos a regra (2) da definição da adição, come : Pela hipótese de indução, então . Portanto Assim o passo indutivo é válido.
Pelo princípio da indução, concluímos que
para todo
. (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
para quaisquer
.
Estratégia: usar indução em
.
-
Base (
): aplicar a regra (1) com : Por outro ladoporque pela regra (1). Então o que verifica a base. -
Passo indutivo: suponha que para um dado
valha a hipótese de indução Queremos provarComeçamos transformando a esquerda usando a regra (2) (come ): Pela hipótese de indução, então Agora observamos a direita que queremos:Mas pela regra (2) aplicada ae temos . Substituindo, Portanto tanto a esquerda quanto a direita valem, e então Assim o passo indutivo está provado.
Pelo princípio da indução em
, obtemos
para todos
. (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
para todos
.
Estratégia: usar indução em
(o segundo argumento).
-
Base (
): queremos provar .
A regra (1) dá. Do Passo 2 já provamos . Logo . -
Passo indutivo: suponha que para um dado
valha para todo fixo. Devemos provar .
Calcule a esquerda usando a regra (2):Para a direita, aplique a propriedade (b) já provada (Passo 3) come : Pela hipótese de indução temos. Aplicando o operador aos dois lados (isso preserva igualdade), obtemos AssimIsso mostra o passo indutivo.
Pelo princípio da indução em
, concluímos que
para todos
. (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
para todos
.
Estratégia: usar indução em
.
-
Base (
): pela regra (1) aplicada a , E pela regra (1) aplicada a, Portanto. -
Passo indutivo: suponha que
para um dado . Queremos provar Use a regra (2) na esquerda:Use a regra (2) na direita (aplicada ae primeiro): Agora aplique a regra (2) eme (ou observe que pela definição), então Pela hipótese de indução. Aplicando aos dois lados obtemos Isso mostra queAssim o passo indutivo é válido.
Pelo princípio da indução em
,
para todos
. (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
então
, para
.
Estratégia: usar indução em
. Usaremos também a injetividade do sucessor (axioma Peano 4).
-
Base (
): suponha . Pelo Passo 2 sabemos e . Assim . -
Passo indutivo: suponha que a propriedade do cancelamento vale para um dado
; isto é, se então . Queremos provar que se então .
Começamos reescrevendo os lados usando a propriedade (b) do Passo 3:A hipótesetorna-se então Pela injetividade do sucessor (axioma) segue queAgora aplicamos a hipótese indutiva (que diz que do igualse segue ) para concluir . Assim o passo indutivo está provado.
Pelo princípio da indução em
, concluímos que se
então
para todos
. (Comentário: a injetividade do sucessor foi crucial para “remover” um sucessor comum e reduzir ao caso anterior.)
Resposta
(a)
para todo
.\n
(b) para todos
.\n
(c) para todos
.\n
(d) para todos
.\n
(e) Se então
para todos
.
(b)
(c)
(d)
(e) Se