domicile » Auto / Moto » L'essence du théorème de Gödel. Confession d'un grand logicien

L'essence du théorème de Gödel. Confession d'un grand logicien

Je m'intéresse depuis longtemps à ce qu'est le sensationnel théorème de Gödel. Et comment il est utile pour la vie. Et finalement j'ai pu comprendre.

La formulation la plus populaire du théorème est :
"Tout système d'axiomes mathématiques, à partir d'un certain niveau de complexité, est soit incohérent en interne, soit incomplet."

Je le traduirais dans un langage humain non mathématique comme celui-ci (un axiome est la position initiale d'une théorie, acceptée dans le cadre de cette théorie comme vraie sans exiger de preuve et utilisée comme base pour prouver ses autres dispositions). Dans la vie, un axiome est les principes suivis par une personne, une société, une direction scientifique, des états. Parmi les représentants de la religion, les axiomes sont appelés dogmes. Par conséquent, n'importe lequel de nos principes, n'importe quel système de vues, à partir d'un certain niveau, devient intérieurement contradictoire, ou incomplet. Afin d'être convaincu de la véracité d'une certaine affirmation, il faudra aller au-delà du système de vues donné et en construire un nouveau. Mais ce sera aussi imparfait. Autrement dit, le PROCESSUS DE CONNAISSANCE EST INFINI. Le monde ne peut pas être pleinement connu tant que nous n'avons pas atteint la source.

"... si nous considérons la capacité de raisonner logiquement comme la principale caractéristique de l'esprit humain, ou du moins son principal outil, alors le théorème de Gödel indique directement les capacités limitées de notre cerveau. Convenez qu'il est très difficile pour une personne amenée sur la foi dans le pouvoir infini de la pensée pour accepter la thèse sur les limites de son pouvoir ... De nombreux experts pensent que les processus formels-computationnels "aristotéliciens" sous-jacents pensée logique ne sont qu'une partie de la conscience humaine. Son autre domaine, fondamentalement "non informatique", est responsable de manifestations telles que l'intuition, les idées créatives et la compréhension. Et si la première moitié de l'esprit tombe sous les restrictions de Gödel, alors la seconde moitié est exempte de telles limites ... Le physicien Roger Penrose est allé encore plus loin. Il a suggéré l'existence de certains effets quantiques non computationnels qui assurent la mise en œuvre d'actes créatifs de conscience... L'une des nombreuses conséquences de l'hypothèse de Penrose peut être, en particulier, la conclusion qu'il est fondamentalement impossible de créer une intelligence artificielle basée sur sur les appareils informatiques modernes, même si l'émergence des ordinateurs quantiques conduira à une grande percée dans le domaine l'informatique. Le fait est que n'importe quel ordinateur ne peut que modéliser de plus en plus précisément le travail de l'activité "informatique" formelle-logique de la conscience humaine, mais les capacités "non informatiques" de l'intellect lui sont inaccessibles.

Une conséquence importante du théorème de Gödel est la conclusion qu'on ne peut pas penser aux extrêmes. Toujours dans le cadre de la théorie existante, il y aura une déclaration qui ne peut être ni prouvée ni réfutée. Ou, en d'autres termes, à une affirmation il y a toujours une paire qui la réfute.

Conclusion suivante. Le bien et le mal ne sont que les 2 faces d'une même médaille, sans laquelle il ne peut exister. Et cela vient du principe que dans l'univers il n'y a qu'une seule source de tout : le bien et le mal, l'amour et la haine, la vie et la mort.

Toute déclaration d'exhaustivité du système est fausse. Vous ne pouvez pas vous fier aux dogmes, car tôt ou tard ils seront réfutés.

Dans ce sens, religions modernes sont dans une position critique : les dogmes de l'Église s'opposent au développement de nos idées sur le monde. Ils essaient de tout serrer dans le cadre de concepts rigides. Mais cela conduit au fait que du monothéisme, d'une source unique de tous les processus naturels, ils passent au paganisme, où il y a des forces du bien et des forces du mal, il y a un dieu du bien quelque part très loin dans le ciel, et il y a un diable (le dieu du mal), qui a longtemps posé la patte sur tout ce qui est sur Terre. Cette approche conduit à la division de toutes les personnes en amis et ennemis, justes et pécheurs, croyants et hérétiques, amis et ennemis.

Voici un autre petit texte qui révèle populairement l'essence qui découle du théorème de Gödel :
« Il me semble que ce théorème porte une importance sens philosophique. Seules deux options sont possibles :

a) La théorie est incomplète, c'est-à-dire en termes de théorie, on peut formuler une question à laquelle il est impossible de tirer une réponse positive ou négative des axiomes/postulats de la théorie. Dans le même temps, des réponses à toutes ces questions peuvent être données dans le cadre d'une théorie plus complète, dans laquelle l'ancienne sera un cas particulier. Mais cette nouvelle théorie aura ses propres "questions sans réponse" à l'infini.

