L'intelligence créative en mathématiques - Théorèmes de Gödel et ordinaux transfinis

Théorie des ensembles

"Nous appelons ensemble toute réunion M d’objets de notre conception, déterminés et bien distincts, que nous nommerons éléments de M."
Georg Cantor, 1895

Arithmétique

C'est la théorie des nombres entiers naturels (0, 1, 2, 3, ...)
Les nombres entiers naturels peuvent être représentés par des ensembles : D'une façon générale, n+1 est obtenu en introduisant n comme élément supplémentaire dans l'ensemble n.

Ordinaux transfinis

On considère l'ensemble de tous les entiers naturels {0, 1, 2, 3, ... }. On l'appelle ω. On peut alors, en utilisant le même procédé qu'avec les nombres entiers naturels, définir ω + 1 = {0, 1, 2, 3, ..., ω}. (Remarque : ω + 1 a le même nombre d'éléments que ω (on dit qu'ils ont le même cardinal) en ce sens qu'on peut établir une correspondance (on dit une bijection) qui associe 2 par 2 les éléments de ω aux éléments de ω + 1 (par exemple {(0, ω), (1, 0), (2, 1), ...}))
On peut continuer ainsi à l'infini pour obtenir ω + ω ou ω x 2 = {0, 1, 2, ..., ω, ω+1, ω+2, ...} puis ω x 3, ... ω x ω = ω puissance 2, ω puissance 3, ... ω puissance ω, ..., ω puissance ω puissance ω, ...
Tout ordinal est soit le successeur d'un autre ordinal (x+1) soit l'ordinal limite d'une suite infinie d'ordinaux x0, x1, x2, ...

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.

Propositions et prédicats

Une proposition est un énoncé complet qui peut être vrai ou faux, par exemple : "6 est un nombre pair" est une proposition vraie, "7 est un nombre pair" est une proposition fausse.
La notion de prédicat vient d'Aristote.
"Dans la grammaire traditionnelle issue d'Aristote, les mots sujet et prédicat s'opposent : le sujet étant « ce dont il s'agit » (ce qui est considéré comme connu), et le prédicat, « ce que l'on dit du sujet » (autrement dit, l'information nouvelle). Le prédicat est alors l'équivalent du syntagme verbal — c'est-à-dire du verbe, accompagné de tous ses satellites (à l'exclusion du sujet). Par exemple, dans la phrase (proposition) Paul m´a donné un livre, le sujet est Paul, et le prédicat, m'a donné un livre — ce dernier étant composé d'un groupe verbal (a donné) et de deux compléments d'objet, l'un, indirect (m’), l'autre, direct (un livre)." (Wikipedia)
En logique, un prédicat est une sorte de "proposition incomplète" qui doit être complétée par un sujet pour constituer une proposition, qui pourra être vraie ou fausse selon le sujet auquel on applique le prédicat. Par exemple "est un nombre pair" est un prédicat qui donne une proposition vraie si on l'applique à 6 et une proposition fausse si on l'applique à 7). On note P(x) la proposition obtenue en appliquant le prédicat P au sujet x.
Un prédicat peut être représenté par une formule qui comporte ce qu'on appelle une variable libre, c'est-à-dire une lettre qui représente une inconnue qu'on peut remplacer par ce qu'on veut, par exemple "n est un nombre pair". On obtient une proposition en remplaçant la variable libre par une valeur précise.

Systèmes formels

Les systèmes formels (ou théories, ou systèmes de logique selon Alan Turing) 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. "La proposition P est un théorème du système S" est équivalen à "La proposition P est démontrable dans le système S".
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.

Limitation des systèmes formels

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 gödelienne G qui est vraie mais n'est pas démontrable dans ce système formel.

Démonstration

On suppose qu'on a un système formel S englobant l'arithmétique et tel que tous les théorèmes de S sont vrais, autrement dit S ne permet pas de démontrer des propositions fausses. On va voir qu'on peut construire une proposition G qui est vraie mais n'est pas démontrable dans S.
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 naturels, par exemple en associant un chiffre ou une suite de chiffres à chaque symbole utilisé pour représenter les formules et démonstrations. 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 dans S 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 dans S 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 gödelienne de ce système formel : G = F(f).
On reformule G en remplaçant p par f dans la définition de F(p). On obtient alors :
G = "Il n'existe pas de nombre n qui soit le code d'une démonstration dans S du prédicat de code f appliqué au nombre f".
Mais étant donné que le prédicat de code f, c'est F, on a :
G = "Il n'existe pas de nombre n qui soit le code d'une démonstration dans S de F(f)"
autrement dit, étant donné que G = F(f) :
G = "Il n'existe pas de nombre n qui soit le code d'une démonstration dans S de G" ou "G n'est pas démontrable dans S" ou "G n'est pas un théorème de S".
Autrement dit, G dit "Je ne suis pas démontrable dans S" !
Supposons que G soit fausse. Cela signifierait qu'il existe un nombre n qui soit le code d'une démonstration dans S de G, donc G serait un théorème de S, donc G serait vraie puisqu'on a supposé au départ que tous les théorèmes de S sont vrais. Si G était fausse, alors G serait vraie, on aurait une contradiction, donc G n'est pas fausse, donc G est vraie. Mais puisque G exprime le fait que G n'est pas un théorème de S, G est donc une proposition vraie qui n'est pas un théorème de S. CQFD.
On peut également démontrer que non G n'est pas non plus démontrable. On ne peut donc démontrer ni la vérité ni la fausseté de G, qui est donc une proposition indécidable. La démonstration précédente ajoutée à celle de la non démontrabilité de non G démontrent le théorème de Gödel.

