Théoréme de Godël

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

Le théorème de Gödel

Énoncé simplifié du théorème d'incomplétude :
Dans toute branche des mathématiques suffisamment complexe (par exemple l'arithmétique), il existe une infinité de faits vrais qu'il est impossible de prouver en utilisant la branche des mathématiques en question. Bien évidement le théorème tel qu'il a été écrit par Gödel est plus précis, de même que la preuve qu'il en a donné. L'idée de cette preuve est néanmoins accessible, et nous en donnons plus loin une esquisse.

Qu'a fait Gödel avec son théorème ?
Jusqu'au début du siècle les mathématiciens étaient persuadés qu'on pouvait, un peu à la manière des écoliers en géométrie, démontrer toutes les vérités mathématiques par déduction.

Gödel a démontré en 1931 deux résultats mathématiques :
=> Il se peut que dans certains cas, on puisse démontrer une chose et son contraire (inconsistance).
=> Il existe des vérités mathématiques qu'il est impossible de démontrer (incomplétude)
Le plus célèbre de ces résultats est le second, qu'on appelle théorème d'incomplétude de Gödel.

Quelques définitions
Système formel
Preuve
Machine de Turing
Programme informatique
(voir le glossaire en bas de la page)

Une preuve simplifiée du théorème
Malgré les performances et la diversité des ordinateurs actuels, tous ont un modèle théorique commun appelé machine de Turing. On peut donner à une machine de Turing un programme arbitrairement long, mais évidemment de taille finie, qui répond VRAI ou FAUX à une affirmation qu'on lui donne, sans jamais se tromper.
La question est:
Si un humain est capable de savoir si la phrase qu'il donne à la machine est vraie ou fausse, la machine est-elle aussi capable de découvrir la vérité ?

Gödel donne alors la phrase suivante à la machine:
"La machine ne répondra jamais VRAI à cette phrase"

Que fait la machine ?

Si elle répond VRAI, elle affirme que "La machine ne répondra jamais VRAI à cette phrase" est une affirmation vraie. Or ce n'est pas le cas, puisqu'elle vient justement de répondre VRAI à la phrase. Si la machine ne se trompe pas, elle ne peut donc pas répondre VRAI.

Si elle répond FAUX, elle affirme que "La machine ne répondra jamais VRAI à cette phrase" est une affirmation fausse. Or l'affirmation n'est pas fausse puisque la machine vient justement de répondre FAUX. Si la machine ne se trompe pas, elle ne peut donc pas répondre FAUX.

Et nous, pouvons nous répondre à la question ?...
La phrase dit : "La machine ne répondra jamais VRAI à cette phrase". Nous venons de voir qu'en effet, la machine ne peut pas répondre VRAI. Nous savons donc que cette phrase est une vérité. Pourtant la machine ne pourra pas la découvrir...
_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

Suite :

Voyons le théorème d'un peu plus près :

La géométrie d'Euclide
Tous les écoliers le savent, la géométrie est une discipline déductive. Elle se différencie en cela des sciences physiques, par exemple, qui sont une science en partie expérimentale car on peut vérifier la véracité de ce que l'on affirme par l'expérience.

D'aucun répondront qu'on peut faire de même en géométrie : mesurer un angle, les côtés d'un triangle...Eh bien, oui et non... Ce qui a fait le succès de la géométrie et le malheur de nombreux écoliers depuis les Grecs c'est la méthode axiomatique utilisée par Euclide, qui permet de démontrer en géométrie des théorèmes en utilisant uniquement la logique de l'esprit et des axiomes de base (axiomes d'Euclide par exemple) comme le fameux :

"Par deux points, on ne mène qu'une droite"

Ce type de démonstration se passe de vérification par l'expérience. Le côté évidement vrai des axiomes et la logique normalement implacable de la déduction font que le résultat obtenu ne peut être que vrai, ce qui a fait de la géométrie Euclidienne un modèle de connaissance scientifique pendant 2000 ans.

On pensait encore, il y a 200 ans, que toutes les branches des mathématiques, à l'instar de la géométrie, pouvaient être axiomatisées et qu'on pouvait déduire logiquement de ces axiomes toutes les vérités concernant la discipline en question.

Mais au 19ème siècle, certains scientifiques ont remplacé un des axiomes d'Euclide :

