Le coin des amatheurs version 2
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 ?
La première partie du raisonnement est correcte ainsi que sa conclusion : il est effectivement vrai que si A dépasse 1 alors A n'est pas le plus grand entier. Le problème est dans la contraposition. Dans le texte ci-dessus, j'ai fait un raccourci. La vrai contraposée de ce qui précède est « si A est le plus grand entier, alors A = 1 ». Mais il y a un SI au début de cette phrase ! Lisez bien : cette phrase ne signifie pas, contrairement à ce qui est dit dans la fausse démonstration, que 1 est le plus grand entier. Cette phrase signifie que, s'il y avait effectivement un plus grand entier (ce qu'on devrait démontrer avant de conclure), alors cet entier serait forcément 1. Mais encore faut-il montrer au préalable qu'il y a bien un plus grand entier, ce qui évidemment risque d'être difficile !