Seja s: N N função sucessor que satisfaz:
P1) s: N N é injetiva.
P2) N-s(N)=1.
Prove que: Se X subseteq N tal que 1 in X e s(n) in X, forall n in X Rightarrow X=N. Então para todo subconjunto não-vazio A subseteq N, tem-se A-s(A) neq emptyset.
Sugestão: Suponha ao contrário e verifique que: 1 in A^c e s(n) in A^c para assim concluir A^c=N.

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:
  1. 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.
  2. ℕ - 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:
(1+2+3+ldots+n)^2=1^3+2^3+ldots+n^3;
Para todo n in N, seja Hn=1+12+13+ldots+1n
Prove por indução em n que:
n+H1+ldots+Hn-1=n Hn ; forall n >= 2
Use indução para demonstrar os seguintes fatos:
a^n>1+n(a-1) ; forall n >= 2, e a>1.
Sejam u=(2,-1,0) e v=(1,-3,2).
Calcule a área do triângulo determinado pelos vetores 2 u e-v.