"par un point donné, on fait passer exactement une parallèle à une droite donnée"

par un autre énoncé, comme par exemple celui de Riemann :

"par un point hors d'une droite, on ne peut faire passer aucune parallèle à cette droite"

En utilisant le nouveau jeu d'axiomes comme vérités de base, on peut déduire, comme en géométrie Euclidienne, des théorèmes, dont certains seront faux dans notre monde, puisqu'ils sont déduis d'un axiome faux dans notre monde (ce qui n'exclu pas qu'ils soient justes dans un monde imaginaire dans lequel les axiomes seraient vrais).

Ce phénomène a fait prendre conscience aux mathématiciens que la géométrie était une chose "palpable", dont les affirmations, énoncés et théorèmes n'étaient pas vides de sens, et que ce sens "intuitif" pouvait les gêner dans leur tâche qui consiste à déduire une chose de certaines autres, sans forcément se soucier de la véracité des faits démontrés.
Or on sait qu'il faut se méfier de l'intuition et du « C'est clair ! » des profs de maths, comme le montre l'exemple suivant dû à Russel :

Il y a deux sortes d'ensembles, les ensembles normaux, qui ne se contiennent pas eux même, comme l'ensemble des mots de ce texte, et les ensembles non-normaux, qui se contiennent eux même, comme l'ensemble des choses dont on parle dans ce texte (en effet, je viens d'en parler). Considérons à présent N, l'ensemble des ensembles normaux. La question est : N est-il normal ?
=> Si N est normal, alors, il est dans N puisque N est l'ensemble des ensembles normaux. N se contient donc lui-même et par conséquent N est non-normal.
=> Au contraire, si N est non-normal, alors il se contient lui-même, or les éléments de N sont les ensembles normaux, donc N est normal.

Où est passée l'intuition...?

La tentative de Hilbert
Afin de trouver une solution à un certain nombre de ces problèmes, Hilbert a proposé au début du siècle un programme de recherche visant entre autres à formaliser les mathématiques, c'est à dire à définir les termes utilisés de façon non ambigu et sans faire appel à l'intuition.

Un des buts de Hilbert était d'obtenir des théories formelles en mathématiques, c'est à dire :

=> un ensemble de règles pour écrire les formules
=> un ensemble d'axiomes (formules de base qui représentent ce qu'on juge vrai) écrits dans le système formel
=> un ensemble de règles de transformation qui permettent de passer d'une formule à une autre, c'est à dire de déduire d'un axiome ou d'un théorème, un nouveau théorème

Les règles doivent être suffisamment précises pour être applicables mécaniquement, par une machine par exemple, sans faire appel à l'intelligence.
On pourrait ainsi programmer un ordinateur en lui donnant les règles et les axiomes, puis en lui demandant d'appliquer successivement toutes les règles à tous les axiomes, dans un processus éventuellement infini. L'ordinateur serait alors capable de lister tout ce qu'on peut déduire des axiomes, c'est à dire tous les théorèmes possibles de la théorie formelle.
Imaginons à présent que nous voulions savoir si une certaine formule F est un théorème, c'est à dire si elle peut être déduite des axiomes en utilisant une suite de déductions. Quatre cas peuvent se présenter si nous utilisons l'ordinateur en question :

1. Il listera la formule F , et pas la formule non F
2. Il listera la formule non F , et pas la formule F
3. Il listera la formule F et la formule non F
4. Il ne listera ni la formule F , ni la formule non F

Dans le cas 1, cela signifie que la formule F est un théorème. Dans le cas 2, que la formule non F est un théorème. Que dire des autres cas ? Dans le cas 3, on dit que la théorie est inconsistante, c'est à dire qu'on peut à la fois prouver une chose et son contraire. Dans le quatrième cas, on dit que la théorie est incomplète, c'est à dire qu'il existe des choses dont on ne peut savoir si elles sont vraies ou non.

Un exemple concret de système formel, avec redéfinition des termes consistance et complétude est accessible ici.

La deuxième partie du programme de Hilbert consistait justement à démontrer que les théories formelles des mathématiques étaient consistantes.

Si beaucoup de travail a été réalisé en ce qui concerne la formalisation des mathématiques (des théories formelles pour de nombreuses branches des mathématiques ont été développées à partir du 19ème siècle, avant même le programme de Hilbert), il a fallu attendre les résultats de Gödel, assez inattendus, pour répondre entre autres à la deuxième partie du programme.

