Seja
função sucessor que satisfaz:
P1)
é injetiva.
P2)
.
Prove que: Se
tal que
e
. Então para todo subconjunto não-vazio
, tem-se
.
Sugestão: Suponha ao contrário e verifique que:
e
para assim concluir
.
P1)
P2)
Prove que: Se
Sugestão: Suponha ao contrário e verifique que:
Passo 1
Beleza, vamos lá! O problema que temos aqui envolve funções e conjuntos dos números naturais, ou seja, ℕ. A gente precisa entender uma função chamada sucessor, que basicamente pega um número natural e retorna o próximo número. As propriedades que essa função tem são:
- Injetiva: Isso quer dizer que se dois números têm o mesmo sucessor, então eles são iguais. Não tem “repetição” nos sucessores.
- ℕ - s(ℕ) = {1}: Isso significa que, se você tirar todos os sucessores possíveis dessa função da lista dos números naturais, sobra só o número 1.
Nosso objetivo é provar que se temos um conjunto X que:
- Contém o número 1,
- E se para todo número n que está em X, o sucessor s(n) também está em X,
então X tem que ser igual a todo o conjunto dos números naturais, ou seja, X = ℕ.
Depois disso, vamos mostrar que para qualquer subconjunto não-vazio A de ℕ, sempre existe pelo menos um número que está em A mas não no sucessor de A.
Passo 2
Primeiro, vamos entender o que significa que X contém 1 e é fechado pela função sucessor. Quer dizer que, além de ter o 1, se a gente tiver um número qualquer em X, o próximo número também está em X. Por exemplo, se 1 está em X, então s(1) = 2 está em X; se 2 está em X, então s(2) = 3 está em X, e assim por diante.
Passo 3
Vamos usar o princípio da indução para provar que X inclui todos os números naturais. Sabemos que 1 está em X. Supondo que um número k está em X, então, por definição, s(k) = k + 1 também está em X. Assim, seguindo esse passo a passo, todos os números naturais entram em X.
Passo 4
Agora, precisamos provar que X é igual a ℕ. Já mostramos que X contém todos os números naturais, então X é, de fato, ℕ. Não pode ter mais nada, porque X já está incluindo cada número de ℕ.
Passo 5
Com essa conclusão, vamos para a segunda parte do problema. Queremos mostrar que para qualquer conjunto não-vazio A ⊆ ℕ, o conjunto A - s(A) não é vazio. Ou seja, sempre tem pelo menos um número que está em A mas não no sucessor de A.
Passo 6
Vamos supor, para chegar a uma contradição, que A - s(A) seja vazio. Isso significa que todo número em A também está no sucessor de A. Nesse caso, o complemento de A, Aᶜ, teria que conter todos os números que não estão em s(A).
Passo 7
De acordo com a sugestão, se A - s(A) é vazio, então 1 não está em A (porque A - s(A) vazio implica que 1 está em Aᶜ). Além disso, se todo número em A está no sucessor de A, então todos os sucessores estão em A, o que implica que Aᶜ contém 1 e também todos os sucessores desses números, seguindo a propriedade que X = ℕ se contém 1 e está fechado pelo sucessor.
Passo 8
Isso levaria a concluir que Aᶜ = ℕ, ou seja, A estaria vazio. Mas isso é uma contradição, porque assumimos que A é um subconjunto não-vazio de ℕ. Portanto, nossa suposição inicial de que A - s(A) é vazio está errada.
Resposta
Logo, para todo subconjunto não-vazio A ⊆ ℕ, sempre existe pelo menos um número que está em A mas não no sucessor de A, ou seja, A - s(A) ≠ ∅.
Exercícios relacionados
Use indução para demonstrar os seguintes fatos:
;
Para todo
, seja
Prove por indução em que:
Prove por indução em
Use indução para demonstrar os seguintes fatos:
, e
.
Sejam
e
.
Calcule a área do triângulo determinado pelos vetores .
Calcule a área do triângulo determinado pelos vetores