Questão 4. Sejam a, b e c números naturais. Prove as seguintes propriedades básicas de ordem:
a<b se, e somente se, s(a) \leq b.

Passo 1

O enunciado dá que a,b,c são números naturais e pede para provar a equivalência
a<b \quad\text{se, e somente se,}\quad s(a)\le b,
onde s(x) denota o sucessor de x (ou seja, s(x)=x+1 na notação habitual).
Informações e definições que vamos usar (tudo retirado da teoria de números naturais):
  • A definição de ordem não estrita ( \le): x\le y significa que existe n\in\mathbb{N} tal que
x + n = y.
  • A definição de ordem estrita ( <): x<y significa que existe n\in\mathbb{N} com n\neq 0 e
x + n = y.
(Equivalente a x\le y e x\neq y.)
  • Definição recursiva da adição:
x + 0 = x, \qquad x + s(y) = s(x + y).
  • Propriedade básica usada: todo natural diferente de 0 é sucessor de algum natural; ou seja, se n\neq 0 então existe d tal que n = s(d).
A partir dessas definições vamos provar as duas implicações da equivalência. Não resolvo nada neste passo; apenas assinalei o que foi dado e as ferramentas que vamos usar.

Passo 2

Lema técnico que usaremos (e que provarei rapidamente): para quaisquer naturais a e n vale
s(a) + n = s(a + n).
Prova do lema por indução em n:
  • Caso base n=0: pela definição de adição,
s(a) + 0 = s(a), \qquad s(a + 0) = s(a),
logo s(a)+0 = s(a+0).
  • Passo indutivo: suponha s(a) + n = s(a + n) para um n. Então, usando a definição de adição,
s(a) + s(n) = s\big(s(a) + n\big).
Pela hipótese indutiva s(a)+n = s(a+n), então
s\big(s(a) + n\big) = s\big(s(a+n)\big).
Mas, novamente pela regra de adição na segunda coordenada,
s\big(s(a+n)\big) = s\big(a + s(n)\big).
Assim s(a) + s(n) = s(a + s(n)), completando o passo indutivo.
Portanto o lema s(a) + n = s(a + n) é válido para todo n\in\mathbb{N}. Esse lema é uma aplicação direta da recursão da adição; é uma identidade que facilita reescrever soma com um sucessor.

Passo 3

Prova da implicação \Rightarrow: suponha a < b. Pela definição de < existe c\in\mathbb{N} com c\neq 0 e
a + c = b.
Como c\neq 0, pela propriedade citada existe d\in\mathbb{N} tal que c = s(d). Substituindo em a + c = b obtemos
a + s(d) = b.
Pela definição da adição isso é equivalente a
s(a + d) = b.
Agora aplicamos o lema do Passo 2 com o mesmo d:
s(a) + d = s(a + d).
Comparando com s(a + d)=b, temos
s(a) + d = b.
Isto mostra que existe d\in\mathbb{N} tal que s(a) + d = b, ou seja, por definição de \le,
s(a)\le b.
Portanto a<b implica s(a)\le b.

Passo 4

Prova da implicação \Leftarrow: suponha s(a)\le b. Pela definição de \le existe e\in\mathbb{N} tal que
s(a) + e = b.
Pelo lema do Passo 2 temos s(a)+e = s(a + e). Assim
b = s(a + e).
Usando a identidade s(a+e)=a + s(e) (que é apenas a mesma regra de adição escrita de outra forma), obtemos
b = a + s(e).
Note que s(e)\neq 0. Logo existe um natural não nulo (especificamente s(e)) tal que a + s(e) = b. Pela definição de < isso significa exatamente a < b.
Portanto s(a)\le b implica a<b.

Passo 5

Conclusão: juntando os Passos 3 e 4 provamos as duas direções. A equivalência está demonstrada: a<b se, e somente se, s(a)\le b.
Um exemplo rápido para fixar a intuição: com a=2 e b=4, temos a<b porque 2+2=4 com 2\neq 0. A sucessão dá s(a)=3 e s(a)\le b porque 3+1=4. Os dois lados batem.

Resposta

a<b se, e somente se, s(a)\le b

Exercícios relacionados