Questão 5. (Tricotomia). Sejam
e
números naturais. Prove que exatamente uma das seguintes afirmações é verdadeira:
, ou
.
Passo 1
O que o enunciado dá e pede (em linguagem clara):
- Dados dois números naturais
e . - Pede-se provar que exatamente uma das três afirmações é verdadeira:
-
, -
, -
.
-
“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
e o operador sucessor . Assim cada natural é ou ou da forma para um único . Para existe um único predecessor tal que . - Definição prática de ordem estrita: direi que
quando existe um natural com tal que Aqui é a adição usual em . A condição garante que e são distintos, isto é, implica . - Observação (intuição útil): somar 1 aos dois lados preserva relações do tipo menor/igual; formalmente, se
então ; se então . 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 . Por quê? Porque reduzir
para os seus predecessores
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
.
Vou provar a afirmação por indução forte sobre a soma
Passo 4
Base da indução: casos com
pequeno.
- Se
então e . Logo . Assim exatamente uma das três (no caso, ) é verdadeira. - Se
então os pares possíveis são ou . No primeiro temos (portanto ), no segundo temos (portanto ). 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 de naturais com
vale que exatamente uma das afirmações
é verdadeira. Vou mostrar que então vale a mesma conclusão para qualquer par
com
.
Suponha que para todo par
Considere
tais que
. Há dois subcasos:
- Um dos números é
.
- Se
e então e estamos feitos. - Se
e então tem predecessor e claramente (pois existe tal que com ), então . Analogamente, se e então . Em todos esses subcasos exatamente uma das três afirmações é verdadeira.
- Ambos são maiores que
.
Então existeme em tais que e . Note que
portanto podemos aplicar a hipótese de indução ao par
. Pela hipótese de indução, exatamente uma das três afirmações é verdadeira para
:
- Se
, existe com . Somando em ambos os lados (isto é, aplicando o sucessor) obtemos , portanto e . - Se
, então aplicando sucessor chegamos a . - Se
, análogo, aplicando sucessor obtemos .
Assim, em todos os subcasos (quando ambos são positivos) a relação entre
e
é exatamente a mesma que entre
e
, 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 de naturais: para quaisquer
exatamente uma das afirmações
é 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).
Pelo princípio da indução forte, a propriedade é verdadeira para todo par
Passo 7
Observações adicionais sobre exclusão mútua (para ficar bem claro):
- Não é possível ter
e ao mesmo tempo, porque impõe que não exista com . - Não é possível ter
e ao mesmo tempo porque isso produziria e com ; somando as igualdades obteríamos e, pela propriedade cancelativa da adição em , isso forçaria , contradizendo . (A propriedade cancelativa pode ser provada por indução simples: se então .) Esses argumentos reforçam que as três alternativas são mutuamente exclusivas.
Resposta
Para quaisquer
, exatamente uma das afirmações
,
ou
é verdadeira.