(a) Enuncie o Princípio da Boa Ordenação.
(b) Usando indução, prove que
é divisível por 3 para todo inteiro
.
(b) Usando indução, prove que
Passo 1
O enunciado pede duas coisas:
- (a) enunciar o Princípio da Boa Ordenação, que é um resultado sobre subconjuntos de inteiros positivos.
- (b) usar indução para provar que
é divisível por 3 para todo inteiro .
Passo 2
O Princípio da Boa Ordenação diz que:
Todo subconjunto não vazio de tem um menor elemento.
Todo subconjunto não vazio de
Passo 3
Base da indução (
).
Para temos
Para
e
é múltiplo de
. Logo, a propriedade vale para
.
Passo 4
Passo indutivo.
Suponha que para algum valha a propriedade, isto é,
Suponha que para algum
para certo inteiro
. Então, para
temos
Pela hipótese indutiva,
, e
é claramente múltiplo de
. Assim
ou seja, é múltiplo de
. Concluímos que a propriedade vale para
.
Pelo princípio da indução,
é divisível por
para todo inteiro
.
Resposta
(a) Todo subconjunto não vazio de
tem um menor elemento.
(b) Por indução em , mostramos que
é múltiplo de
para todo inteiro
.
(b) Por indução em