Théorème de Gödel - histoire des types. Confession d'un grand logicien

Théorèmes d'incomplétude de Gödel

Théorèmes d'incomplétude de Gödel

Théorèmes d'incomplétude de Gödel- deux théorèmes de logique mathématique sur les limites fondamentales de l'arithmétique formelle et, par conséquent, de toute théorie du premier ordre suffisamment forte.

Le premier théorème stipule que si l’arithmétique formelle est cohérente, alors elle contient une formule irréductible et irréfutable.

Le deuxième théorème stipule que si l’arithmétique formelle est cohérente, alors elle contient une formule non dérivable qui affirme de manière significative la cohérence de cette théorie.

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

L'énoncé du premier théorème d'incomplétude de Gödel peut être énoncé comme suit :

En démontrant le théorème, Gödel a construit la formule G explicitement, on l'appelle parfois la formule indécidable de Gödelian. Dans l'interprétation standard, la phrase G affirme sa propre irréductibilité dans S. Par conséquent, d'après le théorème de Gödel, si une théorie S est cohérente, alors cette formule est effectivement irréductible dans S et donc vraie dans l'interprétation standard. Ainsi, pour les nombres naturels, la formule G est vrai, mais ne peut pas être dérivé dans S.

La preuve de Gödel peut également être effectuée pour toute théorie obtenue à partir de S en ajoutant de nouveaux axiomes, par exemple la formule G comme un axiome. Par conséquent, toute théorie cohérente qui serait une extension de l’arithmétique formelle sera incomplète.

Pour prouver le premier théorème d'incomplétude, Gödel a attribué un numéro spécifique à chaque symbole, expression et séquence d'expressions en arithmétique formelle. Puisque les formules et les théorèmes sont des phrases arithmétiques et que les dérivations formelles des théorèmes sont des séquences de formules, il est devenu possible de parler de théorèmes et de preuves en termes de nombres naturels. Par exemple, laissez la formule indécidable de Gödelian G a un numéro m, alors cela équivaut à l'énoncé suivant dans le langage de l'arithmétique : « il n'existe pas un tel nombre naturel n, Quoi n il y a un numéro de sortie de formule avec un numéro m". Une telle comparaison de formules et de nombres naturels s'appelle l'arithmétisation des mathématiques et a été réalisée pour la première fois par Gödel. Cette idée est ensuite devenue la clé pour résoudre de nombreux problèmes importants de logique mathématique.

Esquisse de la preuve

Fixons un système PM formel dans lequel les concepts mathématiques élémentaires peuvent être représentés.

Les expressions d'un système formel sont, vues de l'extérieur, des séquences finies de symboles primitifs (variables, constantes logiques et parenthèses ou points), et il n'est pas difficile de spécifier strictement quelles séquences de symboles primitifs sont des formules et lesquelles ne le sont pas. De même, d’un point de vue formel, les preuves ne sont rien d’autre que des séquences finies de formules (aux propriétés strictement définies). Pour des considérations mathématiques, peu importe les objets que nous prenons comme symboles primitifs, et nous décidons d'utiliser des nombres naturels à ces fins. En conséquence, la formule est une séquence finie de nombres naturels, la conclusion de la formule est une séquence finie de séquences finies de nombres naturels. Les concepts (énoncés) mathématiques deviennent ainsi des concepts (énoncés) sur les nombres naturels ou leurs séquences, et peuvent donc eux-mêmes être exprimés dans le symbolisme du système PM (au moins en partie). On peut montrer notamment que les notions « formule », « dérivation », « formule dérivable » sont définissables au sein du système PM, c'est-à-dire qu'il est possible de restituer, par exemple, la formule F(v) en PM avec une variable libre v(dont le type est une séquence de nombres) tel que F(v), dans une interprétation intuitive, signifie : v- formule dérivée. Construisons maintenant une phrase indécidable du système PM, c'est-à-dire la phrase UN, pour lequel ni l'un ni l'autre UN, ni l'un ni l'autre non-A non dérivable, comme suit :

Une formule en PM avec exactement une variable libre dont le type est un nombre naturel (une classe de classes) sera appelée une classe d'expression. Organisons les expressions de classe dans une séquence d'une manière ou d'une autre, notons n-e à travers R.(n), et notons que le concept d '«expression de classe», ainsi que la relation d'ordre R. peut être déterminé dans le système PM. Soit α une expression de classe arbitraire ; à travers [α; n] désigne la formule formée à partir de l'expression de classe α en remplaçant la variable libre par le symbole d'un nombre naturel n. Relation ternaire x = [oui;z] s'avère également définissable en PM. Nous allons maintenant définir la classe K nombres naturels comme suit :

(où Bew x moyens: x- formule dérivée). Puisque tous les concepts présents dans cette définition peuvent être exprimés en PM, il en est de même pour le concept K, qui est construit à partir d'eux, c'est-à-dire qu'il existe une telle classe d'expression S, que la formule [ S;n], interprété intuitivement, signifie qu'un nombre naturel n appartient K. En tant que classe d'expression, S identique à certains spécifiques R.(q) dans notre numérotation, soit

est valable pour un nombre naturel spécifique q. Nous allons maintenant montrer que la phrase [ R.(q);q] indécidable en PM. Donc, si la phrase [ R.(q);q] est supposé dérivable, alors il s'avère vrai, c'est-à-dire conformément à ce qui a été dit ci-dessus, q appartiendra K, c'est-à-dire conformément à (*), ¬Bew[ R.(q);q] sera exécuté, ce qui contredit notre hypothèse. En revanche, si la négation [ R.(q);q] était déductible, alors ¬ n ∈ K, c'est-à-dire Bew[ R.(q);q] sera vrai. Ainsi, [ R.(q);q] ainsi que sa négation seront déductibles, ce qui est encore une fois impossible.

Forme polynomiale

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

En arithmétique formelle S, on peut construire une formule qui, dans l’interprétation standard, est vraie si et seulement si la théorie S est cohérente. Pour cette formule, l’énoncé du deuxième théorème de Gödel est vrai :

