Théorème de Gödel

Résumé court du théorème de Gödel : la vérité n'est pas toujours démontrable.

É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 évidemment 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


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...

Il y a quelque chose que je ne saisis pas...

La machine a le choix, donc de répondre : VRAI ou FAUX. Dans ce cas, il lui est impossible de répondre car il s'agit d'un paradoxe. Cependant, une personne extérieure peut affirmer sans se tromper que la machine n'a pas pu répondre à l'affirmation.

Lorsqu'on parle de vérités qui ne peuvent être démontrées, je ne suis pas certaine qu'on soit dans le même registre. Ou alors il existe des paradoxes dans les mathématiques.

Moui, en réalité, tu l'affirmes.

Citation :

Il se peut que dans certains cas, on puisse démontrer une chose et son contraire (inconsistance).

Mais il y a une chose que je ne parviens pas à éclairicir... Et je ne sais même pas de quoi il s'agit... Je comprends qu'on puisse remettre en doute la logique des mathématiques, mais c'est plutôt la preuve du théorème qui me pose question.

Je vais bientôt approfondir ce sujet. Patience.

Tout vient à point à qui sait attendre...

J'attendrai donc.

Ma chère Caspi, voici un complément d'information sur le
théorème de Gödel.

-----------------------------------------------

Théorème de l'incomplétude :

Dans n'importe quel système finiment axiomatisé cohérent et capable de formaliser l'arithmétique, on peut construire une proposition qui ne peut être ni prouvée ni réfutée dans ce système.

Théorème de l'indécidabilité :

Si T est une théorie cohérente, tout énoncé de T qui affirme la cohérence de T est un indécidable de T.

-----------------------

La démonstration de Gödel est très technique et sa lecture est donc difficile. Voici une description schématique de son raisonnement, tel qu’il le présente lui-même dans l’introduction de son article :

1) Supposons qu’il existe une Théorie Complète (TC) fondée sur un nombre fini d'axiomes et permettant, si l’on considère une phrase quelconque, de décider sans jamais se tromper si cette phrase est vraie ou non.

2) Considérons la phrase « TC ne dira jamais que la présente phrase est vraie ». Nommons cette phrase G, ce que nous noterons : G = « TC ne dira jamais que G est vraie ».

3) Soumettons G à TC et demandons à TC de dire si G est vraie ou non.

4) Si TC dit que G est vraie, alors G est fausse. Mais alors comme TC a dit que G était vraie, TC a commis une erreur. Cependant par hypothèse TC ne se trompe jamais. Donc TC ne dira jamais que G est vraie.

5) Si « TC ne dit jamais que G est vraie », G est vraie. Mais d'après ce que nous venons de voir TC ne pourra jamais le dire.

6) Il ne peut donc pas exister de Théorie Complète, c’est-à-dire de théorie permettant, quelle que soit la phrase que l'on considère, de dire si elle est vraie ou non.

Ce raisonnement rappelle le paradoxe fameux qui met en scène un Crétois disant : « Les Crétois ne disent que des mensonges ».

-----------------------------------------------

Ce qui m'amène à formuler un paradoxe inconsistant :

"La conscience décrit l'univers qui lui est extérieur (un des postulats
de la science), base des découvertes scientifiques. Cependant,
la conscience peut-elle se décrire elle-même ?"

C'est exactement la même situation que le dessinateur de caricatures.
Le dessinateur dessine des caricatures, mais le dessinateur n'a pas
pu dessiner sa main qui a permis de dessiner les caricatures.

Même exemple, quand les croyants affirment que Dieu a créé
tout l'univers, mais auxquels on demande : qui a créé Dieu ?

Même paradoxe pour l'écoulement du temps :

"Si le temps venait à ralentir ou s'accélérer, nous en apercevrions-nous ?"

Or, le temps concerne à la fois la réalité qui nous est extérieure, mais
aussi notre conscience qui permet la perception du phénomène.
Si le temps ralentissait, le mouvement des atomes observés serait
ralenti, mais les mécanismes cérébraux permettant la conscience
serait aussi ralentis, parallèlement au reste des phénomènes qui
nous sont extérieurs. Donc si le temps variait, nous ne le verrions
même pas.

Nous voyons que la nature même de la conscience est inaccessible.
Sachons que la conscience est un outil pour connaître la Réalité,
le seul moyen de connaître la conscience est d'utiliser un
outil qui ne soit pas la conscience.

