Sejam
. Demonstre as seguintes propriedades dos números naturais:
a) Associatividade:
e
;
b) Comutatividade do produto:
(Dica:use indução sobre
)
c) Distributividade:
(Dica: use indução sobre
)
d) Lei de corte para o produto: Se
, então
. (Dica:
axioma de Peano - PIF sobre
)
a) Associatividade:
b) Comutatividade do produto:
c) Distributividade:
d) Lei de corte para o produto: Se
Passo 1
O enunciado pede para demonstrar, para quaisquer
, as seguintes propriedades:
- (a) Associatividade:
e - (b) Comutatividade do produto:
(Dica: usar indução sobre .) - (c) Distributividade:
(Dica: usar indução sobre .) - (d) Lei de corte (cancelamento) para o produto: se
então .
(Dica: usar o princípio da indução sobre.)
Informações dadas (implícitas, típicas num desenvolvimento pela aritmética de Peano):
- Os naturais vêm com a operação de sucessor
e com o princípio de indução. - As operações são definidas recursivamente (definições que vamos usar explicitamente abaixo).
Passo 2
Vou relembrar as definições recursivas padrão (Peano) que usarei — é essencial entender como
e
são construídos, porque todas as provas usam essas definições.
Definições (recursivas sobre o segundo argumento):
- Para adição:
Aqui
é o sucessor de
(às vezes escrito
). A definição diz: somar
com o sucessor de
é o sucessor de
.
- Para multiplicação:
A multiplicação é soma iterada: multiplicar
por o sucessor de
é multiplicar por
e depois somar mais
.
Também vamos usar o princípio da indução: para provar uma propriedade
para todo
mostra-se
e que
.
Explicação rápida do porquê dessas definições: com elas,
e
; e a multiplicação cresce adicionando cópias de
. Essas formas permitem provas por indução simples.
Passo 3
Lema útil (que vamos precisar): associatividade da adição. Provarei
por indução em
.
Base
:
e
Logo
.
Passo indutivo: suponha
para certo
. Então, aplicando a regra para sucessor,
e
Pela hipótese indutiva
, logo
Portanto
. Assim a propriedade vale para
. Concluímos por indução que a adição é associativa:
Comentário didático: a ideia é simples — como
foi definido recursivamente pelo segundo argumento, ao passar de
para
aparece um
dos dois lados, e a igualdade segue da hipótese indutiva.
Passo 4
Lema útil: comutatividade da adição (vamos precisar dela para manipular somas nas provas seguintes). Provo
por indução em
.
Base
:
Passo indutivo: suponha
. Então
e
Pela hipótese indutiva
, logo
, portanto
. Isso completa a indução:
para todo
.
Comentário: muitas provas em aritmética usam comutatividade da soma para reorganizar termos; por isso provamos já.
Passo 5
Provar agora a distributividade (parte (c)), que será usada depois para propriedades do produto. Prova por indução em
(conforme a dica).
Queremos mostrar
para todos
.
Base
:
e
Assim a igualdade vale para
.
Passo indutivo: suponha que para algum
valha
para todos
. Precisamos provar a mesma coisa para
. Usamos a definição de multiplicação:
Pela hipótese indutiva substituímos:
Agora reorganizamos a soma usando associatividade e comutatividade da adição (lemmas já provados):
Mas
e
, visto que
Portanto
Assim a distributividade vale para
. Por indução sobre
concluímos que
para todos
.
Comentário prático: a etapa-chave foi usar associatividade e comutatividade da soma para agrupar termos de modo a reconhecer as definições
e
.
Passo 6
Agora com a distributividade disponível, volto para provar a associatividade da multiplicação (segunda parte de (a)):
Vou provar isso por indução em
(definição de
é recursiva em segundo argumento).
Base
:
e
Logo vale para
.
Passo indutivo: suponha que
para certo
. Considere
. Pelo lado esquerdo,
Usando distributividade (Passo 5) com o primeiro fator
:
Pela hipótese indutiva
, portanto
Pelo lado direito,
pela definição de multiplicação aplicada ao fator
. Então os dois lados coincidem, e a igualdade se mantém para
. Concluímos por indução que
para todos
. Assim a multiplicação é associativa.
Comentário: a associatividade do produto seguia depois de já termos distributividade; por isso essa ordem de provas faz sentido.
Passo 7
Provar a comutatividade do produto (parte (b)):
. A dica era usar indução sobre
; eu farei isso, e em cada passo usarei a definição e o que já foi provado (comutatividade e associatividade da soma, distributividade, identidade de
, etc).
Prova por indução em
.
Base
:
Queremos mostrar para todo
.
Queremos mostrar
- Pela definição
(por indução em usando a definição recursiva em segundo argumento, ou notando que soma de zeros dá zero). - Pela definição também
.
Logo.
Passo indutivo: suponha
para todo
(hipótese indutiva forte: fixo
vale para todos
). Mostrarei
para todo
.
Tomemos
arbitrário. Pela definição,
Pela hipótese indutiva
, então
Agora, usando distributividade e comutatividade da soma, observo que
Logo
Isso fecha o passo indutivo. Assim, por indução em
,
para todos
. Ou seja, a multiplicação é comutativa.
Comentário sobre a estratégia: foi fundamental a hipótese indutiva
para trocar os fatores dentro da soma
e reconhecer a definição de
. Por isso a indução sobre
é natural aqui.
Passo 8
Agora tenho associatividade e comutatividade da multiplicação, e distributividade. Vou provar a lei de corte para o produto (parte (d)): se
então
. Antes, preciso discutir um detalhe prático: se
não vale (pois
para quaisquer
). Portanto a forma correta é: para
(ou supondo que
comece em
), verifica-se que
implica
. Vou provar a versão com
. (Isto está de acordo com a dica de usar indução sobre
.)
Preparação: preciso de um lema simples sobre produtos não serem zero quando ambos os fatores são não nulos.
Lema A: Se
e
então
.
Prova do Lema A por indução em
(mostrando para todo
que
):
- Base
: . - Passo indutivo: suponha que para
vale sempre que . Então para , Se então é um natural e é sucessor de algo (ou pelo menos não ); em particular soma de dois termos, um dos quais , não pode ser . Formalmente, pela propriedade de sucessor e injetividade de já se vê que soma com um termo não-nulo não dá . Logo . Isso fecha a indução do lema.
Com o Lema A estabelecido, prossigo para a prova do cancelamento.
Proposição (Lei de corte para produto): para todo
, se
então
.
Prova por indução em
.
Base
:
logo
implica
. OK.
Passo indutivo: suponha a propriedade válida para um
, isto é, suponha: para quaisquer
, se
então
. Vou mostrar que a propriedade vale para
.
Se
então, pelas definições,
Reescrevendo:
essa forma é apenas motivadora; para ficar estritamente em termos de soma, argue-se por contradição usando a ordem natural:
Suponha, sem perda, que
. Então ou
ou
. Suponha
. Então existe
tal que
. Então
Mas como
, segue que
. Isto contradiz o Lema A, porque
e
implicam
. Portanto não pode ocorrer
. Analogamente, não pode ocorrer
. Logo
.
Assim, por indução em
(para
), temos a propriedade de cancelamento: se
e
então
.
Comentário final: a hipótese
é essencial — para
não se tem cancelamento, porque
para todo
.
Passo 9
Resumo final das propriedades demonstradas (já provadas passo a passo acima):
- Associatividade da soma:
para todos . - Associatividade do produto:
para todos . - Comutatividade do produto:
para todos . - Distributividade:
para todos . - Lei de corte para o produto: se
e então .
Resposta
Se