b) Complète, mais contradictoire. Il est possible de répondre à toutes les questions, mais certaines questions peuvent être répondues par oui et par non en même temps.

Les théories scientifiques sont du premier type. Ils sont cohérents, mais cela signifie qu'ils ne décrivent pas tout. Il ne peut y avoir de "finale" théorie scientifique. Toute théorie est incomplète et ne décrit pas quelque chose, même si nous ne savons pas encore ce que c'est. On ne peut que créer des théories de plus en plus complètes. Pour moi personnellement, c'est une raison d'être optimiste, car cela signifie que le progrès de la science ne s'arrêtera jamais.

« Dieu tout-puissant » appartient au deuxième type. Dieu Tout-Puissant est la réponse à toutes les questions. Et cela signifie automatiquement que cela mène à l'absurdité logique. Des paradoxes comme la "pierre lourde" peuvent être inventés par lots.

En général, les connaissances scientifiques sont vraies (cohérentes), mais à un moment donné ne décrivent pas tout. En même temps, rien n'empêche de repousser les frontières du connu à l'infini, de plus en plus loin et tôt ou tard tout inconnu devient connu. La religion, d'autre part, prétend être une description complète du monde "en ce moment", mais en même temps, elle est automatiquement incorrecte (absurde)."

A une époque, alors que je commençais tout juste mon l'âge adulte Je programmais. Et il y avait un tel principe: si de nombreuses corrections sont apportées au programme, il doit être réécrit à nouveau. Ce principe, à mon avis, correspond au théorème de Godel. Si le programme devient plus complexe, il devient incohérent. Et cela ne fonctionnera pas correctement.

Un autre exemple tiré de la vie. Nous vivons à une époque où les responsables disent que le principe fondamental de l'existence devrait être la loi. C'est-à-dire le système juridique. Mais dès que la législation devient plus complexe et que l'élaboration de règles se développe, les lois commencent à se contredire. Ce que nous voyons maintenant. Vous ne pouvez jamais créer un système juridique qui prescrirait tous les aspects de la vie. D'un autre côté, ce serait juste pour tout le monde. Parce que les limites de notre compréhension du monde ressortiront toujours. Et les lois humaines commenceront à un moment donné à entrer en conflit avec les lois de l'univers. Nous comprenons beaucoup de choses intuitivement. Intuitivement aussi, nous devons juger les actions des autres. Il suffit que l'État ait une constitution. Et en s'appuyant sur les articles de cette constitution, pour réguler les rapports dans la société. Mais tôt ou tard, la constitution devra être changée.

L'USE est un autre exemple de l'erreur de nos idées sur les capacités humaines. Nous essayons de tester les capacités de calcul du cerveau lors d'un examen. Mais les capacités intuitives à l'école ont cessé d'être développées. Mais l'homme n'est pas un biorobot. Il est impossible de créer un système de notation qui serait capable de révéler toutes les possibilités inhérentes à une personne, à sa conscience, à son subconscient et à sa psyché.

Il y a près de 100 ans, Gödel a franchi une étape incroyable dans la compréhension des lois de l'univers. Et nous n'avons toujours pas pu l'utiliser, considérant ce théorème comme un problème mathématique hautement spécialisé pour un cercle restreint de personnes traitant de certains sujets abstraits dans leur entourage. Ensemble avec théorie des quanta et les enseignements du Christ, le théorème de Gödel nous permet d'échapper à la captivité des faux dogmes, de surmonter la crise qui persiste encore dans notre vision du monde. Et le temps presse.

Théorème d'incomplétude de Godel

Ouspensky V.A.

Peut-être que le théorème d'incomplétude de Gödel est vraiment unique. Unique en ce sens qu'ils s'y réfèrent lorsqu'ils veulent prouver "tout dans le monde" - de la présence des dieux à l'absence de raison. Je me suis toujours intéressé à une "question plus primaire" - et qui parmi ceux qui se réfèrent au théorème d'incomplétude pourrait non seulement le formuler, mais aussi le prouver ? Je poste Cet article pour la raison qu'il présente une formulation très accessible du théorème de Gödel. Je vous recommande de lire d'abord l'article de Tullio Regge Kurt Gödel et son célèbre théorème

La conclusion sur l'impossibilité d'un critère universel de vérité est une conséquence directe du résultat obtenu par Tarski en combinant le théorème d'indécidabilité de Godel avec sa propre théorie de la vérité, selon laquelle il ne peut y avoir de critère universel de vérité même pour un domaine relativement étroit de la théorie des nombres, et donc pour toute science utilisant l'arithmétique. Naturellement, ce résultat s'applique a fortiori au concept de vérité dans tout domaine de connaissance non mathématique dans lequel l'arithmétique est largement utilisée.

Karl Popper