Bisou à Caspi.

Merci beaucoup pour toutes ces précisions. Je pense qu'à présent, j'ai compris l'essence de ce théorème.

(Woaw... J'avoue que ma logique en prend un sacré coup. Moi qui voyait les mathématiques comme outil inébranlable, parfait... Et suffisant à lui-même.)

En effet, nous vivons dans un univers fini, donc les mathématiques
et les théories ont un champ d'investigation fini, et donc
nos connaissances ne peuvent guère être infinies.

La finitude exclut l'existence de l'absolu.


Dans la théorie quantique, chaque paquet d'énergie peut
transporter une quantité finie d'énergie. La notion d'information
et de connaissance est liée à la finitude de la quantité minimum
élémentaire de l'énergie.
Tout ceci aurait été différent si nous avions été dans un univers
dont la constante de Planck était nulle ou infinie.

Tout réside donc sur ces quantas ?

Et sinon, j'avoue ne pas comprendre le sens, ici, du mot "absolu". Mais je sens que tu vas m'éclaircir dans peu de temps...

(Merci d'avance.)

L'absolu, c'est quand on croit que la vérité est accessible formellement,
et qu'elle est définitive.

Exemple :

A l'époque d'Euclide, les mathématiciens pensaient que le théorème
de Pythagore était vrai. Cependant, il s'agit d'une vérité relative.
En effet, ce théorème de Pythagore est vrai, mais seulement si on
précise qu'il est appliqué dans un espace euclidien. Il est faux dans les
espaces non euclidiens.

Depuis Einstein et Gödel, nous savons que tout est relatif.
Il n'existe aucun repère absolu.

Aimablement à toi, chère Caspi.

Merci pour toutes ces précisions.

Une dernière demande, cependant...

Pulstars a écrit:

Il se peut que dans certains cas, on puisse démontrer une chose et son contraire (inconsistance).

Pourrais-tu en donner un exemple ? (Sauf si cela te demande des recherches trop conséquentes, je n'ai pas envie de te gêner.)

Affirmer une chose et dire le contraire oui.

Exemple :
Un individu dit : "je mens !". Si sa courte phrase dit la vérité, alors
il ment, mais alors s'il ment, il ne dit donc pas la vérité.
C'est une logique circulaire qui n'a pas d'issue.
C'est vrai ET faux (comme le principe de superposition d'états,
selon les travaux de Schrödinger en physique quantique).

D'accord, c'est bon, je voulais être certaine, et je crois que j'ai compris. Mille merci, Pulstars !

A ton service, chère demoiselle.

Je pense avoir compris ce que le théorème de Gödel implique. Mais pour moi les exemples ne sont pas approprié.
L'exemple de l'ordinateur "L'ordinateur ne répondra jamais Vrai à cette affirmation", oblige l'ordinateur à statuer sur lui même, sur la théorie lui permettant de répondre et donc finalement sur ces axiomes. Et effectivement une théorie ne peut pas dire si ces axiomes sont vrai ou faux (du moins il me semble). Les axiomes sont posés par la logique et la construction de relations, de théorèmes qui s'ensuient est nécessairement logique et cohérente avec les axiomes. Posé une question à une théorie sur ces axiomes est pour moi un peu stupide. A moins que je n'ai pas saisis l'exemple.
Si l'ordinateur était réellement capable de répondre par oui ou non avec un nombres arbitraires d'axiomes sur une portée totale d'affirmation alors pour moi ce nombres d'axiomes serait infinie et le programme ne pourrait pas exister.

Pourquoi ce théorème existe :
Selon moi, ce théorème démontre que, Les mathématiques sont imparfaites car de construction humaine. Elles n'ont donc rien d'absolue. Quelle nouvelle !

Pulsar a dit :

Citation :

En effet, nous vivons dans un univers fini, donc les mathématiques
et les théories ont un champ d'investigation fini, et donc
nos connaissances ne peuvent guère être infinies.

Je pensais que la question univers fini-infini n'avait pas encore trouvé de réponse ?

Pulsar a dit :

Citation :

La finitude exclut l'existence de l'absolu.

Pourquoi ? Au contraire, j'aurais pensé que seul l'infinie exclut l'absolue, car qui dit infini dit infinité de possibilité. Si l'univers est fini, n'était il pas plus simple que l'homme avec ses moyens finis puisse atteindre une connaissance absolue de son monde finit ?
Merci de m'éclairer sur ce point.