La réponse de Gödel
En 1931, dans un article intitulé "Über formal unentscheidbare Sâtze der Principia Mathematica und verwandter Systeme" (Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés) Gödel a démontré qu'il était impossible de prouver la consistance d'un certain nombre de théories formelles (dont l'arithmétique) en utilisant ces théories, contrairement à ce que semblait croire Hilbert. Ce premier résultat, très inattendu pour l'époque s'est accompagné d'un deuxième, plus célèbre, le théorème d'incomplétude qui énonce que la plupart des théories formelles (dont l'arithmétique), si elles sont consistantes, sont incomplètes, c'est à dire qu'il existe des résultats effectivement vrais qui ne peuvent pas être prouvés dans cette théorie.

Pour en revenir à notre ordinateur qui déduit des théorèmes, les résultats de Gödel prouvent que pour la plupart des théories formelles, il existe des formules F pour lesquelles l'ordinateur sera confronté au 3ème ou au 4ème cas.

Très basiquement, la démonstration de Gödel a consisté à écrire le paradoxe du menteur (Tous les crétois sont des menteurs, c'est un crétois qui le dit...) en utilisant l'arithmétique. Plus précisément, il a construit une formule de l'arithmétique qui affirme d'elle même qu'elle est indémontrable.

Le système formel qu'a utilisé Gödel pour sa démonstration est voisin de celui des Principia Mathematica de Whitehead et Russell. Ce système formel permet d'exprimer les relations arithmétiques courantes.
Nous ne referons pas bien sûr dans la suite la démonstration complète de Gödel qui est longue et difficile, mais nous essaierons d'en indiquer clairement les étapes.

La numération de Gödel et les métamathématiques
La première étape a consisté à assigner à chaque symbole du sytème formel un nombre différent. Puis Gödel a trouvé le moyen d'affecter un nombre à chaque formule (en faisant le produit des premiers nombres premiers élevés à la puissance du nombre représentant les symboles qui y figurent), puis à chaque suite de formule.
L'important est de comprendre qu'un nombre de Gödel étant donné, on peut déterminer si c'est une suite de formules (et si oui de quelles formules elle est composée), une formule (et si oui laquelle) ou un symbole.
Inversement, étant donné un symbole, une formule ou une suite de formules, on peut facilement calculer le nombre de Gödel associé.

Tous ces nombre qui représentent des formules ou des suites de formules représentent donc des faits de l'arithmétique, mais nous pouvons aussi nous intéresser à la méta-arithmétique, qui consiste à parler des faits qui concernent l'arithmétique. Par exemple, dire que

"Pour tout x, il existe y tel que y > 2x"

est un fait arithmétique, c'est à dire un fait qui concerne les nombres entiers. D'un autre côté, dire que

La formule "Pour tout x, il existe y tel que y > 2x" est démontrable en arithmétique

est un fait meta-arithmétiquen, c'est à dire un fait qui concerne l'arithmétique.

Les formules et suites de formules étant représentés par Gödel sous forme de nombres, celui-ci a ainsi pu exprimer des faits méta-arithmétiques par des formules arithmétiques... Par exemple, dire qu'une formule de nombre de Gödel g1 contient la formule de nombre de Gödel g2 revient plus ou moins, avec la méthode de Gödel à affirmer que g2 est un diviseur de g1, ce qui une propriété arithmétique, exprimant un fait méta-arithmétique.
Gödel a ainsi réussi à exprimer, en utilisant les nombres de Gödel et l'arithmétique (mais la formule reste assez complexe) que :

La formule de nombre de Gödel g1 est démontrable par la suite de formules de nombre de Gödel g2.

Dans la suite, nous appellerons cette formule G.

La preuve d'incomplétude
La suite du raisonnement a été de montrer que si G était était démontrable, alors la négation de G le serait aussi, et inversement. On aurait alors la possibilité de démontrer une formule et son constraire, ce qui est la définition de l'inconsistance vue plus haut. Par conséquent, si on suppose que le système formel employé est consistant (i.e. que l'arithmétique est consistante), alors on ne peut pas démontrer la formule G ni son contraire. On dit que G est indécidable. Or, la formule G dit que la formule G est indémontrable (rappellons la formule)