Uspensky Vladimir Andreevich est né le 27 novembre 1930 à Moscou. Diplômé de la Faculté de mécanique et de mathématiques de l'Université d'État de Moscou (1952). Docteur en sciences physiques et mathématiques (1964). Professeur, chef du département de logique mathématique et théorie des algorithmes de la faculté de mécanique et de mathématiques (1966). Lit les cours du cours "Introduction à la logique mathématique", "Fonctions calculables", "Théorème de complétude de Gödel". Préparation de 25 candidats et 2 docteurs en sciences

1. Énoncé du problème

Le théorème d'incomplétude, dont nous donnerons la formulation exacte à la fin de ce chapitre, et peut-être plus tard (si cela intéresse le lecteur) et la démonstration, énonce approximativement ceci : quand certaines conditions dans n'importe quelle langue, il y a des déclarations vraies mais indémontrables.

Lorsque nous formulons un théorème de cette manière, presque chaque mot nécessite une explication. Par conséquent, nous commencerons par expliquer le sens des mots que nous utilisons dans cette formulation.

1.1. Langue

Nous ne donnerons pas la définition la plus générale possible d'un langage, préférant nous limiter aux concepts de langage dont nous aurons besoin plus tard. Il existe deux concepts de ce type : "l'alphabet de la langue" et "l'ensemble des énoncés vrais de la langue".

1.1.1. Alphabet

Par alphabet, nous entendons un ensemble fini de signes élémentaires (c'est-à-dire des choses qui ne peuvent pas être décomposées en éléments constitutifs). Ces caractères sont appelés lettres de l'alphabet. Par mot d'un alphabet, nous entendons une suite finie de lettres. Par exemple, les mots ordinaires en anglais (y compris les noms propres) sont des mots de l'alphabet à 54 lettres (26 lettres minuscules, 26 lettres majuscules, un tiret et une apostrophe). Un autre exemple - entiers en notation décimale sont des mots de l'alphabet à 10 lettres, dont les lettres sont des signes : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Nous utiliserons des majuscules ordinaires pour désigner les alphabets. Si L est un alphabet, alors L ? désignera l'ensemble de tous les mots de l'alphabet L, - mots formés à partir de ses lettres. Nous supposerons que toute langue a son propre alphabet, de sorte que toutes les expressions de cette langue (c'est-à-dire - les noms de divers objets, les déclarations sur ces objets, etc.) sont des mots de cet alphabet. Par exemple, toute proposition de la langue anglaise, ainsi que tout texte écrit en anglais, peut être considéré comme un mot de l'alphabet étendu de 54 lettres, qui comprend également des signes de ponctuation, un espace entre les mots, un signe de ligne rouge et éventuellement d'autres caractères utiles. En supposant que les expressions du langage sont des mots d'un certain alphabet, nous excluons donc de la considération les expressions "multicouches" comme ???f(x)dx. Cependant, cette limitation n'est pas trop importante, puisque toute expression de ce type, en utilisant des conventions appropriées, peut être "étirée" sous une forme linéaire. Tout ensemble M contenu dans L ? est appelé un ensemble de mots de l'alphabet L. Si nous disons simplement que M est un ensemble de mots, alors nous voulons dire que c'est un mot d'un alphabet. Maintenant, l'hypothèse linguistique ci-dessus peut être reformulée comme suit : dans n'importe quelle langue, tout ensemble d'expressions est un ensemble de mots.

1.1.2. Beaucoup de vraies revendications

On suppose qu'on nous donne un sous-ensemble T de l'ensemble L? (où L est l'alphabet d'une langue que nous considérons), qui est appelé l'ensemble des "énoncés vrais" (ou simplement des "vérités"). Passant directement au sous-ensemble T, nous omettons les étapes intermédiaires de raisonnement suivantes : premièrement, quels mots de l'alphabet L sont des expressions bien formées de la langue, c'est-à-dire qu'ils ont un certain sens dans notre interprétation de cette langue (par exemple , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 sont des expressions bien formées, alors que des expressions comme +=x ne le sont pas) ; deuxièmement, quelles expressions sont des formules, c'est-à-dire peut dépendre d'un paramètre (par exemple, x=3, x=y, 2=3, 2=2) ; troisièmement, lesquelles des formules sont des formules fermées, c'est-à-dire des instructions qui ne dépendent pas de paramètres (par exemple, 2=3, 2=2) ; et enfin, quelles formules fermées sont des déclarations vraies (par exemple, 2=2).

1.1.3. Paire de langues fondamentales

1.2. "Improuvable"

"Improuvable" signifie n'avoir aucune preuve.

1.3. Preuve

Malgré le fait que le terme "preuve" est peut-être l'un des plus importants en mathématiques (les Bourbaki commencent leur livre "Fundamentals of Mathematics" par les mots : "Depuis l'époque des anciens Grecs, dire "mathématiques" signifiait la même chose que disant "preuve""), il n'a pas de définition précise. En général, le concept de preuve avec toutes ses branches sémantiques appartient plutôt au domaine de la psychologie qu'aux mathématiques. Quoi qu'il en soit, la preuve n'est qu'un argument que nous trouvons nous-mêmes assez convaincant pour convaincre tout le monde.