En d’autres termes, la cohérence de l’arithmétique formelle ne peut être prouvée au moyen de cette théorie. Cependant, il existe des preuves de la cohérence de l'arithmétique formelle en utilisant des moyens qui n'y sont pas exprimables.

Esquisse de la preuve

La formule est d’abord construite Escroquer, qui exprime de manière significative l'impossibilité de dériver une formule dans la théorie S avec sa négation. Alors l'énoncé du premier théorème de Gödel est exprimé par la formule Escroquer ⊃ G, Où G- La formule insoluble de Gödel. Tout raisonnement pour prouver le premier théorème peut être exprimé et réalisé au moyen de S, c'est-à-dire que la formule est déductible dans S Escroquer ⊃ G. Donc, si dans S est dérivable Escroquer, alors c'est déductible et G. Cependant, d’après le premier théorème de Gödel, si S est cohérent, alors G n'y est pas déductible. Par conséquent, si S est cohérent, alors la formule qu'il contient est également irréductible Escroquer.

Remarques

Voir aussi

Links

• V.A. Ouspenski Théorème d'incomplétude de Gödel. - M. : Nauka, 1982. - 110 p. - (Conférences populaires sur les mathématiques).
• L'académicien Yu. L. Ershov "Preuve en mathématiques", programme A. Gordon du 16 juin 2003
• A. B. Sosinsky Théorème de Gödel // École d'été "Mathématiques modernes". - Doubna : 2006.
• P.J. Cohen Sur les fondements de la théorie des ensembles // Avancées des sciences mathématiques. - 1974. - T. 29. - N° 5 (179). - pages 169 à 176.
• M. Kordonski La fin de la vérité. - ISBN5-946448-001-04
• V.A. Ouspenski Théorème de Gödel sur l'incomplétude et quatre routes qui y mènent // École d'été "Mathématiques modernes". - Doubna : 2007.
• Zenkin A.A. Le principe de division du temps et analyse d’une classe de raisonnements plausibles quasi-finis (en utilisant l’exemple du théorème de l’indénombrable de G. Cantor) // DAN. - 1997. - T. 356. - N° 6. - P. 733-735.
• Tchéchuline V. L. Sur une version courte de la preuve des théorèmes de Gödel // « Problèmes fondamentaux des mathématiques et des sciences de l'information », documents du XXXIVe séminaire-école de mathématiques d'Extrême-Orient du nom de l'académicien E.V. Zolotova. - Khabarovsk, Russie : 2009. - P. 60-61.

Fondation Wikimédia.

2010.

Voyez ce que sont les « théorèmes de Gödel sur l’incomplétude » dans d’autres dictionnaires :

Ce terme a d'autres significations, voir le théorème de Gödel. Le théorème de Gödel sur l'incomplétude et le deuxième théorème de Gödel [1] deux théorèmes de logique mathématique sur les limites fondamentales de l'arithmétique formelle et, par conséquent, de tout ... ... Wikipédia

Les théorèmes d'incomplétude de Gödel sont deux théorèmes de logique mathématique sur l'incomplétude des systèmes formels d'un certain type. Table des matières 1 Premier théorème d'incomplétude de Gödel 2 Deuxième théorème d'incomplétude de Gödel ... Wikipédia

Ce terme a d'autres significations, voir le théorème de Gödel. Le théorème de Gödel sur l'exhaustivité du calcul des prédicats est l'un des théorèmes fondamentaux de la logique mathématique : il établit un lien sans ambiguïté entre la vérité logique... ... Wikipédia Nom commun de deux théorèmes établis par K. Gödel. D'abord G. t. à propos de n. déclare que dans tout système formel cohérent contenant un minimum d'arithmétique (les signes et les règles habituelles pour les manipuler), il existe un formellement indécidable... ...

Encyclopédie mathématique L’un des théorèmes les plus célèbres de la logique mathématique est à la fois chanceux et malchanceux. En cela, elle ressemble à la théorie de la relativité restreinte d’Einstein. D’une part, presque tout le monde en a entendu parler. D’un autre côté, dans l’interprétation populaire, la théorie d’Einstein, comme on le sait,. Et le théorème de Gödel sur l'incomplétude (ci-après simplement TGN), dans à peu près la même formulation populaire libre, "prouve qu'il existe des choses incompréhensibles pour l'esprit humain". Ainsi, certains tentent de l’adapter comme argument contre le matérialisme, tandis que d’autres, au contraire, prouvent avec son aide que Dieu n’existe pas. Ce qui est drôle, c’est non seulement que les deux côtés ne peuvent pas avoir raison en même temps, mais aussi que ni l’un ni l’autre ne prennent la peine de comprendre ce que dit réellement ce théorème.

Et alors ? Ci-dessous je vais essayer de vous en parler « sur les doigts ». Ma présentation sera bien entendu peu rigoureuse et intuitive, mais je demanderai aux mathématiciens de ne pas me juger strictement. Il est possible que pour les non-mathématiciens (dont je fais partie en fait), il y ait quelque chose de nouveau et d'utile dans ce qui est décrit ci-dessous.

La logique mathématique est en effet une science assez complexe, et surtout peu familière. Cela nécessite des manœuvres prudentes et strictes, dans lesquelles il est important de ne pas confondre ce qui a été réellement prouvé avec ce qui est « déjà clair ». Cependant, j'espère que pour comprendre le « aperçu d'une preuve de TGN » suivant, le lecteur n'aura besoin que de connaissances en mathématiques/informatique au lycée, de capacités de réflexion logique et de 15 à 20 minutes.

En simplifiant quelque peu, TGN affirme que dans des langages suffisamment complexes, il existe des déclarations non prouvables. Mais dans cette phrase, presque chaque mot nécessite une explication.

Commençons par essayer de comprendre ce qu'est une preuve. Prenons un problème d'arithmétique scolaire. Par exemple, disons que nous devons prouver l’exactitude de la formule simple suivante : « » (permettez-moi de vous rappeler que le symbole se lit « pour tout » et est appelé « quantificateur universel »). Vous pouvez le prouver en le transformant à l’identique, disons, comme ceci :

