Questão 9. Prove as seguintes propriedades fundamentais da multiplicação para quaisquer naturais
e
:
Mostre que se
e
são ambos positivos, então
também é positivo.
Mostre que se
Passo 1
O que o enunciado dá e o que pede.
- Temos dois números naturais
e tais que e . - Precisamos provar que o produto
também é positivo.
Definição que usarei (padrão em aritmética de naturais): um natural
é dito positivo quando existe algum natural
tal que
. Ou seja,
é um sucessor de outro natural. Vou escrever isso usando a forma:
tal que
, e similar para
.
Passo 2
Plano de prova e ferramenta básica.
- Vou usar a definição recursiva usual da multiplicação por naturais:
- Prova por indução em
: fixo e mostro que para todo vale . Para fazer isso preciso também de um lema simples sobre soma: a soma de dois naturais positivos é positiva. Vou provar esse lema primeiro (é curto) e depois faço a indução.
Passo 3
Lema (soma de positivos é positiva) e sua prova.
Afirmação: se e
então
.
Prova do lema: como existe
com
. Como
existe
com
. Então
Afirmação: se
Prova do lema: como
Escrevendo
, obtemos que
é da forma
com
. Portanto
. Isso prova o lema. (Intuição: somando dois sucessores obtém-se outro sucessor.)
Passo 4
Base da indução em
.
Queremos provar que, para fixo , a propriedade
: “
” vale para todo
. Começamos com
(lembrando que
significa
). Usando a definição recursiva:
Queremos provar que, para fixo
Como por hipótese
, segue que
. Assim
é verdadeira.
Passo 5
Passo indutivo.
Suponha que para algum vale
, isto é, suponha que
. Consideremos
. Pela definição da multiplicação,
Suponha que para algum
Pelo passo indutivo
e pela hipótese inicial
. Pelo lema do Passo 3 (soma de positivos é positiva), a soma
é positiva. Portanto
. Isso completa o passo indutivo.
Passo 6
Conclusão por indução e observação final.
Pelo princípio da indução matemática sobre temos que, para todo
(ou seja, para todo
),
. A escolha de qual dos dois fatores induzir foi arbitrária: fixando
e induzindo em
dá-se o mesmo argumento simétrico. Portanto, para quaisquer naturais
e
, se
e
então
. (Intuitivamente: produto de sucessores é soma de sucessores, logo sucessor.)
Pelo princípio da indução matemática sobre