Raisonnement par récurrence
Faire tomber le premier domino ne suffit pas ; encore faut-il que chacun renverse le suivant. La récurrence exige ces deux garanties, et l'infini s'écroule tout seul.
Faire tomber le premier domino ne suffit pas ; encore faut-il que chacun renverse le suivant. La récurrence exige ces deux garanties, et l'infini s'écroule tout seul.
Le raisonnement paraît solide : dans un groupe de n chevaux, retirez-en un, puis retirez l'autre, et les deux sous-groupes se recouvrent, donc toutes les robes coïncident. L'hérédité semble impeccable. Elle échoue pourtant au tout premier pas : avec deux chevaux, les sous-groupes obtenus ne se recouvrent plus du tout.
Partout où l'on dispose d'un ordre sans suite infinie descendante. L'induction bien fondée s'applique aux arbres, aux mots, aux ordinaux transfinis. Gerhard Gentzen a même démontré en 1936 la cohérence de l'arithmétique de Peano, au prix d'une récurrence poussée jusqu'à l'ordinal epsilon zéro.