Les théorèmes d'incomplétudes de Gödel et le théorème de Löb

On peut également démontrer que la négation de la proposition gödelienne G n'est pas non plus démontrable. La proposition G est dite indécidable, c'est-à-dire qu'elle n'est pas démontrable et sa négation n'est pas non plus démontrable. C'est le premier théorème de Gödel, selon lequel dans tout système formel cohérent (c'est-à-dire qui ne permet pas de démontrer des propositions fausses) qui contient l'arithmétique, il existe au moins une proposition indécidable.
Gödel a également démontré un second 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.
Martin Löb a démontré un théorème plus général selon lequel, si on peut démontrer dans un système formel vérifiant les mêmes conditions que si la proposition P est démontrable dans ce système alors elle est vraie, alors la proposition P est démontrable dans ce système. Le second théorème d'incomplétude de Gödel correspond en fait au cas particulier du théorème de Löb où P correspond à une proposition fausse, étant donné que non P est équivalent à P implique faux.

Signification et conséquences philosophiques des théorèmes 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. Pour toute théorie, il existe des vérités qu'on ne peut pas démontrer dans le cadre de cette théorie, mais pour toute vérité, il existe une théorie qui permet de la démontrer. La vérité mathématique apparaît ainsi non pas comme quelque chose de figé mais comme quelque chose en construction, en progression permanente, inépuisable.
Les systèmes formels permettent de certifier les vérités mathématiques. Leurs limitations posent le problème du degré de certitude qu'on peut avoir par rapport à ces vérités mathématiques et du statut de la vérité en mathématiques.
Une machine ne peut pas accéder à toutes les vérités mathématiques. L'être humain est-il une machine très élaborée ou y a-t-il quelque chose de non mécanique en l'homme ? (esprit, conscience, libre arbitre...) ? Est-il lui-même soumis aux limitations des théorèmes de Gödel ou y échappe-t-il ?

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 gödelienne qui exprimera sa propre indémontrabilité dans ce nouveau système.
Si on part d'un certain système formel S0, on détermine sa proposition gödelienne G0, on l'ajoute à S0 en tant qu'axiome pour obtenir un nouveau système S1, ce système S1 a lui aussi sa proposition gödelienne G1, qu'on peut ajouter en tant qu'axiome à S1 pour obtenir un nouveau système S2, et ainsi de suite à l'infini. On peut alors définir un système S ω dont les théorèmes seraient la réunion des théorèmes de S0, S1, S2... Mais ce système aurait aussi sa proposition gödelienne G ω qui serait vraie mais non démontrable dans S ω, et que l'on pourrait ajouter en tant qu'axiome à S ω pour obtenir un nouveau système S ω+1, et ainsi de suite. On voit qu'on a là une construction similaire à celle des ordinaux transfinis. En fait, on pourrait de cette façon associer un système formel à chaque ordinal pour construire une suite non pas simplement infinie mais transfinie de systèmes formels.

Systèmes formels et ordinaux transfinis

On peut alors se demander si on ne pourrait pas atteindre la totalité des vérités mathématiques, non pas pas un seul système formel, mais par une telle suite transfinie de systèmes formels, en ce sens que pour toute proposition vraie P, il existerait un ordinal x tel que la proposition P serait démontrable dans le système S x.
Des logiciens tels que Alan Turing et Solomon Feferman ont étudié cette possibilité.
Au lieu d'ajouter à un système sa proposition gödelienne, Feferman utilise le "principe de réflexion uniforme" qui 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. Il a montré qu'une itération transfinie de ce principe de réflexion uniforme permet de démontrer toutes les propositions vraies de l'arithmétique. Autrement dit, pour toute proposition vraie de l'arithmétique P, il existe un ordinal x tel que en "répétant x fois" l'application du principe de réflexion uniforme à un système de départ S 0 on obtienne un système S x tel que P soit démontrable dans S x. Reste à définir la notion de "répéter x fois" où x est un ordinal. On a vu au début qu'un ordinal est soit le successeur d'un autre ordinal (x = y+1) soit la limite d'une suite infinie d'ordinaux (x = limite de y0, y1, y2, ...) Si x = y+1, répéter y+1 fois signifie répéter y fois puis appliquer une fois. Si x = limite de y0, y1, y2... répéter x fois signifie considérer le système dont les théorèmes sont la réunion des théorèmes des systèmes S y0, S y1, S y2, ...

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 ω, puis on continue avec ω+1, ω+2... on s'aperçoit qu'on est dans un nouveau schéma répétitif, on passe à la limite ω + ω = ω x 2, puis ω x 3, nouveau schéma répétitif, on passe à la limite ω x ω = ω 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éative, 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