Questão 5. (Tricotomia). Sejam a e b números naturais. Prove que exatamente uma das seguintes afirmações é verdadeira: a<b, a=b, ou a>b.

Passo 1

O que o enunciado dá e pede (em linguagem clara):
  • Dados dois números naturais a e b.
  • Pede-se provar que exatamente uma das três afirmações é verdadeira:
    • a<b,
    • a=b,
    • a>b.
“Exatamente uma” significa duas coisas ao mesmo tempo: (i) pelo menos uma das afirmações é verdadeira (cobertura/totalidade) e (ii) não é possível que duas (ou três) delas sejam verdadeiras ao mesmo tempo (mutua exclusão). Vou provar ambos os pontos de forma rigorosa.

Passo 2

Definições e instrumentos que vou usar (explicados devagar):
  • Vamos supor a definição usual dos números naturais que contém 0 e o operador sucessor S. Assim cada natural n é ou 0 ou da forma S(m) para um único m. Para n>0 existe um único predecessor n-1 tal que S(n-1)=n.
  • Definição prática de ordem estrita: direi que x<y quando existe um natural k com k\neq 0 tal que x + k = y.Aqui + é a adição usual em \mathbb{N}. A condição k\neq 0 garante que x e y são distintos, isto é, x<y implica x\neq y.
  • Observação (intuição útil): somar 1 aos dois lados preserva relações do tipo menor/igual; formalmente, se x<y então S(x)<S(y); se x=y então S(x)=S(y). Vou usar isso ao passar da prova para antecessores aos próprios números.

Passo 3

Estratégia de prova escolhida e por que:
Vou provar a afirmação por indução forte sobre a soma s=a+b. Por quê? Porque reduzir a,b para os seus predecessores a-1,b-1 diminui a soma e permite aplicar hipótese de indução de forma simples e limpa, sem depender de subtração definida em todos os casos. Além disso essa técnica trata simultaneamente dos casos em que um dos números é zero. É um método direto e baseado em propriedades fundamentais de \mathbb{N}.

Passo 4

Base da indução: casos com s=a+b pequeno.
  • Se s=0 então a=0 e b=0. Logo a=b. Assim exatamente uma das três (no caso, a=b) é verdadeira.
  • Se s=1 então os pares possíveis são (0,1) ou (1,0). No primeiro temos 0<1 (portanto a<b), no segundo temos 1>0 (portanto a>b). Em cada caso exatamente uma das três afirmações é verdadeira.
    Esses casos iniciais cobrem a base da indução.

Passo 5

Passo indutivo (hipótese de indução forte):
Suponha que para todo par (x,y) de naturais com x+y<s vale que exatamente uma das afirmações x<y,\; x=y,\; x>y é verdadeira. Vou mostrar que então vale a mesma conclusão para qualquer par (a,b) com a+b=s.
Considere (a,b) tais que a+b=s. Há dois subcasos:
  1. Um dos números é 0.
  • Se a=0 e b=0 então a=b e estamos feitos.
  • Se a=0 e b\neq 0 então b tem predecessor b-1 e claramente 0<b (pois existe k=b tal que 0+k=b com k\neq 0), então a<b. Analogamente, se b=0 e a\neq 0 então a>b. Em todos esses subcasos exatamente uma das três afirmações é verdadeira.
  1. Ambos são maiores que 0.
    Então existem a' e b' em \mathbb{N} tais que a=S(a') e b=S(b'). Note que
a'+b' = (a-1)+(b-1) = a+b-2 = s-2 < s,
portanto podemos aplicar a hipótese de indução ao par (a',b'). Pela hipótese de indução, exatamente uma das três afirmações é verdadeira para (a',b'):
  • Se a'<b', existe k\neq 0 com a'+k=b'. Somando 1 em ambos os lados (isto é, aplicando o sucessor) obtemos S(a')+k=S(b'), portanto a + k = b e a<b.
  • Se a'=b', então aplicando sucessor chegamos a a=b.
  • Se a'>b', análogo, aplicando sucessor obtemos a>b.
Assim, em todos os subcasos (quando ambos são positivos) a relação entre a e b é exatamente a mesma que entre a' e b', logo exatamente uma das três afirmações vale. Isso conclui o passo indutivo.

Passo 6

Conclusão da indução e cobertura:
Pelo princípio da indução forte, a propriedade é verdadeira para todo par (a,b) de naturais: para quaisquer a,b\in\mathbb{N} exatamente uma das afirmações a<b,\; a=b,\; a>b é verdadeira. Isso prova a totalidade (pelo menos uma é verdadeira) e, pela argumentação acima que herda a exclusividade dos passos menores, também a mutual exclusão (não podem ser simultaneamente verdadeiras duas diferentes).

Passo 7

Observações adicionais sobre exclusão mútua (para ficar bem claro):
  • Não é possível ter a=b e a<b ao mesmo tempo, porque a=b impõe que não exista k\neq 0 com a+k=b.
  • Não é possível ter a<b e a>b ao mesmo tempo porque isso produziria a+k=b e b+\ell=a com k,\ell\neq 0; somando as igualdades obteríamos a+(k+\ell)=a e, pela propriedade cancelativa da adição em \mathbb{N}, isso forçaria k+\ell=0, contradizendo k,\ell\neq 0. (A propriedade cancelativa pode ser provada por indução simples: se x+y=x então y=0.) Esses argumentos reforçam que as três alternativas são mutuamente exclusivas.

Resposta

Para quaisquer a,b\in\mathbb{N}, exatamente uma das afirmações a<b, a=b ou a>b é verdadeira.

Exercícios relacionados