Une fois écrite, la preuve devient un mot dans un alphabet P, tout comme n'importe quel texte anglais est un mot dans l'alphabet L, dont un exemple a été donné ci-dessus. L'ensemble de toutes les preuves forme un sous-ensemble (et un assez grand sous-ensemble) de l'ensemble P?. Nous n'essaierons pas de donner une définition précise de ce concept à la fois "naïf" et "absolu" de la preuve, ni - ce qui est équivalent - de définir le sous-ensemble correspondant de P?. Au lieu de cela, nous considérerons un analogue formel de ce concept vague, pour lequel nous utiliserons encore le terme "preuve" dans ce qui suit. Cet analogue a deux caractéristiques très importantes qui le distinguent du concept intuitif (bien que l'idée intuitive de la preuve reflète toujours ces caractéristiques dans une certaine mesure). Tout d'abord, nous supposons qu'il existe différents concepts de preuve, c'est-à-dire que différents sous-ensembles de preuves dans P? sont autorisés, et même plus que cela : nous supposerons en fait que l'alphabet des preuves de P lui-même peut changer . Dans ce qui suit, nous exigeons que pour chacune de ces conceptions de preuve il existe méthode efficace, autrement dit, un algorithme qui déterminerait nécessairement si un mot donné de l'alphabet P est une preuve ou non. Nous supposons également qu'il existe un algorithme qui peut toujours être utilisé pour déterminer quelle déclaration une preuve donnée prouve. (Dans de nombreuses situations, la déclaration en cours de preuve est simplement la dernière déclaration dans la séquence d'étapes qui forment la preuve.)

Ainsi, notre formulation finale de la définition est la suivante :

(1) Nous avons l'alphabet L (l'alphabet de la langue) et l'alphabet P (l'alphabet de la preuve).

(2) On nous donne un ensemble P qui est un sous-ensemble de P? et dont les éléments sont appelés "preuves". À l'avenir, nous supposerons que nous avons également un algorithme qui nous permet de déterminer si un mot arbitraire de l'alphabet P est un élément de l'ensemble P, c'est-à-dire une preuve, ou non.

(3) Nous avons aussi une fonction ? (pour trouver ce qui a été prouvé exactement), à qui appartient le domaine ? satisfait la condition P???P?, et dont la plage est dans P?. Nous supposons que nous avons un algorithme qui calcule cette fonction ( valeur exacte mots "algorithme calcule une fonction" ce qui suit: les valeurs de la fonction sont obtenues à l'aide de cet algorithme - un ensemble de règles de transformation spéciales). On dira que l'élément p? P est une preuve du mot ?(p) de l'alphabet L.

Troïka<Р, Р, ?>, satisfaisant aux conditions (1)-(3) est appelé un système déductif sur l'alphabet L.

Pour le lecteur familier avec la manière habituelle de définir la "preuve" en termes d'"axiome" et de "règle d'inférence", nous allons maintenant expliquer comment cette méthode peut être considérée comme occasion spéciale la définition donnée au paragraphe 1.3.2. C'est-à-dire qu'une preuve est généralement définie comme une séquence de telles expressions de langage, dont chacune est soit un axiome, soit obtenue précédemment à partir d'énoncés déjà existants en utilisant l'une des règles d'inférence. Si nous ajoutons un nouveau mot * à l'alphabet de notre langue, alors nous pouvons écrire une telle preuve comme un mot composé à l'aide de l'alphabet résultant : la séquence d'expressions devient le mot C1*C2*...*Cn. Dans ce cas, la fonction qui détermine exactement ce qui a été prouvé a sa valeur dans la partie de ce mot qui suit immédiatement la dernière lettre * de la séquence. L'algorithme dont l'existence est requise dans la section 1.3.2. définitions, peuvent facilement être construites une fois que nous avons défini avec précision l'une des significations acceptées des mots « axiome » et « règle d'inférence ».

1.4 Tentatives de formulation précise du théorème d'incomplétude

1.4.1. Premier essai

« Sous certaines conditions pour le couple fondamental de la langue de l'alphabet L et du système déductif<Р, Р, ?>sur L, il existe toujours un mot dans T qui n'a pas de preuve. Cette option semble encore vague. En particulier, nous pourrions facilement trouver autant de systèmes déductifs que nous voulons qui ont très peu de mots démontrables. ?) il n'y a pas de mots du tout qui aurait des preuves.

1.4.2. Deuxième essai

Il existe une autre approche, plus naturelle. Supposons qu'on nous donne un langage - au sens où on nous donne un couple fondamental de ce langage. Nous allons maintenant chercher un tel système déductif sur L (intuitivement, nous cherchons une technique de preuve) avec lequel nous pourrions prouver autant de mots de T que possible, à la limite tous les mots du théorème de T. Gödel décrivent la situation dans laquelle un tel système déductif (par lequel chaque mot de T serait démontrable) n'existe pas. Ainsi, nous voudrions formuler la déclaration suivante :