Le passage d'une formule à une autre s'effectue selon certaines règles bien connues. La transition de la 4ème formule à la 5ème s'est produite, disons, parce que chaque nombre est égal à lui-même - c'est un axiome de l'arithmétique. Et toute la procédure de preuve traduit ainsi la formule en la valeur booléenne VRAI. Le résultat pourrait aussi être un MENSONGE – si nous réfutions une formule. Dans ce cas, nous prouverions son déni. On peut imaginer un programme (et de tels programmes ont en fait été écrits) qui prouverait des déclarations similaires (et plus complexes) sans intervention humaine.

Disons la même chose de manière un peu plus formelle. Supposons que nous ayons un ensemble constitué de chaînes de caractères d'un certain alphabet, et qu'il existe des règles par lesquelles, à partir de ces chaînes, nous pouvons sélectionner un sous-ensemble de ce que l'on appelle déclarations- c'est-à-dire des phrases grammaticalement significatives, dont chacune est vraie ou fausse. Nous pouvons dire qu'il existe une fonction qui associe les instructions à l'une des deux valeurs suivantes : VRAI ou FAUX (c'est-à-dire les mapper dans un ensemble booléen de deux éléments).

Appelons une telle paire - un ensemble d'instructions et une fonction de à - "langage des déclarations". Notez qu'au sens courant, le concept de langage est un peu plus large. Par exemple, l'expression russe "Venez ici!" ni vrai ni faux, c'est-à-dire que du point de vue de la logique mathématique, ce n'est pas une affirmation.

Pour aller plus loin, nous aurons besoin du concept d’algorithme. Je n’en donnerai pas ici une définition formelle, car cela nous égarerait assez loin. Je me limiterai à l'informel : "algorithme" est une séquence d’instructions non ambiguës (« programme ») qui en un nombre fini d'étapes convertit les données sources en résultats. Ce qui est en italique est fondamentalement important : si le programme boucle sur certaines données initiales, alors il ne décrit pas l'algorithme. Par souci de simplicité et en application à notre cas, le lecteur peut considérer qu'un algorithme est un programme écrit dans n'importe quel langage de programmation qu'il connaît, qui, pour toute donnée d'entrée d'une classe donnée, est assuré de terminer son travail en produisant un résultat booléen.

Demandons-nous : pour chaque fonction il existe un « algorithme de preuve » (ou, en bref, "déductif"), équivalent à cette fonction, c'est-à-dire transformer chaque instruction en exactement la même valeur booléenne qu'elle ? La même question peut être formulée de manière plus succincte comme suit : est-ce que chaque fonction sur un ensemble d'instructions calculable? Comme vous l'avez déjà deviné, de la validité de TGN, il s'ensuit que non, pas toutes les fonctions - il existe des fonctions incalculables de ce type. En d’autres termes, toutes les affirmations vraies ne peuvent pas être prouvées.

Il est très possible que cette déclaration provoque en vous une protestation interne. Cela est dû à plusieurs circonstances. Premièrement, lorsqu'on nous enseigne les mathématiques à l'école, nous avons parfois la fausse impression que les expressions « le théorème est vrai » et « le théorème peut être prouvé ou vérifié » sont presque totalement identiques. Mais à bien y réfléchir, ce n’est pas du tout évident. Certains théorèmes se prouvent assez simplement (par exemple en essayant un petit nombre d’options), tandis que d’autres sont très difficiles. Prenons par exemple le célèbre théorème du dernier théorème de Fermat :

dont la preuve n'a été trouvée que trois siècles et demi après la première formulation (et elle est loin d'être élémentaire). Il faut faire la distinction entre la véracité d’une affirmation et sa prouvabilité. Il ne ressort de nulle part qu’il n’existe pas de déclarations vraies mais indémontrables (et pas entièrement vérifiables).

Le deuxième argument intuitif contre TGN est plus subtil. Disons que nous avons une affirmation non démontrable (dans le cadre de cette déductive). Qu’est-ce qui nous empêche de l’accepter comme un nouvel axiome ? Ainsi, nous compliquerons un peu notre système de preuves, mais ce n'est pas effrayant. Cet argument serait tout à fait correct s’il existait un nombre fini d’énoncés non démontrables. En pratique, ce qui suit peut arriver : après avoir postulé un nouvel axiome, vous tombez sur un nouvel énoncé non démontrable. Si vous l’acceptez comme un autre axiome, vous tomberez sur le troisième. Et ainsi de suite à l’infini. Ils disent que la déduction restera incomplet. Nous pouvons également forcer l’algorithme de preuve à se terminer en un nombre fini d’étapes avec un résultat pour tout énoncé du langage. Mais en même temps, il commencera à mentir - conduisant à la vérité pour les déclarations incorrectes, ou au mensonge - pour les fidèles. Dans de tels cas, ils disent que la déduction contradictoire. Ainsi, une autre formulation du TGN ressemble à ceci : « Il existe des langages propositionnels pour lesquels une déductibilité complète et cohérente est impossible » - d'où le nom du théorème.

Parfois appelé « théorème de Gödel », l’énoncé est que toute théorie contient des problèmes qui ne peuvent être résolus par la théorie elle-même et nécessitent sa généralisation. Dans un sens, cela est vrai, même si cette formulation tend à obscurcir la question plutôt qu’à la clarifier.

Je noterai également que si nous parlions de fonctions familières qui mappent un ensemble de nombres réels, alors la « non-calculabilité » de la fonction ne surprendrait personne (ne confondez simplement pas « fonctions calculables » et « nombres calculables ». » - ce sont des choses différentes). Tout écolier sait que, par exemple, dans le cas d'une fonction, il faut être très chanceux avec l'argument pour que le processus de calcul de la représentation décimale exacte de la valeur de cette fonction soit complété en un nombre fini d'étapes. Mais très probablement, vous le calculerez à l'aide d'une série infinie, et ce calcul ne conduira jamais à un résultat exact, même s'il peut s'en rapprocher autant que vous le souhaitez - simplement parce que la valeur du sinus de la plupart des arguments est irrationnelle. TGN nous dit simplement que même parmi les fonctions dont les arguments sont des chaînes et dont les valeurs sont zéro ou un, il existe également des fonctions non calculables, bien qu'elles aient une structure complètement différente.