n : Il n'existe aucun nombre de Gödel qui représente une suite de formule qui soit la démonstration de la formule portant le nombre de Gödel n

Cette affirmation métamathématique (disant que G est indémontrable) est manifestement vraie, comme nous venons de le voir. Et elle est representée par une formule arithmétique, selon la methode de Gödel, qui est donc vraie elle aussi...

Gödel a donc au final construit une fomule arithmétique qui est vraie, et qu'on ne peut pas démontrer en utilisant un système formel de l'arithmétique si celui-ci est consistant.

En allant un peu plus loin, Gödel a montré que même en posant comme axiome que G soit vraie, on pourrait toujours trouver une formule vraie et indémontrable, ce qui signifie que si l'arithmétique est consistante, non seulement elle est incomplète, mais le sera toujours même si on y ajoute des axiomes supplémentaires.

Inconsistance de l'arithmétique ?
Par un raisonnement un peu similaire, Gödel a construit une formule, exprimée dans le système formel qui affirme que :

Si l'arithmétique est consistante, alors la fomule G est vraie.

Puis il démontre cette affirmation, toujours en utilisant le système formel. Ceci implique que si on pouvait démontrer dans le système formel, que l'arithmétique est consistante, alors, en utilisant la preuve donnnée par Gödel, il s'en suivrait que G serait démontrable dans le système formel. Or nous venons de voir que ce n'était pas le cas. Par conséquent, c'est qu'il est impossible de démontrer dans le système formel que l'arithmétique est consistante, ce qui a apporté une réponse au problème de Hilbert...
_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

Suite 2

Les conséquences du théorème

Les deux théorèmes de 1931 de Gödel sur l'inconsistance et l'incomplétude de l'arihtmétique du premier ordre ont eu des répercussions importantes sur la pensée philiosophique moderne.

La première conséquence de ces théorèmes est que la Vérité ne peut pas être exprimée en terme de démonstrabilité. Une chose prouvable n'est pas nécéssairement vraie et une chose vraie n'est pas toujours prouvable. Beaucoup de philisophes ont pensé le contraire et ont essayé de définir la vérité comme étant égale aux choses démontrables. De manière générale, dans quasiment toutes les entreprises intellectuelles conséquentes, on peut exprimer des arguments mathématiques simples et on risque donc de rentrer dans le cadre du théorème de Gödel. Je peux ainsi prétendre des choses fausses sans qu'on ne puisse démontrer le contraire.

De la même manière, je peux prétendre des choses vraies sans pouvoir me justifier par une démonstration De la même manière que l'ensemble des vérités est plus important que l'ensemble de ce qui est démontrable, la réalité est plus importante que l'ensemble des connaissances possibles. Contrairement aux enseignements de nombreux philosophes, être raisonné n'est pas simplement une question de règles. La raison est créative et originale. Pour trouver des vérités dans un système donné, il faut pouvoir s'en extraire et pour cela il faut une raison qui soit capable non pas de simplement rajouter des axiomes à un système mais d'en créer un nouveau dans lequel l'ancienne vérité indémontrable deviendra au contraire tout à fait démontrable.

source http://www.jutier.net/contenu/kgodel.htm
_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre

Neptune Age : 19 Inscrit le : 08 Déc 2005 Messages : 401

Très intéressant, même si c'est long et qu'il me faut un peu de concentration... Merci. Smile

_________________
"L'idéal du calme est dans un chat assis."
Jules Renard

Uranus Inscrit le : 06 Mar 2005 Messages : 382 Localisation : Laval

N'empeche c'est marrant de se dire que quoi qu'il arrive il y a des choses qu'on ne peut pas démontrer avec les math pourtant c'est des affirmations vraie !! c'est quelque peu casse tete !! mais c'est quand même très interressant !!
_________________
Richard

http://riri-astronomie.site.voila.fr

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

C'est en effet un casse téte, et pourtant c'est logique Smile

La science n'est pas toujours là pour expliquer et démontrer, mais pour comprendre, tout simplement Wink

_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre

Mercure Inscrit le : 02 Avr 2006 Messages : 23

Après avoir relu une paragraphe sur quatre du second message, j'ai enfin terminé la lecture et je crois avoir compris, en partie du moins.