"Sous certaines conditions concernant la paire fondamentale, il n'existe pas de tel système déductif dans lequel chaque mot de T aurait une preuve."

Or, une telle affirmation est évidemment fausse, puisqu'il suffit de prendre un système déductif dans lequel P = L, P = P ? et ?(p) = p pour tout p dans P ? ; puis chaque mot de L? est trivialement démontrable. Par conséquent, nous devons accepter certaines limitations sur les systèmes déductifs que nous utilisons.

1.5. Cohérence

Il serait tout à fait naturel d'exiger que seuls les "énoncés vrais", c'est-à-dire que seuls les mots de T, puissent être prouvés. Nous dirons que le système déductif<Р, Р, ?>est cohérente par rapport à un couple fondamental si?(P)?T. Dans tous les raisonnements ultérieurs, nous ne nous intéresserons qu'à de tels systèmes déductifs cohérents. Si on nous donne un langage, alors il serait extrêmement tentant de trouver un tel système déductif cohérent dans lequel chaque énoncé vrai aurait une preuve. La variante du théorème de Gödel qui nous intéresse précise que sous certaines conditions par rapport au couple fondamental, il est impossible de trouver un tel système déductif.

1.6. complétude

On dit que le système déductif<Р,Р,?>est complet par rapport au couple fondamental, pourvu que ?(P) ?T. Alors notre formulation du théorème d'incomplétude prend la forme suivante :

Sous certaines conditions concernant la paire fondamentale, il n'y a pas de tel système déductif<Р,Р,?>sur L qui serait à la fois complet et relativement cohérent.

Bibliographie

Pour la préparation de ce travail, des matériaux du site http://filosof.historic.ru ont été utilisés.

dont la preuve n'a été trouvée que trois siècles et demi après la première formulation (et c'est loin d'être élémentaire). Il faut faire la distinction entre la vérité d'un énoncé et sa prouvabilité. Il ne s'ensuit nulle part qu'il n'y a pas de déclarations vraies, mais non prouvables (et non entièrement vérifiables).

Le deuxième argument intuitif contre TGN est plus subtil. Supposons que nous ayons une affirmation non démontrable (dans le cadre de cette déduction). Qu'est-ce qui nous empêche de l'accepter comme un nouvel axiome ? Ainsi, nous allons légèrement compliquer notre système de preuves, mais ce n'est pas terrible. Cet argument serait parfaitement correct s'il existait un nombre fini de propositions indémontrables. En pratique, ce qui suit peut se produire - après avoir postulé un nouvel axiome, vous tomberez sur une nouvelle déclaration indémontrable. Prenez-le comme un autre axiome - vous tomberez sur le troisième. Et ainsi de suite à l'infini. Ils disent que deductica restera incomplet. Nous pouvons également prendre des mesures énergiques pour que l'algorithme de preuve se termine après un nombre fini d'étapes avec un résultat pour toute déclaration du langage. Mais en même temps, il commencera à mentir - conduire à la vérité pour des déclarations incorrectes, ou à des mensonges - pour les fidèles. Dans de tels cas, on dit que le déductif contradictoire. Ainsi, une autre formulation de TGN ressemble à ceci: "Il existe des langages propositionnels pour lesquels une déductibilité cohérente complète est impossible" - d'où le nom du théorème.

Parfois appelé « théorème de Gödel » est l'affirmation selon laquelle toute théorie contient des problèmes qui ne peuvent être résolus dans le cadre de la théorie elle-même et nécessitent sa généralisation. En un sens, cela est vrai, bien qu'une telle formulation obscurcisse la question plutôt qu'elle ne la clarifie.

Je note également que si nous parlions des fonctions habituelles qui y mappent l'ensemble des nombres réels, alors la "non-calculabilité" de la fonction ne surprendrait personne (ne confondez pas "fonctions calculables" et "nombres calculables" - ce sont des choses différentes). Tout écolier sait que, par exemple, dans le cas d'une fonction, vous devez ê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 se termine par un nombre fini d'étapes. Et très probablement, vous le calculerez en utilisant une série infinie, et ce calcul ne conduira jamais à un résultat exact, bien qu'il puisse s'en approcher 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, des fonctions non calculables, bien qu'arrangées de manière complètement différente, existent également.

