Mes articles Gödel liens
- Kurt Gödel et son panthéon démoniaque : vers un autre théorème sinthomatique ?canalu.tv/video/universite_de_bordeaux/les_theoremes_de_godel_fin_d_un_espoir.3954 LES THÉORÈMES DE GÖDEL : FIN D’UN ESPOIR ?EN 1931, KURT GÖDEL (1906 - 1978) DÉMONTRAIT, DANS UN ARTICLE RÉVOLUTIONNAIRE, QU'UN SYSTÈME D'AXIOMES COHÉRENT ET SUFFISAMMENT EXPRESSIF EST SUSCEPTIBLE DE GÉNÉRER DES ÉNONCÉS DONT LA VALIDITÉ NE PEUT ÊTRE DÉMONTRÉE DANS LE CADRE DES RÈGLES MÊMES QUI GOUVERNENT LA FORMULATION DE CES ÉNONCÉS ET LEURS DÉDUCTIONS. APPAREMMENT TRÈS TECHNIQUE, CE THÉORÈME BOULEVERSAIT LA PHILOSOPHIE DES MATHÉMATIQUES, ET EN PARTICULIER LA VIEILLE QUESTION DE LEUR "FONDEMENT". JEAN-MARC DESHOUILLERS SE PROPOSE ICI DE DÉCRIRE L'AVANT ET L'APRÈS GÖDEL EN RETRAÇANT L'HISTOIRE DES THÉORIES MATHÉMATIQUES DEPUIS ARISTOTE ET EUCLIDE JUSQU'AU RENVERSEMENT RÉVOLUTIONNAIRE DES FONDEMENTS MATHÉMATIQUES INDUIT PAR LE THÉORÈME D’INCOMPLÉTUDE. LA CONFÉRENCE A ÉTÉ DONNÉE À L'UNIVERSITÉ VICTOR SEGALEN BORDEAUX 2
INCOHÉRENCE & INCOMPLÉTUDE
Tous les scientifiques croyaient pouvoir mettre le monde en théorèmes, en déduction, en raisonnement sans faille... Comme on pratique en mathématique ordinaire (géométrie, par exemple). Jusqu'à l'arrivée de Gödel! En 1931, il démontre que: | |
Il se peut que dans certains cas, on puisse démontrer une chose et son contraire.
INCOHÉRENCE |
Il existe des vérités mathématiques qu'il est impossible de démontrer.
INCOMPLÉTUDE |
The impact of Gödel's theorem on twentieth-century thought is on par with that of Einstein's theory of relativity, Heisenberg's uncertainty principle, or Keynesian economics. These previously unpublished intimate and informal conversations, however, bring to light and amplify Gödel's other major contributions to logic and philosophy. They reveal that there is much more in Gödel's philosophy of mathematics than is commonly believed, and more in his philosophy than his philosophy of mathematics.Wang writes that "it is even possible that his quite informal and loosely structured conversations with me, which I am freely using in this book, will turn out to be the fullest existing expression of the diverse components of his inadequately articulated general philosophy."The first two chapters are devoted to Gödel's life and mental development. In the chapters that follow, Wang illustrates the quest for overarching solutions and grand unifications of knowledge and action in Gödel's written speculations on God and an afterlife. He gives the background and a chronological summary of the conversations, considers Gödel's comments on philosophies and philosophers (his support of Husserl's phenomenology and his digressions on Kant and Wittgenstein), and his attempt to demonstrate the superiority of the mind's power over brains and machines. Three chapters are tied together by what Wang perceives to be Gödel's governing ideal of philosophy: an exact theory in which mathematics and Newtonian physics serve as a model for philosophy or metaphysics. Finally, in an epilog Wang sketches his own approach to philosophy in contrast to his interpretation of Gödel's outlook.
Et comme le contraire de G est «G est démontrable», on ne peut pas non plus le montrer!
Du coup la théorie est forcément incomplète : ni G, ni son contraire ne peuvent être démontrés.
Cette astuce rappelle les phrases paradoxales comme « cette phrase est fausse».
Mémoires biographiques des Fellows de la Royal Society
https://rtraba.files.wordpress.com/2015/06/kreisel_kurtgoedel.pdf (KURT GODEL 28 April 1906-14 January 1978 Elected For. Mem. R.S. 1968 BY G. KREISEL, F.R.S.)
https://www.edge.org/conversation/verena_huber_dyson-g%C3%B6del-and-the-nature-of-mathematical-truth-ii (GÖDEL ET LA NATURE DES MATHÉMATIQUES VÉRITÉ IIUne conversation avec Verena Huber-Dyson [26/07/05] )
quarante-deux.org -Harry Harrison & Marvin Minsky : le Problème de Turing
wikipedia.org -Test de Turing
lemonde.fr/sciences -Réussite contestée d'un ordinateur au légendaire test de Turing
sites.google.com -TPE sur l'intelligence artificielle
https://interstices.info/alan-turing-du-calculable-a-lindecidable/Calculabilité au sens de Turing Revenons maintenant aux fonctions calculables : Turing montra, en 1937, que la classe des fonctions calculables, au sens de Church, était équivalente à la classe des fonctions programmables sur les machines imaginaires qu’il avait conçues. En son hommage, ces dernières sont connues depuis sous le nom de machines de Turing.
Des fonctions non calculables
Il existe donc aussi des fonctions qui ne sont pas calculables par un moyen purement automatique. On peut se demander s’il s’agit de fonctions « pathologiques », des monstres qui ne servent à personne, ou bien s’il y a des fonctions utiles qui ne sont pas calculables. Il y en a ; en fait beaucoup de fonctions utiles ne sont pas calculables. On peut en citer deux qui sont utiles et qui sont simples à décrire : vérifier qu’un programme s’arrête quelles que que soient ses entrées ; prouver qu’une formule logique est un théorème.
Certains programmes entrent parfois dans des boucles de calcul dont ils ne peuvent plus sortir. C’est la hantise des étudiants en programmation, et c’est aussi une belle bourde pour un programmeur. Imaginons la fonction qui analyse le texte d’un programme quelconque et détermine si ce programme s’arrête pour toutes les entrées possibles. Elle résout un problème crucial, mais elle n’est pas calculable purement automatiquement pour tous les programmes.
L’autre fonction concerne la logique. Formaliser un problème à l’aide de formules logiques (quel que soit, il existe, implique, et, ou, non…) est censé aider à le résoudre, mais cela conduit invariablement à tenter de démontrer des théorèmes. Il serait vraiment très commode qu’une fonction qui prend une formule en paramètre et détermine si elle est un théorème soit calculable. Cependant, ce n’est pas le cas, et beaucoup d’autres fonctions qui sont très utiles ne sont pas calculables non plus.
Ne pas confondre « non-calculable » et « mal défini » Machine de turing: villemin.gerard.free.fr -machine de turing: logique et intelligence artificielle
https://www.amazon.fr/D%C3%A9mons-G%C3%B6del-Logique-folie/dp/2020923394: les Démons de Gödel. Logique et folie
http://www.guillemant.net La physique de demain
https://www.youtube.com/watch?reload=9&v=Ck4iY9fFrC8: Faut-il avoir peur de l'intelligence artificielle ? Philippe guillemant par Bob Bellanca, guillemant.net/index.php?cate=conferences
https://blogs.mediapart.fr/marc-tertre/blog/091112/goedel-le-genie-la-folie-la-vie
http://lirephilosopher.canalblog.com/archives/2021/05/12/38967336.html#utm_medium=email&utm_source=notification&utm_campaign=lirephilosopher La monadologie est un résumé de l’ensemble de la philosophie de LEIBNIZ. La monade n’est autre chose qu’une substance simple qui entre dans les composés simples, c’est-à-dire sans parties
https://www.amazon.fr/Shadows-Mind-Missing-Science-Consciousness/dp/0099582112/ref=pd_sim_2?pd_rd_w=g9Vua&pf_rd_p=3cf56746-caca-49ca-a035-b272242b29b5&pf_rd_r=9WSA63XG7XCP3F0BK3P0&pd_rd_r=5eb4add6-cdf8-4118-a920-0ecac0c2d11f&pd_rd_wg=wlWQF&pd_rd_i=0099582112&psc=1 Roger Penrose: Shadows Of The Mind: A Search for the Missing Science of Consciousnes
https://arxiv.org/ftp/arxiv/papers/1509/1509.02674.pdf Godel's Incompleteness Theorems and Platonic Metaphysics Aleksandar Mikovic
https://journals.openedition.org/etudesplatoniciennes/267 Objets et idéalités dans les mathématiques contemporaines
https://saesfrance.org/les-mondes-possibles-a-laube-du-xxi-e-siecle-de-la-theorie-litteraire-a-de-nouvelles-realites-journee-detude-universite-de-pau-et-des-pays-de-ladour/ Les mondes possibles à l’aube du xxi e siècle : de la théorie littéraire à de nouvelles réalités, journée d’étude, Université de Pau et des Pays de l’Adour
https://www.persee.fr/doc/phlou_0035-3841_1952_num_50_27_4404 la notion kantienne d'analyse transcendantale Ce terme qualifie deux choses chez Kant :
- « transcendantal » se dit de tout ce qui est condition de possibilité. Appliqué à la connaissance ("connaissance transcendantale"), ce terme qualifie donc les conditions de connaissance a priori des objets. Les formes de la sensibilité, les catégories de l'entendement et le sujet (transcendantal) sont les conditions de possibilité de tout savoir scientifique : elles sont ce qui est fondement de son existence (Critique de la raison pure). La liberté est la condition de possibilité de la morale, car sans elle la moralité ne restera qu'une chimère (Critique de la raison pratique).
- « transcendantal » est de plus un adjectif qui qualifie toute étude des conditions de possibilité. La Critique de la raison pure ou la Critique de la raison pratique.
Husserl, utilise le terme de « transcendantal » dans un sens qu'il qualifie, lui-même, d'« extrêmement large pour désigner le « motif originel », qui donne son sens depuis Descartes à toutes les philosophies modernes [...] (à savoir la question), de l'ultime source de toutes les formations de connaissance, c'est l'auto-méditation du sujet connaissant sur soi-même et sur sa vie de connaissance, dans laquelle toutes les formations scientifiques qui valent pour lui ont lieu « téléologiquement », sont conservées comme un acquis et sont devenues librement disponibles [...] Cette source a pour titre « Moi-même », avec toute ma vie de connaissance réelle et potentielle [...] Il s'agit d'un concept que l'on ne peut obtenir qu'en s'enfonçant dans l'unité de l'historicité de la philosophie moderne »2.
http://michel.bitbol.pagesperso-orange.fr/Preface_Patricia2.pdf Michel Bitbol Théorie quantique et philosophie transcendantale, dialogues possibles Patrícia Kauark-Leite
http://1libertaire.free.fr/godel03.html Gödel et les limites de la logique PRÉSENCE DE L'HISTOIRE par JOHN DAWSON Démonstration des théorèmes d'incomplétude :
George Boolos spécialiste de la logique de la prouvabilité (et donc du théorème de Gödel) a récemment proposé une nouvelle démonstration du second théorème de Gödel. Avec la démonstration dite sémantique du premier théorème on a deux raisonnements qui ne retiennent que l'essentiel des idées originales de Gödel (qui exigent pour être détaillées plusieurs dizaines de pages). On s'appuie sur des propriétés élémentaires faciles à accepter (ou à prouver pour les systèmes utilisés en mathématiques) et sur une partie technique de 11 lignes. Nous présentons ici ces démonstrations pour les personnes que le formalisme et les casse-tête logiques n'effraient pas.
On se donne un système formel S à propos duquel on fera une série d'hypothèses qui permettront de prouver pour S en quelques lignes les deux théorèmes d'incomplétude de Gödel.
Lorsqu'une formule f du système S est démontrable dans S on écrit : |- f
La première hypothèse est :
(i) S est assez riche pour que l'on puisse y exprimer la propriété, notée @ f, qui signifie "il existe une preuve formelle de f dans S".
Pour obtenir @ f il suffit que le langage du système formel S contienne celui de l'arithmétique (ou celui des ensembles finis). En pratique, la formule @ f code minutieusement la définition de ce qu'est une déduction dans S. Si on devait
écrire @ f ce serait une formule longue. L'existence de @ f est une découverte positive importante de Gödel.
On fait ensuite l'hypothèse que :
(ii) si |- f alors |- @ f
(si f est démontrable dans S alors @ f est aussi démontrable dans S)
Cela signifie simplement que la capacité du système S à faire de l'arithmétique lui permet de démontrer les formules du type @ f lorsqu'elles sont vraies. On établit sans mal la propriété (ii) pour les systèmes usuels utilisés en mathématiques (arithmétique élémentaire, théorie des ensembles, etc.). On suppose ensuite :
(iii) |- @ (f -> g) -> (@ f -> @ g)
(iv) |- @ f -> @ @ f
Comme pour (ii) ces hypothèses signifient simplement que la formule @ f est écrite en suivant de près la définition des déductions dans S et que l'arithmétique de S est assez puissante. L'hypothèse suivante :
(v) S contient la logique propositionnellesignifie que les raisonnements usuels (du type si ((A et B) -> C) et A et que B alors je peux en déduire C) qu'on fait sans cesse dans une démonstration mathématique sont utilisables dans S. Cette hypothèse (que ne satisfaisait pas le système formel de la figure 1, trop élémentaire) est vérifiée par les systèmes usuels des mathématiques. La propriété :
(*) Si |- f -> g alors |- @ f -> @ g
se déduit de (ii), (iii)
et (v) en procédant comme suit : si |- f -> g, d'après (ii) on a |- @ (f -> g). En utilisant (iii) et ce qu'on appelle la règle du modus ponens (vraie en logique propositionnelle) on a : |- @ f -> @ g.
On désignera par faux une formule de S représentant la contradiction. On prend une formule f quelconque, et on pose faux = (f et NON f). Dire que S est consistant, signifie qu'avec S on ne peut pas déduire faux. Cela s'écrit donc : NON |- faux. Une formule du système S exprimant que la théorie S est consistante est donc : NON @ faux. Le second
théorème de Gödel va établir que lorsque S est consistant cette formule n'est pas démontrable dans S.
Une méthode générale
décrite par Gödel permet dans les systèmes formels assez riches de construire une formule g qui exprime sa propre non prouvabilité dans S (là encore il s'agit d'un résultat positif que les philosophes oublient à la faveur des résultats négatifs). Nous ferons l'hypothèse que S permet effectivement d'avoir une formule g telle que :
(vi) |- g <-> NON @ g
Nous supposerons (uniquement pour la démonstration du premier théorème d'incomplétude)
que S satisfait la propriété de :
(vii) correction de S pour les formules arithmétiques
Cette hypothèse signifie que lorsque S démontre une formule portant sur les nombres entiers, alors cette formule est vraie des nombres entiers usuels. La propriété (vii) est vérifiée en particulier si chaque axiome est vrai et si les règles d'inférences ne permettent de déduire que des choses vraies à partir de choses vraies. Dans les systèmes formels pour l'arithmétique, cette propriété est satisfaite car on ne choisit que des axiomes et des règles d'inférences vrais
de toute évidence. L'hypothèse (vii) est la seule hypothèse qui ne puisse se démontrer facilement pour des systèmes plus riches comme celui de la théorie des ensembles. C'est une hypothèse dite sémantique car elle se réfère au concept de formule vraie des nombres entiers usuels. Cette hypothèse est plus forte que l'hypothèse de consistance qui sera seule utile pour le second théorème [L'hypothèse (vii) implique la consistance car si S était inconsistant alors tout serait démontrable dans S et donc, en particulier, la formule arithmétique 0=1 ce qui est impossible si (vii) est vraie. ]. La formule @ f est un énoncé arithmétique, donc si S prouve @ f c'est que ce que dit @ f est vrai, c'est-à-dire : |- f. Autrement dit :
(**) si |- @ f alors |- f
Gödel dans sa démonstration initiale a préféré remplacer l'hypothèse sémantique (vii) par une hypothèse syntaxique (faisant appel uniquement à des considérations formelles) mais difficile à présenter ici et plus forte que l'hypothèse de consistance. [Gödel avait adoptée l'hypothèse d'oméga-consistance : si le S prouve une formule du type () alors pour un entier n au moins, NON |- NON P(n).]
Premier théorème d'incomplétude de Gödel
Montrons à partir de (i)-(vii) qu'il existe une formule g de S au moins telle que ni g ni NON g ne sont prouvables dans S (incomplétude). Comme nos hypothèses signifient à la fois que le système S est assez puissant et qu'il est consistant on traduira cela en disant : un système formel ne peut à la fois être puissant, consistant et complet.
De l'affirmation |- g <-> NON @ g on déduit que |- g -> NON @ g (logique propositionnelle).
Donc de |- g on déduit |- NON @ g. Il en résulte que si g est prouvable alors |- @ g (d'après (ii)) et |- NON @ g et donc le système est inconsistant ce qui contredit l'hypothèse (vii). Dans S on ne peut donc pas prouver g.
Si on suppose que S permet de prouver NON g c'est-à-dire : |- NON g alors de |- g <-> NON @ g (hypothèse (vi)) on déduit |- NON g <-> @ g et donc |- NON g -> @ g d'où on tire |- @ g et donc |- g (d'après (**) qui est une conséquence
de l'hypothèse (vii)). Or c'est impossible d'après ce que nous venons de voir au-dessus.
En résumé S ne peut ni prouver g, ni prouver NON g. La formule g est indécidable dans S.
Cette première preuve est courte mais possède le défaut d'utiliser une hypothèse sémantique. La preuve du second théorème va améliorer très sensiblement la situation : elle va, sous l'hypothèse de consistance (qui remplacera l'hypothèse sémantique (vii)) montrer que la formule exprimant la consistance de S n'est pas prouvable dans S.
Second théorème d'incomplétude de Gödel
La démonstration du second théorème de Gödel que propose Boolos commence par la série des 11 étapes suivantes :
1 |- g <-> NON @ g (hypothèse (vi))
2 |- g -> NON @ g (avec 1 et la logique propositionnelle)
3 |- @ g -> @ NON @ g (propriété (*) à partir de 2)
4 |- @ g -> @ @ g (d'après (iv))
5 |- NON @ g -> (@ g -> faux) (en logique propositionnelle, les formules du type NON q -> (q -> faux) sont démontrables)
6 |- @ NON @ g -> @ (@ g -> faux) (à partir de 5 et (*))
7 |- @(@ g -> faux) -> (@ @ g -> @ faux) (d'après (iii)
--8 |- @ g -> @ faux (logique propositionnelle à partir de 3, 6, 7 et 4)
9 |- NON @ faux -> g (logique propositionnelle à partir de 8 et 1)
10 |- @ NON @ faux -> @ g (d'après (*) et (9))
11 |- NON @ faux -> NON @ NON @ faux
(logique propositionnelle avec 8 et 10)
Donc si |- NON @ faux alors on a à la fois |- NON @ NON @ faux d'après 11 et |- @ NON
@ faux par (ii) et donc |- faux. Par contraposition : si NON |- faux (S est consistant) alors on a NON |- NON @ faux (S ne prouve pas que S est consistant).
Un système formel consistant vérifiant les hypothèses (i)-(vi) ne peut pas prouver qu'il est consistant : un système formel S ne peut être à la fois riche, consistant et prouver qu'il est consistant
