Use o PBO para mostrar que:
Toda função monótona não-crescente f: N N é constante a partir de certo ponto.

Passo 1

O enunciado pede para mostrar que se temos uma função monótona não-crescente f: N to N, então existe um índice N0 e um valor c tais que f(n)=c para todo n>= N0. Vamos usar o Princípio da Boa Ordenação (PBO), que diz que todo subconjunto não-vazio de N tem um menor elemento.

Passo 2

Definimos o conjunto imagem de f:
S = ,f(n) mid n in N,
Como f tem domínio em N, o conjunto S é não-vazio. Pelo PBO, existe um menor elemento em S; chamemos esse mínimo de c = min S. Por definição de imagem, existe então um índice N0 tal que f(N0)=c.

Passo 3

Agora, para qualquer n>= N0, pela não-crescência de f temos
f(n) <= f(N0) = c
Mas, como c é o menor valor assumido por f, não existe n com f(n). Logo
c <= f(n) <= c
e daí segue que f(n)=c. Portanto, a partir de N0, a função permanece constante no valor c.

Resposta

Existe N0inN e cinN tais que, para todo n>= N0, f(n)=c.

Exercícios relacionados