À d’autres fins, nous décrirons le « langage de l’arithmétique formelle ». Considérons une classe de chaînes de texte de longueur finie, constituées de chiffres arabes, de variables (lettres de l'alphabet latin) prenant des valeurs naturelles, d'espaces, de signes arithmétiques, d'égalité et d'inégalité, de quantificateurs (« existe ») et (« pour tout ») et , peut-être , quelques autres symboles (leur nombre exact et leur composition n'ont pas d'importance pour nous). Il est clair que toutes ces lignes n’ont pas de sens (par exemple, « » n’a pas de sens). Le sous-ensemble d’expressions significatives de cette classe (c’est-à-dire les chaînes vraies ou fausses du point de vue de l’arithmétique ordinaire) sera notre ensemble d’instructions.

Exemples d'énoncés arithmétiques formels :

etc. Appelons maintenant une « formule avec un paramètre libre » (FSP) une chaîne qui devient une instruction si un nombre naturel y est substitué comme paramètre. Exemples de FSP (avec paramètre) :

etc. En d’autres termes, les FSP sont équivalents aux fonctions d’arguments naturels avec des valeurs booléennes.

Désignons l'ensemble de tous les FSP par la lettre . Il est clair qu'il peut être ordonné (par exemple, nous écrivons d'abord les formules à une lettre classées par ordre alphabétique, suivies des formules à deux lettres, etc. ; peu importe pour nous dans quel alphabet le classement aura lieu). Ainsi, tout FSP correspond à son numéro dans la liste ordonnée, et nous le noterons .

Passons maintenant à une esquisse de la preuve de TGN dans la formulation suivante :

• Pour le langage propositionnel de l’arithmétique formelle, il n’existe pas de système déductif complet et cohérent.

Nous allons le prouver par contradiction.

Supposons donc qu’un tel système déductif existe. Décrivons l'algorithme auxiliaire suivant, qui attribue une valeur booléenne à un nombre naturel comme suit :

En termes simples, l'algorithme donne la valeur VRAI si et seulement si le résultat de la substitution de son propre numéro dans le FSP dans notre liste donne une fausse déclaration.

Nous arrivons ici au seul endroit où je demanderai au lecteur de me croire sur parole.

Il est évident que, sous l'hypothèse faite ci-dessus, tout FSP peut être comparé à un algorithme contenant un entier naturel en entrée et une valeur booléenne en sortie. L’inverse est moins évident :

La preuve de ce lemme nécessiterait, au minimum, une définition formelle plutôt qu’intuitive du concept d’algorithme. Pourtant, si l’on y réfléchit un peu, c’est tout à fait plausible. En fait, les algorithmes sont écrits dans des langages algorithmiques, parmi lesquels il existe des langages aussi exotiques que, par exemple, Brainfuck, composé de huit mots à un seul caractère, dans lesquels, néanmoins, n'importe quel algorithme peut être implémenté. Il serait étrange que le langage plus riche de formules d'arithmétique formelle que nous avons décrit s'avère plus pauvre - même si, sans aucun doute, il n'est pas très adapté à la programmation ordinaire.

Après avoir dépassé cet endroit glissant, nous arrivons rapidement au bout.

Ainsi, ci-dessus, nous avons décrit l'algorithme. D’après le lemme que je vous ai demandé de croire, il existe un FSP équivalent. Il y a un numéro dans la liste - par exemple, . Demandons-nous, à quoi est égal ? Que ceci soit la VÉRITÉ. Ensuite, selon la construction de l'algorithme (et donc de la fonction qui lui est équivalente), cela signifie que le résultat de la substitution d'un nombre dans la fonction est FAUX. L'inverse se vérifie de la même manière : de FALSE suit TRUE. Nous avons atteint une contradiction, ce qui signifie que l’hypothèse initiale est incorrecte. Ainsi, il n’existe pas de système déductif complet et cohérent pour l’arithmétique formelle. Q.E.D.

Il convient ici de rappeler Epiménide (voir le portrait dans le titre), qui, comme on le sait, déclarait que tous les Crétois sont des menteurs, lui-même étant Crétois. Dans une formulation plus succincte, sa déclaration (connue sous le nom de « paradoxe du menteur ») peut être formulée comme suit : « Je mens ». C’est précisément une telle affirmation, qui elle-même proclame sa fausseté, que nous avons utilisée comme preuve.

En conclusion, je tiens à souligner que TGN ne prétend rien de particulièrement surprenant. En fin de compte, tout le monde est habitué depuis longtemps au fait que tous les nombres ne peuvent pas être représentés comme un rapport de deux nombres entiers (rappelez-vous, cette affirmation a une preuve très élégante qui date de plus de deux mille ans ?). Et tous les nombres ne sont pas non plus des racines de polynômes à coefficients rationnels. Et maintenant, il s’avère que toutes les fonctions d’un argument naturel ne sont pas calculables.

L’esquisse de la preuve donnée concernait l’arithmétique formelle, mais il est facile de voir que TGN est applicable à de nombreux autres langages propositionnels. Bien sûr, toutes les langues ne sont pas ainsi. Par exemple, définissons une langue comme suit :

• "Toute phrase en langue chinoise est une déclaration vraie si elle est contenue dans le recueil de citations du camarade Mao Zedong, et incorrecte si elle n'y figure pas."

L’algorithme de preuve complet et cohérent correspondant (on pourrait l’appeler « dogmatique déductif ») ressemble alors à ceci :

• « Feuilletez le recueil de citations du camarade Mao Zedong jusqu'à ce que vous trouviez le dicton que vous recherchez. Si on le trouve, alors c’est vrai, mais si le recueil de citations est terminé et que la déclaration n’est pas trouvée, alors elle est incorrecte.

Ce qui nous sauve ici, c’est que tout livre de citations est évidemment limité, donc le processus de « preuve » prendra inévitablement fin. Ainsi, TGN n'est pas applicable au langage des déclarations dogmatiques. Mais nous parlions de langages complexes, non ?

Tout système d'axiomes mathématiques, à partir d'un certain niveau de complexité, est soit intérieurement contradictoire, soit incomplet.

En 1900, la Conférence mondiale des mathématiciens s'est tenue à Paris, au cours de laquelle David Hilbert (1862-1943) a présenté sous forme de thèses les 23 problèmes les plus importants, selon lui, que les théoriciens du prochain XXe siècle auraient dû résoudre. Le numéro deux sur sa liste était l’un de ces problèmes simples dont la réponse semble évidente jusqu’à ce qu’on creuse un peu plus. En termes modernes, telle était la question : les mathématiques sont-elles autosuffisantes ? La deuxième tâche de Hilbert se résumait à la nécessité de prouver strictement que le système d'axiomes - les énoncés de base acceptés en mathématiques comme base sans preuve - est parfait et complet, c'est-à-dire qu'il permet de décrire mathématiquement tout ce qui existe. Il était nécessaire de prouver qu'il était possible de définir un système d'axiomes tel qu'ils seraient, d'une part, mutuellement cohérents, et d'autre part, qu'une conclusion pourrait en être tirée quant à la vérité ou à la fausseté de toute affirmation.

Prenons un exemple de géométrie scolaire. En planimétrie euclidienne standard (géométrie sur un plan), il peut être prouvé sans aucun doute que l'affirmation « la somme des angles d'un triangle est de 180° » est vraie, et l'affirmation « la somme des angles d'un triangle est de 137° ». °» est faux. Essentiellement parlant, en géométrie euclidienne, toute affirmation est fausse ou vraie, et il n’existe pas de troisième option. Et au début du XXe siècle, les mathématiciens croyaient naïvement que la même situation devait être observée dans tout système logiquement cohérent.

Et puis, en 1931, un mathématicien viennois à lunettes, Kurt Gödel, a publié un court article qui a tout simplement bouleversé le monde entier de la soi-disant « logique mathématique ». Après de longs et complexes préambules mathématiques et théoriques, il établit littéralement ce qui suit. Prenons n'importe quelle déclaration comme : « L'hypothèse n° 247 dans ce système d'axiomes est logiquement indémontrable » et appelons-la « déclaration A ». Ainsi, Gödel a simplement prouvé la propriété étonnante suivante de tout système d'axiomes :

"Si la déclaration A peut être prouvée, alors la déclaration non-A peut être prouvée."

En d’autres termes, si la véracité de l’affirmation « l’hypothèse 247 est prouvable » peut être prouvée, alors la véracité de l’affirmation « l’hypothèse 247 est prouvable » peut également être prouvée. Autrement dit, pour revenir à la formulation du deuxième problème de Hilbert, si un système d’axiomes est complet (c’est-à-dire que n’importe quelle affirmation qu’il contient peut être prouvée), alors il est contradictoire.

La seule façon de sortir de cette situation est d’accepter un système d’axiomes incomplet. Autrement dit, nous devons accepter le fait que dans le contexte de tout système logique, nous aurons toujours des déclarations de « type A » qui sont évidemment vraies ou fausses - et nous ne pouvons juger de leur vérité qu'en dehors du cadre des axiomatiques dont nous disposons. accepté. S'il n'y a pas de telles déclarations, alors nos axiomatiques sont contradictoires et, dans son cadre, il y aura inévitablement des formulations qui peuvent être à la fois prouvées et réfutées.

Ainsi, la formulation du premier théorème d'incomplétude, ou faible, de Gödel : « Tout système formel d'axiomes contient des hypothèses non résolues. » Mais Gödel ne s’est pas arrêté là, formulant et démontrant le deuxième théorème d’incomplétude de Gödel, ou fort, : « La complétude (ou l’incomplétude) logique de tout système d’axiomes ne peut être prouvée dans le cadre de ce système. Pour le prouver ou le réfuter, des axiomes supplémentaires sont nécessaires (renforcement du système).

Il serait plus prudent de penser que les théorèmes de Gödel sont de nature abstraite et ne nous concernent pas, mais uniquement des domaines de logique mathématique sublime, mais en fait, il s'est avéré qu'ils sont directement liés à la structure du cerveau humain. Le mathématicien et physicien anglais Roger Penrose (né en 1931) a montré que les théorèmes de Gödel peuvent être utilisés pour prouver l'existence de différences fondamentales entre le cerveau humain et un ordinateur. Le sens de son raisonnement est simple. L’ordinateur agit de manière strictement logique et n’est pas capable de déterminer si l’affirmation A est vraie ou fausse si elle va au-delà des axiomatiques, et de telles affirmations, selon le théorème de Gödel, existent inévitablement. Une personne, confrontée à une déclaration A aussi logiquement indémontrable et irréfutable, est toujours capable de déterminer sa vérité ou sa fausseté - sur la base de son expérience quotidienne. En cela au moins, le cerveau humain est supérieur à un ordinateur lié par des circuits logiques purs. Le cerveau humain est capable de comprendre toute la profondeur de la vérité contenue dans les théorèmes de Gödel, mais un cerveau informatique ne le pourra jamais. Le cerveau humain est donc tout sauf un ordinateur. Il est capable de prendre des décisions et réussira le test de Turing.

Je me demande si Hilbert avait la moindre idée jusqu'où ses questions nous mèneraient ?

Kurt GÖDEL
Kurt Gödel, 1906-1978

Mathématicien autrichien puis américain. Né à Brünn (aujourd'hui Brno, République tchèque). Il est diplômé de l'Université de Vienne, où il est resté professeur au département de mathématiques (depuis 1930 - professeur). En 1931, il publia un théorème qui reçut plus tard son nom. Étant une personne purement apolitique, il a vécu une période extrêmement difficile avec le meurtre de son ami et collègue de département par un étudiant nazi et est tombé dans une profonde dépression, dont les rechutes l'ont hanté pour le reste de sa vie. Dans les années 1930, il émigre aux États-Unis, mais retourne dans son Autriche natale et se marie. En 1940, au plus fort de la guerre, il fut contraint de fuir vers l’Amérique en transit par l’URSS et le Japon. Il a travaillé pendant un certain temps au Princeton Institute for Advanced Study. Malheureusement, le psychisme du scientifique n'a pas pu le supporter et il est mort de faim dans une clinique psychiatrique, refusant de manger, car il était convaincu qu'ils allaient l'empoisonner.

Comment se développe un modèle scientifique en sciences naturelles ? L'expérience quotidienne ou scientifique s'accumule, ses jalons sont soigneusement formulés sous forme de postulats et constituent la base du modèle : un ensemble d'énoncés acceptés par tous ceux qui travaillent dans le cadre de ce modèle.

Anatoly Wasserman

En 1930, Kurt Gödel démontra deux théorèmes qui, traduits du langage mathématique dans le langage humain, signifient à peu près ce qui suit : tout système d'axiomes suffisamment riche pour être utilisé pour définir l'arithmétique sera soit incomplet, soit contradictoire. Il ne s'agit pas d'un système complet - cela signifie que dans le système, il est possible de formuler une affirmation qui ne peut être ni prouvée ni réfutée au moyen de ce système. Mais Dieu, par définition, est la cause finale de toutes les causes. Du point de vue des mathématiques, cela signifie que l'introduction de l'axiome sur Dieu complète l'ensemble de notre axiome. Si Dieu existe, alors toute affirmation peut être prouvée ou réfutée, faisant référence, d’une manière ou d’une autre, à Dieu. Mais selon Gödel, le système complet d’axiomes est inévitablement contradictoire. Autrement dit, si nous croyons que Dieu existe, nous sommes alors obligés de conclure que des contradictions sont possibles dans la nature. Et puisqu’il n’y a pas de contradictions, sinon notre monde entier s’effondrerait à cause de ces contradictions, nous devons conclure que l’existence de Dieu est incompatible avec l’existence de la nature.

Sosinsky A.B.

Le théorème de Gödel, avec les découvertes de la relativité, de la mécanique quantique et de l'ADN, est généralement considéré comme la plus grande réussite scientifique du XXe siècle. Pourquoi? Quelle est son essence ? Quelle est sa signification ? Ces questions sont abordées dans sa conférence dans le cadre du projet « Conférences publiques « Polit.ru » » par Alexeï Bronislavovitch Sosinsky, mathématicien, professeur à l'Université indépendante de Moscou, officier de l'Ordre des Palmes académiques de la République française, lauréat de le Prix du gouvernement russe dans le domaine de l'éducation en 2012. En particulier, plusieurs formulations différentes ont été données, trois approches de sa preuve ont été décrites (Kolmogorov, Chaitin et Gödel lui-même) et sa signification pour les mathématiques, la physique, l'informatique et la philosophie a été expliquée.

Ouspenski V.A.

La conférence est consacrée à la version syntaxique du théorème d'incomplétude de Gödel. Gödel lui-même a prouvé la version syntaxique en utilisant une hypothèse plus forte que la cohérence, à savoir la cohérence dite oméga.

Ouspenski V.A.

Conférences à l'école d'été « Mathématiques modernes », Dubna.

J'avoue avoir lu l'idée même d'envisager la question de l'existence de Dieu de ce côté chez Anatoly Alexandrovich Wasserman :
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0 %BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92 %D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8. D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0. B4.D1.8B

Mais j'aimerais développer cette idée et la décrire un peu plus en détail.
Dans la religion (comme dans la non-religion), il existe une certaine axiomatique de la construction. Du moins dans un cas idéal, s’il ne s’agit pas simplement d’une croyance aveugle, mais d’un choix conscient et éclairé. Par exemple, un axiome de la physique peut être considéré comme « la nature peut être connue grâce à la raison et aux conclusions logiques, toutes les lois de la physique sont les mêmes en tout point de l’espace et à tout moment ». Par exemple, l’axiome de la religion peut être considéré comme l’affirmation « Dieu existe et est la cause première de toutes choses ». En d’autres termes, il ne fait aucun doute que tous les nombreux détails et branches peuvent être réduits à plusieurs affirmations importantes et non démontrables, qui sont précisément ces axiomes.

Considérons les croyances religieuses à partir de ces positions. L’axiome religieux le plus important : « Dieu existe et est la cause première de toutes choses ».
Rappelons maintenant l'un des théorèmes mathématiques les plus importants, le théorème de Gödel.
http://elementy.ru/trefil/21142
Théorème de Gödel faible : « Tout système formel d'axiomes contient des hypothèses non résolues » ou « si un système d'axiomes est complet, alors il est incohérent ».
Théorème fort de Gödel : « L'exhaustivité (ou l'incomplétude) logique de tout système d'axiomes ne peut être prouvée dans le cadre de ce système. Pour le prouver ou le réfuter, des axiomes supplémentaires sont nécessaires (renforcement du système).

Rappelons quelques définitions. Un système d'axiomes est complet si un énoncé formulé pour un système d'axiomes donné est prouvable (c'est-à-dire qu'il est vrai ou faux). Une hypothèse non résolue est une affirmation dont ni la vérité ni la fausseté ne peuvent être prouvées, c'est-à-dire que l'affirmation n'est pas logiquement prouvable. Un système d’axiomes est contradictoire si une seule et même affirmation peut s’avérer à la fois vraie et fausse.

Du théorème de Gödel, il s'ensuit que si le concept de Dieu est inclus dans un système axiomatique, alors ce système n'est pas complet, c'est-à-dire qu'il y a des conséquences (phénomènes) qui ne sont pas prouvables, c'est-à-dire qu'elles peuvent ou non exister, ce n'est pas prouvable.
Mais cela contredit les deux dispositions suivantes (choisissez celle qui est la plus convaincante) : la nature ne contient pas de phénomènes qui peuvent être considérés à la fois comme existants et comme inexistants ; tout phénomène naturel existe ou n'existe pas ; La deuxième position dit que, par définition, Dieu est la cause première de tout, donc Dieu conduit soit à l'existence de certaines choses (déclarations), soit à leur non-existence, se référer à Dieu peut prouver ou réfuter n'importe quelle déclaration. Cela contredit le caractère incomplet du système.

Ou bien. Si vous incluez le concept de Dieu dans le système axiomatique et supposez qu'il est complet (toute déclaration dans un système complet d'axiomes est prouvable), alors selon le théorème de Gödel, un tel système d'axiomes sera contradictoire, c'est-à-dire qu'il y aura des phénomènes. dont on peut prouver qu'ils existent tous les deux et qu'ils n'existent pas.

Il ne sert à rien d'inclure Dieu dans un système d'axiomes contradictoires, car il est contradictoire, c'est-à-dire qu'il contient des phénomènes dont il est possible de prouver qu'ils existent et qu'ils n'existent pas, ce qui, comme indiqué, contredit la nature et le concept de Dieu.

Enfin, si le concept de Dieu n'est pas inclus dans le système axiomatique, alors il ne peut pas être considéré comme la base fondamentale de l'univers, dont découle tout ce qui existe, ce qui contredit essentiellement la définition de Dieu.

Pour la validité de cette preuve, il faut reconnaître la validité des lois de la logique mathématique (logique propositionnelle + calcul des prédicats), qui permettent d'établir les lois de conséquence, de vérité, de fausseté, d'incohérence, de cohérence des énoncés et autres propriétés et relations entre les instructions.

Si nous supposons que la logique mathématique n'est pas applicable à l'étude de la question de l'existence de Dieu, alors la conséquence sera qu'il n'est pas possible d'étudier cette question à l'aide du raisonnement, à l'aide de la raison. En d’autres termes, une raison cohérente aboutit toujours à une réponse négative à la question de l’existence de Dieu.

Que se passe-t-il en fin de compte... toute personne, même vaguement rationnelle, reconnaît bien sûr la validité des lois de la logique, ce qui signifie qu'elle arrive invariablement à la conclusion que Dieu dans la définition de « la cause de toutes choses » n'existe pas. . Une personne non rationnelle qui prétend que Dieu ne peut être connu qu'à travers les sentiments (et non la raison), bien sûr, peut le dire, mais il n'y a aucun moyen de convaincre autrui que les sentiments ne peuvent pas être transmis. De plus, le concept de Dieu est un concept formulé par la raison. Comment il est proposé de traduire le concept de raison en sensation, et même de telle manière qu'il puisse être transmis à une autre personne, n'est pas clair. Encore une fois, même une personne quelque peu rationnelle dira que ce n'est pas possible : traduire le concept abstrait de la raison en le ressentir et le ressentir.

Enfin, il existe une autre option : « Dieu n’est pas la cause première de tout ». De telles contradictions ne surviennent alors pas, cependant, il s'agit d'un affaiblissement significatif de la position de la religion, puisque c'est précisément le fait que Dieu a tout créé, que Dieu est le commencement de tous les principes, qui est le fondement de nombreuses déclarations de religion et justifications dans les litiges.

P.S. Il convient de noter une autre chose curieuse et intéressante pour les physiciens. Cette définition de Dieu ne dit rien de sa rationalité. Autrement dit, on pourrait ajouter « Dieu est la cause rationnelle de toutes choses », mais il s’agit là d’un rétrécissement de la définition, qui n’est pas initialement requis pour la preuve. Sans rationalité, le concept de « Dieu » peut facilement être remplacé par « la singularité et le big bang sont la cause de toutes choses ». Et la réponse sera la même : la singularité et le big bang ne sont pas la cause profonde de tout ce qui existe.
En effectuant une abstraction encore plus grande, nous pouvons dire qu'aucun phénomène ou aucune cause ne peut être la cause profonde de toutes choses, c'est-à-dire que la cause profonde n'existe pas en principe. En raisonnant dans le cadre de n'importe quelle axiomatique, on peut arriver à la conclusion que la cause profonde de tout n'existe pas. Pour le dire très simplement, quelle que soit la profondeur avec laquelle nous comprenons l’univers, les questions resteront toujours dans l’esprit de : « d’où vient le big bang, d’où vient la singularité, d’où vient l’univers palpitant, d’où vient l’univers ? d’où vient le multivers, pourquoi l’univers existe-t-il toujours ? etc. La cause profonde de tout ne peut en principe être trouvée ; elle n’est contenue dans aucun objet, phénomène ou concept. Par conséquent, pour une personne, cela équivaut à son absence. Théoriquement, on peut supposer l'existence d'un observateur extérieur à l'extérieur de notre univers, qui répondra à la question de savoir d'où vient tout (ce même axiome supplémentaire, une extension du théorème de Gödel), mais alors se posera la question de savoir d'où vient l'observateur extérieur, son l'univers et la cause profonde de tout cela vient.

L'idée de la preuve est de construire une expression qui indiquerait son

propre non-démontrabilité. Cette construction peut se faire en trois étapes :

La première étape est l'établissement d'une correspondance entre l'arithmétique formelle et l'ensemble des entiers (Goedelisation) ;

La deuxième étape est la construction d'une propriété spéciale dont on ne sait pas s'il s'agit d'un théorème d'arithmétique formelle ou non ;

La troisième étape est la substitution à la place de x d'un certain entier associé à lui-même, c'est-à-dire le remplacement de tous par ces nombres

Première étape. Gédélisation de l'arithmétique formelle

L'arithmétique formelle peut être arithmétique (c'est-à-dire godelisée) de la manière suivante : chacun de ses théorèmes est associé à un certain nombre. Cependant, puisque tout nombre est aussi un théorème, alors tout théorème peut être considéré, d'une part, comme un théorème de l'arithmétique formelle, et d'autre part, comme un théorème sur l'ensemble des théorèmes de l'arithmétique formelle, c'est-à-dire comme un théorème sur l'ensemble des théorèmes de l'arithmétique formelle. métathéorème correspondant à la preuve d'un certain théorème.

