Théorème de Gödel, transfini et intelligence créative

Logique

Science relative aux processus de la pensée rationnelle (induction, déduction, hypothèse p. ex.) et à la formulation discursive des vérités.
En logique on manipule d'une part des propositions qui constituent des énoncés complets pouvant être vrais ou faux, et d'autre part des prédicats qui doivent être complétés par un sujet pour constituer une proposition, qui pourra être vraie ou fausse selon le sujet auquel on applique le prédicat. On note P(x) la proposition obtenue en appliquant le prédicat P au sujet x.

Systèmes formels

Les systèmes formels permettent de prouver la vérité de faits mathématiques. Ils sont constitués d'un ensemble de faits considérés comme évidents et appelés axiomes, et d'un ensemble de règles de déduction qui permettent, à partir d'un certain nombre de faits établis appelés théorèmes, d'en déduire d'autres.
Exemples d'axiomes : Exemple de règle (modus ponens) :
De P => Q et P on peut déduire Q
On pouvait espérer que cette méthode permettrait de prouver toute vérité mathématique en la construisant à partir d'axiomes et de règles adéquates, pourvu que le système formel choisi soit constitué d'un ensemble d'axiomes et de règles suffisemment complet pour formaliser complètement la notion de vérité mathématique dans un certain domaine.

Premier théorème d'incomplétude de Gödel

Le mathématicien Kurt Gödel a démontré qu'en fait c'est impossible. En effet, pour tout domaine des mathématiques qui englobe l'arithmétique (la théorie des nombres entiers naturels), quels que soient les axiomes et les règles choisis pour constituer un certain système formel, si ce système est consistant (ne permet pas de prouver une chose et son contraire) on pourra construire une proposition dite indécidable, dont on ne pourra prouver ni la vérité ni la fausseté dans ce système formel. C'est le premier théorème d'incomplétude de Gödel.

Démonstration du premier théorème d'incomplétude de Gödel

La démonstration fait appel à une représentation du système formel par des objets qu'il peut manipuler (les nombres entiers). Les propositions et les démonstrations sont "codées" par des nombres entiers. Le système formel acquiert ainsi une sorte de capacité d'introspection. Des propositions portant sur des nombres peuvent être interprétées en terme de faits portant sur le système formel, tels que la proposition "telle proposition est démontrable dans le système formel" que l'on pourra exprimer sous une forme du type "il existe un nombre n tel que n est le code d'une démonstration de la proposition dont le code est le nombre p".
Le principe de la démonstration consiste à construire une proposition qui exprime sa propre indémontrabilité.
On part d'un prédicat F défini par : F(p) = "Il n'existe pas de nombre n qui soit le code d'une démonstration du prédicat de code p appliqué au nombre p".
Ensuite on détermine le nombre f, le code du prédicat F, et on considère la proposition de Gödel de ce système formel : G = F(f).
La proposition G est donc de la forme : "Il n'existe pas de nombre n qui soit le code d'une démonstration de F(f)"
ou G = "Il n'existe pas de nombre n qui soit le code d'une démonstration de G".
Autrement dit, G dit "Je ne suis pas démontrable" ! Si G était fausse, alors G serait démontrable, donc vraie (sinon un système qui permettrait de démontrer des choses fausses serait sans intérêt), donc G ne peut pas être fausse, donc G est vraie. On a donc trouvé une proposition vraie qui ne peut pas être démontrée par le système formel. Donc tout système formel consistant qui englobe l'arithmétique est nécessairement incomplet.

Signification du premier théorème d'incomplétude de Gödel

On ne peut pas enfermer la notion de vérité mathématique dans un système fini permettant de déterminer mécaniquement si une proposition est vraie. Il y a donc une part de créativité dans le travail du mathématicien.

Deuxième théorème d'incomplétude de Gödel

De ce premier théorème, Gödel a déduit un deuxième théorème d'incomplétude selon lequel la consistance d'un système formel qui vérifie les mêmes conditions n'est pas démontrable dans le cadre de ce système formel.

Peut-on dépasser la limitation du premier théorème d'incomplétude ?

On a donc un système formel qui est limité car on a trouvé une proposition G qui est vraie mais n'est pas démontrable dans ce système formel. On pourrait penser que pour résoudre ce problème il suffit d'ajouter G comme axiome à ce système. Mais ça ne résout pas le problème, car on obtient alors un nouveau système formel auquel on peut appliquer la même méthode pour obtenir une nouvelle proposition de Gödel qui exprimera sa propre indémontrabilité dans ce nouveau système. On pourrait même construire une suite infinie de systèmes S0, S1, S2, ... qui auront chacun leur proposition de Gödel G0, G1, G2... mais le théorème de Gödel s'applique même au système constitué par cette suite infinie de systèmes, ainsi qu'à tous les systèmes qu'on pourrait obtenir par cette méthode, en ajoutant la proposition de Gödel à un système incomplet et en regroupant une suite infinie de systèmes dans un seul système. C'est là qu'apparait la notion de transfini.