Pour ce qui suit, nous décrirons le "langage de l'arithmétique formelle". Considérons une classe de chaînes de texte de longueur finie, composée de chiffres arabes, de variables (lettres de l'alphabet latin), prenant valeurs naturelles, espaces, signes d'opérations arithmétiques, égalité et inégalité, quantificateurs ("existe") et ("pour tout") et, peut-être, quelques autres caractères (leur nombre exact et leur composition ne sont pas importants pour nous). Il est clair que toutes ces lignes ne sont pas significatives (par exemple, "" est un non-sens). Le sous-ensemble d'expressions significatives de cette classe (c'est-à-dire les chaînes qui sont vraies ou fausses en termes d'arithmétique ordinaire) sera notre ensemble d'instructions.

Exemples d'instructions arithmétiques formelles :

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é en tant que paramètre. Exemples de FSP (avec paramètre) :

etc. En d'autres termes, les FSP sont équivalentes aux fonctions d'un argument naturel avec une valeur booléenne.

Dénotez l'ensemble de tous les PSF par la lettre . Il est clair qu'il peut être ordonné (par exemple, nous écrivons d'abord des formules à une lettre classées par ordre alphabétique, suivies de formules à deux lettres, etc.; selon quel alphabet l'ordre aura lieu n'est pas fondamental pour nous). 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'y a pas de déduction cohérente complète.

Nous allons prouver par contradiction.

Supposons donc qu'un tel 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 TRUE si et seulement si le résultat de la substitution dans le FSP de son propre numéro dans notre liste donne une fausse déclaration.

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

Évidemment, sous l'hypothèse ci-dessus, tout FSP de peut être associé à un algorithme contenant un nombre naturel en entrée et une valeur booléenne en sortie. Le contraire est moins évident :

La démonstration de ce lemme nécessiterait au moins une définition formelle, et non intuitive, de la notion d'algorithme. Cependant, si vous y réfléchissez un peu, c'est tout à fait plausible. En effet, les algorithmes sont écrits dans des langages algorithmiques, parmi lesquels il y en a des exotiques comme, par exemple, Brainfuck , qui se compose de huit mots d'un caractère, dans lesquels, néanmoins, n'importe quel algorithme peut être implémenté. Il serait étrange que le langage plus riche de formules arithmétiques formelles que nous avons décrit se révèle plus pauvre - même si, sans aucun doute, il n'est pas très adapté à la programmation ordinaire.

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

Nous avons donc décrit l'algorithme ci-dessus. D'après le lemme que je vous ai demandé de croire, il existe un FSP équivalent. Il a un certain nombre dans la liste - disons . Demandons-nous, à quoi ça sert ? Que ce soit VRAI. 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. Le contraire est vérifié de la même manière : de FALSE suit TRUE. Nous sommes arrivés à une contradiction, ce qui signifie que l'hypothèse de départ est erronée. Ainsi, pour l'arithmétique formelle, il n'y a pas de déduction cohérente complète. Q.E.D.

Il convient ici de rappeler Épiménide (voir le portrait dans le titre), qui, comme vous le savez, a déclaré que tous les Crétois sont des menteurs, étant lui-même Crétois. Dans une formulation plus concise, 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 pour la preuve.

En conclusion, je tiens à souligner que TGN ne prétend rien de particulièrement surprenant. Après tout, 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 entiers (rappelez-vous, cette affirmation a une preuve très élégante qui date de plus de deux mille ans ?). Et les racines des polynômes à coefficients rationnels ne sont pas non plus tous des nombres. Et maintenant, il s'est avéré 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 n'est pas difficile de voir que THN s'applique également à de nombreux autres langages propositionnels. Bien sûr, toutes les langues ne sont pas comme ça. Par exemple, définissons un langage comme celui-ci :

"Toute phrase Chinois est une déclaration vraie si elle est contenue dans le livre de citations du camarade Mao Tse Tung, et est incorrecte si elle n'est pas contenue.

Ensuite, l'algorithme de preuve complet et cohérent correspondant (on peut l'appeler "déductif dogmatique") ressemble à ceci :

"Feuillez parcourir le livre de citations du camarade Mao Tse Tung jusqu'à ce que vous trouviez la déclaration que vous recherchez. S'il est trouvé, alors c'est vrai, et si le livre de citations est terminé et que l'énoncé n'est pas trouvé, alors c'est faux.

Ici, nous sommes sauvés par le fait que toute citation est évidemment finie, de sorte que le processus de "prouver" prendra inévitablement fin. Ainsi, TGN est inapplicable au langage des déclarations dogmatiques. Mais nous parlions de langues difficiles, vérité?

Pour ce qui suit, nous décrirons le "langage de l'arithmétique formelle". Considérons une classe de chaînes de texte de longueur finie, composée de chiffres arabes, de variables (lettres de l'alphabet latin) prenant des valeurs naturelles, d'espaces, de signes d'opérations 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 nous importent peu). Il est clair que toutes ces lignes ne sont pas significatives (par exemple, "" est un non-sens). Le sous-ensemble d'expressions significatives de cette classe (c'est-à-dire les chaînes qui sont vraies ou fausses en termes d'arithmétique ordinaire) sera notre ensemble d'instructions.

Exemples d'instructions arithmétiques formelles :

etc. En d'autres termes, les FSP sont équivalentes aux fonctions d'un argument naturel avec une valeur booléenne.

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

Pour le langage propositionnel de l'arithmétique formelle, il n'y a pas de déduction cohérente complète.

Nous allons prouver par contradiction.

Supposons donc qu'un tel 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 TRUE si et seulement si le résultat de la substitution dans le FSP de son propre numéro dans notre liste donne une fausse déclaration.

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

Évidemment, sous l'hypothèse ci-dessus, tout FSP de peut être associé à un algorithme contenant un nombre naturel en entrée et une valeur booléenne en sortie. Le contraire est moins évident :

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

"Toute phrase en chinois est une affirmation vraie si elle est contenue dans le livre de citations du camarade Mao Tse Tung, et est incorrecte si elle n'est pas contenue."

Ensuite, l'algorithme de preuve complet et cohérent correspondant (on peut l'appeler "déductif dogmatique") ressemble à ceci :

"Feuillez parcourir le livre de citations du camarade Mao Tse Tung jusqu'à ce que vous trouviez la déclaration que vous recherchez. S'il est trouvé, alors c'est vrai, et si le livre de citations est terminé et que l'énoncé n'est pas trouvé, alors c'est faux.

Ouspensky V.A.

Théorème d'incomplétude de Gödel. 1994.

Informatique théorique 130,1994, pp.273-238.

Peut-être que le théorème d'incomplétude de Gödel est vraiment unique. Unique en ce sens qu'ils s'y réfèrent lorsqu'ils veulent prouver "tout dans le monde" - de la présence des dieux à l'absence de raison. Je me suis toujours intéressé à une "question plus primaire" - et qui parmi ceux qui se réfèrent au théorème d'incomplétude pourrait non seulement le formuler, mais aussi le prouver ? Je publie cet article pour la raison qu'il présente une formulation très accessible du théorème de Gödel. Je vous recommande de lire d'abord l'article de Tullio Regge Kurt Gödel et son célèbre théorème

La conclusion sur l'impossibilité d'un critère universel de vérité est

une conséquence directe du résultat obtenu par Tarski en combinant

théorème d'indécidabilité de Gödel avec sa propre théorie de la vérité, selon

où il ne peut y avoir de critère universel de vérité, même pour des

domaine étroit de la théorie des nombres, et donc pour toute science qui utilise

arithmétique. Naturellement, ce résultat s'applique a fortiori au concept de vérité

dans tout domaine de connaissance non mathématique dans lequel il est largement

l'arithmétique est utilisée.

Karl Popper

1. Énoncé du problème

Le théorème d'incomplétude, dont nous donnerons la formulation exacte à la fin de ce chapitre, et peut-être plus tard (si cela intéresse le lecteur) et la preuve, énonce approximativement ceci : sous certaines conditions dans n'importe quelle langue il y a vrai, mais déclarations indémontrables.

1.1.1. Alphabet

Par alphabet, nous entendons un ensemble fini de signes élémentaires (c'est-à-dire des choses qui ne peuvent pas être décomposées en éléments constitutifs). Ces caractères sont appelés lettres de l'alphabet. Par mot d'un alphabet, nous entendons une suite finie de lettres. Par exemple, les mots ordinaires en anglais (y compris les noms propres) sont des mots de l'alphabet à 54 lettres (26 lettres minuscules, 26 lettres majuscules, un tiret et une apostrophe). Autre exemple - les nombres naturels en notation décimale sont des mots de l'alphabet à 10 lettres, dont les lettres sont des signes : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Nous utiliserons des majuscules ordinaires pour désigner alphabets. Si L est un alphabet, alors L ? désignera l'ensemble de tous les mots de l'alphabet L, - mots formés à partir de ses lettres. Nous supposerons que toute langue a son propre alphabet, de sorte que toutes les expressions de cette langue (c'est-à-dire - les noms de divers objets, les déclarations sur ces objets, etc.) sont des mots de cet alphabet. Par exemple, toute phrase en anglais, ainsi que tout texte écrit en anglais, peut être considéré comme un mot de l'alphabet étendu de 54 lettres, qui comprend également des signes de ponctuation, un espace entre les mots, un caractère redline et éventuellement d'autres caractères utiles. En supposant que les expressions du langage sont des mots d'un certain alphabet, nous excluons donc de la considération les expressions "multicouches" comme ???f(x)dx. Cependant, cette limitation n'est pas trop importante, puisque toute expression de ce type, en utilisant des conventions appropriées, peut être "étirée" sous une forme linéaire. Tout ensemble M contenu dans L ? est appelé un ensemble de mots de l'alphabet L. Si nous disons simplement que M est un ensemble de mots, alors nous voulons dire que c'est un mot d'un alphabet. Maintenant, l'hypothèse linguistique ci-dessus peut être reformulée comme suit : dans n'importe quelle langue, tout ensemble d'expressions est un ensemble de mots.

1.1.2. Beaucoup de vraies revendications

1.1.3. Paire de langues fondamentales

1.2. "Improuvable"

"Improuvable" signifie n'avoir aucune preuve.

1.3. Preuve

Une fois écrite, la preuve devient un mot dans un alphabet P, tout comme n'importe quel texte anglais est un mot dans l'alphabet L, dont un exemple a été donné ci-dessus. L'ensemble de toutes les preuves forme un sous-ensemble (et un assez grand sous-ensemble) de l'ensemble P?. Nous n'essaierons pas de donner une définition précise de ce concept à la fois "naïf" et "absolu" de la preuve, ni - ce qui est équivalent - de définir le sous-ensemble correspondant de P?. Au lieu de cela, nous considérerons un analogue formel de ce concept vague, pour lequel nous utiliserons encore le terme "preuve" dans ce qui suit. Cet analogue a deux caractéristiques très importantes qui le distinguent du concept intuitif (bien que l'idée intuitive de la preuve reflète toujours ces caractéristiques dans une certaine mesure). Tout d'abord, nous supposons qu'il existe différents concepts de preuve, c'est-à-dire que différents sous-ensembles de preuves dans P? sont autorisés, et même plus que cela : nous supposerons en fait que l'alphabet des preuves de P lui-même peut changer . Dans ce qui suit, nous exigeons que pour chacune de ces conceptions d'une preuve il existe une méthode efficace, c'est-à-dire un algorithme, qui déterminerait nécessairement si un mot donné de l'alphabet P est une preuve ou non. Nous supposons également qu'il existe un algorithme qui peut toujours être utilisé pour déterminer quelle déclaration une preuve donnée prouve. (Dans de nombreuses situations, la déclaration en cours de preuve est simplement la dernière déclaration dans la séquence d'étapes qui forment la preuve.)

Ainsi, notre formulation finale de la définition est la suivante :

(1) Nous avons l'alphabet L (l'alphabet de la langue) et l'alphabet P (l'alphabet de la preuve).