Ainsi, nous pouvons conclure que le système d'arithmétique formelle contient également son propre métasystème.

Nous allons maintenant présenter les résultats obtenus plus spécifiquement et en détail.

Premièrement, nous pouvons associer à chaque symbole et arithmétique formelle une désignation de code spéciale, appelée dans ce cas le nombre de Gödel.

Deuxièmement, nous associons chaque séquence de symboles au même nombre de Gödel en utilisant une fonction de composition. Soit où représente les séquences de symboles qui se forment.

Troisièmement (et c'est essentiel), à chaque preuve d'une séquence d'axiomes et de règles de substitution (ou règles de substitution) est associé un nombre où désigne la séquence de théorèmes utilisée dans la preuve

Ainsi, chaque preuve en arithmétique formelle correspond à un certain nombre – son nombre de Gödel. Tout raisonnement en arithmétique formelle se transforme en calculs sur l'ensemble des nombres naturels.

Ainsi, au lieu de manipuler des symboles, des théorèmes et des preuves, vous pouvez utiliser

calculs sur un ensemble d’entiers. Toute expression comme par exemple la suivante : « prouvable en arithmétique formelle » correspond désormais à un certain nombre, que nous désignerons par

Formulons la position suivante.

La métaarithmétique formelle est contenue dans l'ensemble des nombres naturels, lui-même contenu dans l'interprétation de l'arithmétique formelle.

Cette situation de l'arithmétique formelle n'est pas sans rappeler celle du langage naturel : après tout, rien ne nous empêche de l'utiliser pour y formuler ses concepts et règles de base.

Le bon choix de fonction permet une transition sans ambiguïté de A à, c'est-à-dire l'attribution de deux nombres différents à deux preuves différentes. Par exemple, on peut choisir les nombres de Gödel de telle sorte que chaque symbole de l'alphabet de l'arithmétique formelle corresponde à son propre nombre premier, comme le montre par exemple le tableau. 3.2.

Tableau 3.2

Chaque formule (constituée de symboles variant de 1 à est à son tour codée par une séquence constituée des premiers nombres premiers, soit le nombre

où est un nombre premier.

À son tour, la preuve, c'est-à-dire la séquence de formules, sera codée de la même manière avec le nombre

Et vice versa, grâce à cette méthode de construction des nombres, il devient possible, à partir d'un certain nombre, grâce à sa décomposition en facteurs premiers (en raison du caractère unique de la décomposition des nombres naturels en produits de puissances de nombres premiers), de rendre en deux étapes aux exposants, c'est-à-dire aux symboles primitifs de l'arithmétique formelle. Bien entendu, cela n’est que théorique, car les chiffres deviennent vite trop élevés.

afin qu'ils puissent être manipulés. Il convient toutefois de noter que la possibilité fondamentale de cette opération est essentielle.

Exemple. Soit un nombre T, correspondant à une preuve et représentant un produit de nombres premiers :

Ce développement signifie que la preuve du théorème contient deux étapes : l'une correspondant au nombre 1981027125 253, et l'autre au nombre 1981027125 211. En factorisant à nouveau chacun de ces nombres en facteurs premiers, on obtient

À partir de la table de codage alphabétique de l'arithmétique formelle (tableau 3.2), nous constatons que nos nombres de Gödel pour ces deux nombres

correspondra la preuve suivante :

De la formule découle la formule

Ainsi, en métaarithmétique, la valeur du nombre original est obtenue à partir de l'arithmétique formelle.

Deuxième étape. Lemme de Gödel

Chaque nombre T associé à une preuve correspond à un théorème prouvable en arithmétique formelle. L'arithmétique formelle « goedélisée » est appelée arithmétique formelle arithmétique. Puisque chaque axiome et chaque règle de l'arithmétique formelle arithmétique correspond à une opération arithmétique, alors à l'aide d'un test systématique, il est possible de déterminer si un nombre donné T correspond à la preuve d'un théorème de nombres T et dans ce cas former une paire de conjugués. Nombres. L'expression et sont conjugués » Présentables au sein de l'arithmétique formelle arithmétique elle-même. Cela signifie qu'il existe un numéro de Gödel qui exprime numériquement cette déclaration.

Nous avons atteint le point critique de la preuve de Gödel. Soit A une expression de l’arithmétique formelle arithmétique qui contient une variable libre. Au lieu de cela, vous pouvez remplacer un terme. En particulier, vous pouvez remplacer l'expression A par l'expression A elle-même. Dans ce cas, l'expression numérique A remplit simultanément deux rôles différents (voir la construction ci-dessus).

Cantor et Richard) : c'est à la fois une véritable expression de substitution et un terme résultant. Nous désignerons cette substitution spéciale par Donc la formule signifie que le nombre est le nombre de Gödel obtenu en effectuant la substitution - à l'expression A :

Gödel construit alors une expression (dont on ne sait pas s'il s'agit d'un théorème ou d'un non-théorème) dans laquelle il introduit cette substitution. L'expression ressemble à ceci :

Troisième étape. Remplacement final

En arithmétique formelle arithmétique, cette expression est représentée sous forme numérique. Soit E son nombre de Gödel. Puisque l'expression contient une variable libre, on a le droit d'effectuer une substitution - en remplaçant le nombre E et désignant - la substitution E :

Notons cette seconde expression par a et son nombre de Gödel par E. Donnons des interprétations de l'expression e.

Première interprétation. Il n'existe pas de telle paire pour laquelle ce qui suit serait simultanément valable : d'une part, T est le nombre de la preuve arithmétique du théorème arithmétisé par lui-même, et d'autre part, il y aurait une substitution Mais puisqu'il y a le. même transformation que les autres, il est représentable en termes et dans leurs désignations codées - nombres de Gödel et, par conséquent, un tel nombre existe. Alors peut-être que le numéro T n'existe pas.

Deuxième interprétation. Il n'existe pas de preuve arithmétique du théorème T qui serait un -remplacement de E. Donc, s'il n'y a pas de preuve, c'est parce qu'il n'est pas en soi un théorème. Cela nous amène à la troisième interprétation.

Troisième interprétation. Une expression pour laquelle le nombre de Gödel est -substitution E n'est pas un théorème d'arithmétique formelle arithmétique. Mais c'est là que réside la contradiction, puisque par construction il s'agit précisément du -remplacement de E et que le nombre n'est, par construction, rien d'autre que le nombre E lui-même. De là découle l'interprétation finale de e.