Depuis une bonne douzaines d'année (je n'ai que 18 ans), je me suis toujours dit que je ne voyais pas en quoi nos mathématiques pouvaient s'appliquer à l'ensemble de l'Univers.
En effet, les mathématiques ont été créé par des êtres qui se trompent bien souvent. Ainsi, la probabilité d'inventer une science qui s'applique à tout un ensemble infini qui nous est pratiquement totalement inconnu tend vers zéro.
De plus, si nos mathématiques nous permettent de comprendre, d'analyser et d'effectuer énormément d'expériences et événements de l'Univers, je pense que cela n'est que dû qu'à des manipulations mathématiques; un peu comme si on se débrouillait pour que cela fonctionne.

Or nous venons de voir que nos mathématiques ne peuvent pas tout montrer et sont eronnés.

Par conséquent, je suis encore plus convaincu, après avoir lu le texte précédent, que nos mathématiques sont de loin les meilleurs et les plus simples, notamment lorsqu'ils doivent être appliqués aux concepts complexes.
Ainsi, des phénomènes astrophysique ne pourront probablement jamais être démontrés avec nos mathématiques: il faudra alors en créer de nouveaux que l'on différencierait de nos mathématiques actuels et qui ne serviraient qu'à démontrer des phénomènes qui n'ont pu être jusqu'alors démontrer.

-- Fin de ma petite paranthèse peu utile et très peu claire (avis personnel et sûrement partagé par tous Smile

)

Invité

Le théorème de Gödel s'applique surtout pour les langages mathématiques formels.

Les maths sont un outil élaboré par l'Homme, tandis que les phénomènes astrophysiques sont des faits. L'analyse des faits peut être erronée, altérée, faussé par nos sens, nos outils mathématiques, nos croyances.
Mais les faits en eux-mêmes restent ce qu'ils sont. Wink

La connaissance dépend des observateurs.

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

Nos mathématiques ne sont pas éronnés. Ils ne peuvent pas répondre à tout, tout simplement Smile

_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre

Invité

Disons que la quête de connaissances possède une limite.

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

Je ne pense pas que nos connaissances aient une limite. Par contre, il est fort probable que les mathématiques seules ne peuvent pas tout résoudre.
_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre

Invité

Rooo, ne te contredis pas, lol.

rireeee

Vénus Inscrit le : 03 Jan 2006 Messages : 59 Localisation : Bretagne

Bonjour,

Enfin j'ai réussi à revenir sur ce forum!! Son accès m'était devenu interdit sans que je ne sache pourquoi...

Pour revenir au sujet, je voulais dire au jeune homme qui est intervenu plus haut (Xionbox) ceci:
Les mathématiques sont une construction de l'esprit qui s'est affinée et élargie au fil des siècles. Cette construction suit des règles bien précises indépendamment de l'observation (qui bien souvent nous induit en erreur d'ailleurs). C'est pour cela, par exemple, qu'il existe plusieurs géométries ( celle d'Euclide, celle de Riemann que l'on voit en terminale je crois et d'autres encore que tu ne connais pas).
Cependant, il y a justement des coincidences assez curieuses en étudiant certains phénomènes physiques.
Par exemple, la forme des dunes de sable est une parabole tout comme la trajectoire obtenue en lançant soit même un objet en l'air. La courbe obtenue en suspendant aux deux extrémités une corde est une chaînette c'est-à-dire une fonction hyperbolique... et il n'y a aucune manipulation forcée là-dedans!

Il n'a jamais été question que les mathématiques puissent tout expliquer. Elles ne constituent, seulement, qu'un outil indispensable aux autres disciplines. Mais la nature aime parfois aussi les maths et on en trouve même dans les pétales de roses!! Pas poétique cela? (hihi)

Cordialement,
_________________
Einstein

Invité

Einstein avait été banni ? Clavius peut-il nous expliquer cet incident ?

Soleil Inscrit le : 17 Oct 2004 Messages : 22300

Salut

Personne n'a été banni ! C'est surement un plantage de serveur ou des forumactifs, cela arrive. Wink

_________________
Astronomiquement Votre, Clavius

http://ceraastronomie.monsite.orange.fr/
http://monsite.orange.fr/astronomie.photo
http://monsite.orange.fr/nature-audomarois
http://monsite.orange.fr/ciel-et-terre