(3) Nous avons aussi une fonction ? (pour trouver ce qui a été prouvé exactement), à qui appartient le domaine ? satisfait la condition P???P?, et dont la plage est dans P?. Nous supposons que nous avons un algorithme qui calcule cette fonction (la signification exacte des mots "l'algorithme calcule une fonction" est la suivante : les valeurs de la fonction sont obtenues à l'aide de cet algorithme - un ensemble de règles de transformation spéciales). On dira que l'élément p? P est une preuve du mot ?(p) de l'alphabet L.

Un triplet qui satisfait les conditions (1)-(3) est appelé un système déductif sur l'alphabet L.

Pour le lecteur familiarisé avec la manière habituelle de définir la "preuve" en termes d'"axiome" et de "règle d'inférence", nous expliquerons maintenant comment cette méthode peut être considérée comme un cas particulier de la définition donnée dans la section 1.3.2. C'est-à-dire qu'une preuve est généralement définie comme une séquence de telles expressions de langage, dont chacune est soit un axiome, soit obtenue précédemment à partir d'énoncés déjà existants en utilisant l'une des règles d'inférence. Si nous ajoutons un nouveau mot * à l'alphabet de notre langue, alors nous pouvons écrire une telle preuve comme un mot composé à l'aide de l'alphabet résultant : la séquence d'expressions devient le mot C1*C2*...*Cn. Dans ce cas, la fonction qui détermine exactement ce qui a été prouvé a sa valeur dans la partie de ce mot qui suit immédiatement la dernière lettre * de la séquence. L'algorithme dont l'existence est requise dans la section 1.3.2. les définitions peuvent facilement être construites une fois que nous avons défini avec précision l'un des valeurs acceptées mots "axiome" et "règle d'inférence".

1.4 Tentatives de formulation précise du théorème d'incomplétude

1.4.1. Premier essai

"Sous certaines conditions, pour le couple fondamental de la langue de l'alphabet L et du système déductif sur L, il existe toujours un mot dans T qui n'a pas de preuve." Cette option semble encore vague. En particulier, nous pourrions facilement trouver un certain nombre de systèmes déductifs qui ont très peu de mots démontrables. Par exemple, dans un système déductif vide (où P = ?), il n'y a aucun mot qui aurait des preuves.

1.4.2. Deuxième essai

"Sous certaines conditions concernant la paire fondamentale, il n'existe pas de tel système déductif dans lequel chaque mot de T aurait une preuve."

1.5. Cohérence

Il serait tout à fait naturel d'exiger que seuls les "énoncés vrais", c'est-à-dire que seuls les mots de T, puissent être prouvés. On dira qu'un système déductif est cohérent par rapport à un couple fondamental si ?(P) ?T. Dans tous les raisonnements ultérieurs, nous ne nous intéresserons qu'à de tels systèmes déductifs cohérents. Si on nous donne un langage, alors il serait extrêmement tentant de trouver un tel système déductif cohérent dans lequel chaque énoncé vrai aurait une preuve. La variante du théorème de Gödel qui nous intéresse précise que sous certaines conditions par rapport au couple fondamental, il est impossible de trouver un tel système déductif.

1.6. complétude

On dit qu'un système déductif est complet par rapport à un couple fondamental, pourvu que ?(P)?T. Alors notre formulation du théorème d'incomplétude prend la forme suivante :

Sous certaines conditions par rapport à la paire fondamentale, il n'y a pas de tel système déductif sur L qui serait à la fois complet et relativement cohérent.