Les ordinaux transfinis

Les ordinaux transfinis constituent une extension de la notion de nombre entier. Les nombres entiers peuvent être définis pas : On peut définir les ordinaux transfinis de façon similaire en ajoutant une règle définissant la notion d'ordinal limite d'une suite infinie : Les ordinaux sont dits transfinis à partir de l'ordinal appelé omega, limite associée à la fonction identité.

Systèmes formels et ordinaux transfinis

Des logiciens tels que Alan Turing et Solomon Feferman ont étudié la possibilité d'augmenter un système formel de façon que sa proposition de Gödel devienne démontrable et de réitérer cette opération de façon transfinie.
Dans "Systems of Logic Based on Ordinals", Alan Turing a écrit :
"Le célèbre théorème de Gödel montre que tout système de logique est en un certain sens incomplet, " (Turing appelait "système de logique" ou "logique" ce qu'on appelle actuellement "système formel") "mais en même temps il indique des moyens par lesquels à partir d'un système L de logique un système plus complet L' peut être obtenu. En répétant le processus on obtient une séquence L, L1 = L', L2 = L1', ... chacun plus complet que le précédent. On peut construire une logique L omega dans laquelle les théorèmes démontrables sont la totalité des théorèmes démontrables à l'aide les logiques L, L1, L2, ... On peut alors former L 2 omega à partir de L omega de la même façon que L omega a été formé à partir de L. En procédant de cette façon on peut associer un système de logique à tout ordinal constructif" (Les ordinaux constructifs sont les ordinaux qu'on peut décrire dans un certain système de notation.) "On peut se demander si une séquence de logiques de ce type est complète dans le sens qu'à chaque problème A correspond un ordinal alpha tel que A peut être résolu au moyen de la logique L alpha." (...)

Alan Turing a construit un tel système de "logique ordinale" mais Solomon Feferman a montré que ce système n'était pas complet et il a montré que, par contre, un autre système reposant sur une itération transfinie d'un principe de réflexion uniforme permet de démontrer toutes les propositions vraies de l'arithmétique. Ce principe consiste à dire que si pour tout n, P(n) est démontrable dans un système S, alors la proposition "pour tout n, P(n)" est vraie.

Ordinaux transfinis et créativité

Avec cette méthode, on pourrait se demander si on n'a pas trouvé un moyen d'automatiser la production d'un système qui permettrait de démontrer toutes les vérités mathématiques. Mais ce n'est pas le cas. En effet, la production d'ordinaux transfinis de plus en plus grands n'est pas entièrement automatisable en ce sens que si on trouve un algorithme qui produit une suite croissante d'ordinaux, on peut définir un ordinal limite associé à cet algorithme, et donc cet ordinal limite ne sera pas atteint par cet algorithme ainsi que tous les ordinaux qui lui sont supérieurs.
Dans "Systems of Logic Based on Ordinals", Alan Turing a écrit :
"Quand on a une logique ordinale, on est en position de démontrer des théorèmes de la théorie des nombres par les opérations intuitives de reconnaissance de formules représentant des ordinaux, et les opérations mécaniques d'effectuer les conversions."
Concrètement, pour construire des ordinaux de plus en plus grands, on part de 0, on ajoute 1, on répète l'opération, on atteint ainsi 2, 3, 4... et là, on se rend compte qu'on est dans un processus répétitif, on passe alors à la limite omega, puis on continue avec omega+1, omega+2... on s'aperçoit qu'on est dans un nouveau schéma répétitif, on passe à la limite omega + omega = omega x 2, puis omega x 3, nouveau schéma répétitif, on passe à la limite omega x omega = omega puissance 2, etc..
Toute la difficulté consiste à se rendre compte qu'on est dans un schéma répétitif, et c'est là le coeur de l'intelligence créatrice, la faculté de percevoir les régularités (cf tests de QI).
Les ordinaux transfinis peuvent donc constituer une sorte de réservoir d'intelligence créative, nécessitant de mettre en oeuvre cette intelligence créative pour les construire, et pouvant la restituer si on effectue une itération transfinie d'un principe de réflexion sur un système formel.

Références