DÉMONSTRATION THÉORIE DE LA

La théorie de la démonstration est la logique de la logique. En contraste avec d'autres sous-domaines tels que la théorie des modèles, les grandes questions qui ont tant passionné nos pères ont laissé une trace vivace dans cette discipline, qui s'occupe essentiellement (c'est là la définition technique de la théorie de la démonstration) de l'aspect syntaxique de la logique. Au début, grâce au programme de Hilbert, la théorie de la démonstration avait des visées claires et nettes ; mais, après l'échec du programme (1931), tout devint beaucoup moins simple. En particulier, plus question de répondre de manière simpliste aux grandes interrogations ontologiques sur la nature des mathématiques... Faute de pierre philosophale, la discipline aurait pu disparaître ; s'il n'en a rien été, c'est sans doute que l'étude générale des relations des objets finis aux objets infinis :

– dans la dénotation d'objets (infinis) par des constructions syntaxiques (finies),

– dans les preuves de propriétés d'objets (infinis) au moyen de démonstrations (finies), constitue, par-delà les querelles d'école et les tentatives éphémères du genre de celle que fit Hilbert, le véritable objet de la théorie.

Les avancées en théorie de la démonstration semblent liées à un progrès quant aux méthodes utilisées, plus précisément quant à leur complexité logique :

– Hilbert tenta d'élaborer une théorie élémentaire de la démonstration (« élémentaire » signifiant : de complexité logique nulle, cf. chap. 1) ;

– Gentzen a introduit les méthodes essentielles pour l'analyse des systèmes logiques finis (complexité logique Σ⁰₁ , cf. chap. 2) ;

– plus tard, on a considéré des logiques généralisées (infinies) ; la plus connue d'entre elles est la logique avec ω-règle (complexité logique Π¹₁ , cf. chap. 3) ; mais de nouvelles logiques de plus grande complexité (Π¹₂ , voire Π¹_n : cf. chap. 4) sont maintenant utilisées de manière intensive.

Cette question de complexité logique fait l'objet de nombreux contresens ; aussi importe-t-il de dire bien clairement en quoi elle intervient :

– individuellement, les objets considérés sont effectivement calculables, ils sont en pratique récursifs ; il en est de même des opérations définies sur ces objets ; par exemple les ω-démonstrations sont toujours récursives et peuvent être normalisées (par élimination des coupures) effectivement. On voit donc que, pour les objets, la complexité logique ne joue pas ;

– par contre, l'ensemble de tous les objets du genre considéré est logiquement complexe (l'ensemble des ω-démonstrations récursives est Π¹₁ ; cette complexité logique intervient de manière décisive dans la démonstration du théorème d'élimination des coupures, à savoir que la fonction effective qui élimine les coupures remplit bien son rôle) ;

– dans la pratique, la complexité logique joue surtout un double rôle ; elle a un rôle « hygiénique » : assurer que tout se passe bien, que les opérations définies ont les propriétés attendues ; elle joue aussi un rôle de révélateur : voir des problèmes simples de manière inhabituelle ; le détour par des problèmes de très grande complexité logique peut permettre d'y voir clair dans des situations élémentaires embrouillées.

Une dernière mise en garde : ne pas croire que la complexité logique d'un problème soit un gage de profondeur...

Le programme de Hilbert

David Hilbert a proposé un programme de démonstration d'une opinion philosophique : le formalisme. La prétention de Hilbert à démontrer son point de vue a pour contrepartie évidente la possibilité de le réfuter ; la philosophie s'accommode rarement de conclusions aussi tranchées ! Même réfuté, le formalisme garde ses adeptes, notamment en France, avec Bourbaki : on sait bien que les idéologies simplistes ont un pouvoir d'attraction qui persiste même après leur échec patent ; la réfutation de Hilbert par Gödel ne nous propose en aucune manière une vision de même nature : Gödel a détruit l'espoir de donner une réponse claire et nette à certaines interrogations essentielles, mais il n'a pas donné les bases d'un nouveau credo. Les mathématiques doivent être analysées comme une activité sans signification, semblable à un jeu, tel le jeu d'échecs : il s'agit de règles formelles fixées à l'avance et permettant de construire certains assemblages de symboles, à savoir les énoncés mathématiques et leurs démonstrations.

Voilà le credo formaliste ; évidemment cette attitude s'accommode de positions ontologiques variées, depuis le solipsisme jusqu'aux différentes variantes de positivisme. L'élément essentiel de la pensée de Hilbert (et celle de son époque, le début du xx^e siècle), c'est peut-être le mécanisme : à l'opposé des intuitionnistes, qui, avec Brouwer, allaient proclamer le rôle essentiel du mathématicien en tant que sujet pensant, Hilbert réduit celui-ci à la dimension d'un robot : le sens des mathématiques, l'« intuition », ce n'est que ce qui permet de compenser en partie notre infériorité par rapport aux vraies machines.

L'ontologie hilbertienne est non vide : pour Hilbert, il y a certains objets, certaines propriétés, certaines démonstrations qui ont vraiment un sens, qui existent ; il les appelle élémentaires : ce sont les entiers naturels (plus généralement, les constructions finies) pour ce qui est des objets ; les propriétés élémentaires au sens de Hilbert, ce sont les énoncés de la forme : ∀x₁ ... ∀x_n, f (x₁, ..., x_n) = 0, où f est une fonction calculable, c'est-à-dire récursive. Les énoncés de cette forme sont dits Π⁰₁ , leurs négations Σ⁰₁ ; de très nombreux énoncés mathématiques ont cette forme ou s'y ramènent, citons pêle-mêle : le théorème de Fermat, la conjecture de Riemann, la conjecture de Goldbach, le théorème des quatre carrés, le problème des quatre couleurs... Quant aux démonstrations élémentaires, il s'agit évidemment de démonstrations n'utilisant que des énoncés élémentaires et des principes particulièrement immédiats de démonstration, comme l'induction (la récurrence) sur des énoncés élémentaires. Tout ce qui ne fait pas partie de l'élémentarité, Hilbert l'appelle abstrait (qu'il s'agisse d'objets, de propriétés ou de prédicats) : pour lui, ces objets idéaux ne sont que des abstractions commodes permettant à la mauvaise machine qu'est le mathématicien de fonctionner plus efficacement ; mais ces objets n'ont pas de sens en eux-mêmes. Le programme de Hilbert est une tentative pour démontrer la justesse de l'ontologie hilbertienne : Étant donné une démonstration D d'un énoncé élémentaire R par des méthodes abstraites (par exemple, à l'aide de l'axiome du choix en théorie des ensembles) montrer que R peut être obtenu directement dans les mathématiques élémentaires. De plus, si l'on veut que le résultat ait une quelconque valeur épistémologique, le programme doit être montré par des méthodes élémentaires.

Le programme de Hilbert s'appuyait sur une certaine pratique mathématique : par exemple, le théorème des nombres premiers (Hadamard, La Vallée-Poussin) fut d'abord démontré par la théorie des fonctions analytiques ; mais, plus tard, des démonstrations élémentaires furent données. Un principe « esthétique » de mathématiques est le principe de pureté des méthodes, qui consiste à ne pas utiliser de notions étrangères à l'énoncé démontré, et on voit bien que le programme de Hilbert est un principe général de pureté des méthodes. L'exemple de la théorie des corps réels clos (cf. théorie des modèles) donne un exemple d'une situation analogue, où la pureté des méthodes est vraie.

Une variante du programme de Hilbert est la recherche de démonstrations de cohérence élémentaire. Il est d'ailleurs facile de voir que cette variante du programme de Hilbert est strictement équivalente à l'original.

Le premier théorème d' incomplétude de Gödel (1931) est un coup d'arrêt brutal et définitif au programme : l'énoncé de Gödel est élémentaire, vrai (on le sait par des méthodes non élémentaires), mais non prouvable dans la théorie elle-même : il suffit d'appliquer ce résultat à la formalisation des mathématiques élémentaires pour réfuter le programme de Hilbert. Quant au second théorème d'incomplétude, il réfute le programme sous sa forme de « démonstration de cohérence ».

À l'époque où certains allaient bientôt mettre « mathématiques » au singulier (sous-entendu : la leur), ces résultats pourtant exceptionnellement clairs et définitifs n'allaient influencer de manière significative ni la pratique, ni la « philosophie » des mathématiciens. Paradoxalement, le succès des théorèmes d'incomplétude en dehors des milieux mathématiques n'a d'égal que l'incompréhension à peu près générale du résultat.

Rappelons que le théorème ne dit pas qu'une théorie ne peut pas se penser elle-même (non seulement les théories peuvent se penser elles-mêmes, c'est-à-dire exprimer les propriétés qui parlent d'elles-mêmes ; mais, pour ce qui est de la plupart de ces propriétés, elles peuvent même les démontrer ; il y a, par contre, des propriétés non démontrables dans T, et qui n'ont pas le moindre rapport avec T... De plus, le théorème ne dit rien sur la science en général, et encore moins sur la pensée !

Il est certain que les théorèmes d'incomplétude ont un sens général qui transcende la formulation technique précise de ces énoncés, mais ce n'est pas n'importe quoi ! On pourrait dire que les théorèmes parlent de la pensée mécanique et de ses limites. Pourquoi ne pas formuler le résultat de la manière suivante : Il y a des choses qui ne sont pas du ressort du mécanique.