Nous allons d'abord montrer que tous les entiers sont égaux en utilisant une démonstration par récurrence (cliquez ici si vous ne savez pas ce que c'est). On utilise l'hypothèse Hn : « si max (a,b) est inférieur ou égal à n, alors a = b ».
Vérifions H0 : si max (a,b) est inférieur ou égal à 0, c'est-à-dire si le plus grand entier entre a et b vaut 0, alors ils sont forcément tous deux égaux à 0 (ne pouvant pas être plus petits) et donc ils sont aussi égaux entre eux.
A présent supposons Hn pour un certain n. Considérons deux nombres a et b tels que max (a,b) est inférieur à égal à n+1. Alors max (a-1,b-1) est inférieur ou égal à n et donc d'après Hn on a a-1 = b-1 et donc a = b. Ainsi, en supposant Hn, on a montré que « si max (a,b) est inférieur ou égal à n+1, alors a = b ». Autrement dit, en supposant Hn on a montré Hn+1 : la propriété H est héréditaire.
Par récurrence, on a donc que Hn est vraie pour tout n. A présent, prenons deux entiers A et B et notons C le maximum de A et B. on a max (A,B) inférieur ou égal à C donc d'après HC, on obtient A = B. Ainsi, deux entiers sont toujours égaux !
Bon d'accord, il doit y avoir une erreur. Mais où ?

Le problème est assez subtil, et il se situe dans la récurrence. La vérification de H0 est correcte, du moins si on n'utilise que des entiers positifs, ce qui était implicitement convenu. Le vrai problème est dans l'hérédité : en partant de max (a,b) <= n+1, je passe à max (a-1,b-1) <= n. C'est correct. Sauf qu'ensuite j'applique Hn avec a-1 et b-1. Et le problème est là : dans l'énoncé de Hn, les entiers a et b étaient encore implicitement positifs. Alors que là, a-1 et b-1 peuvent être négatifs (égaux à -1). Le problème ici est donc que je n'avais pas le droit d'appliquer Hn car toutes ses hypothèses n'étaient pas vérifiées !

A présent, nous allons majorer les entiers non nuls en utilisant une contraposition (cliquez ici si vous ne savez pas ce que c'est). Prenons un entier A > 1. Alors en multipliant par A, A2 > A. J'ai donc trouvé un entier (A2) plus grand que A : cela signifie que A n'est pas le plus grand entier.
J'ai donc montré que si A > 1, alors A n'est pas le plus grand entier. En contraposant, je peux en déduire que le plus grand entier est 1. Ainsi, 1 est plus grand que tous les nombres entiers !
Alors, où est l'erreur ?

Réponse