Incomplétude, Gödel, un aperçu

NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 04/06/2020 Orientation générale DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	LOGIQUE
Débutants Logique	Domaines			Glossaire Logique
INDEX Logique	Dualité	Logique de Boole	Logique formelle	Logique floue
	Raisonnement	Intelligence		Incomplétude
		Sommaire de cette page >>> Incomplétude >>> Solution des paradoxes >>> Paradoxe de Russel >>> Russell – Biographie >>> Intelligence artificielle et indécidabilité >>> Accélération

Dessin de Mix et Remix

Voir Pensées & humour

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

- Gödel, l'homme qui a démontré les limites de la science! Le tombeur de l'idéal scientifique.

- Je n'ai jamais affirmé une telle ânerie. Je parlais des limites internes de l'axiomatique.

- Peu importe les détails. Vous êtes du pain béni pour tous les pédants. Ils jetteront dans le même sac le principe d'incertitude avec le théorème d'incomplétude pour en déduire que la science ne peut pas tout.

Yannick Grannier – La déesse des petites victoires

Voir Pensées & humour

INCOMPLÉTUDE

Introduction

En observant les nombres, il est possible d'établir des affirmations et, à partir de celles-ci, d'en déduire d'autres. En poursuivant ce processus, on va trouver toutes une gamme de choses vraies et une autre gamme de choses fausses: des théorèmes donnant les assertions vraies et des théorèmes donnant les assertions fausses. Ces théorèmes forment les fondements de l'arithmétique.

Illustration

Soit un carré représentant toutes les assertions possibles dans cette arithmétique et, selon les couleurs, le vrai (les assertions prouvées) et le faux (les assertions rejetées).

Oui, mais:

Il subsiste quelques îlots qui sont non accessibles.
Gödel, avec son premier théorème d'incomplétude, dit qu'il existe toujours au moins une assertion qui se ne sera pas dans les " prouvées " ou dans les " rejetées ". Ces assertions sont indécidables.

Les deux théorèmes d'incomplétude de Gödel
*Premier*	*Second*
Il n'y a aucun moyen de générer toutes les vérités au sujet des nombres.	Une affirmation ne peut pas être vraie et fausse en même temps. Comment résoudre ce type paradoxe?
Quelle que soit la méthode, il existera toujours au moins une assertion non prouvée.	Pour s'en sortir, il faut sortir du système lui-même, se mettre en méta-position, en vision externe.
Quelle que soit la formalisation cohérente d'une arithmétique, il existera des vérités non décidables dans cette arithmétique.	Une arithmétique est trop faible pour pouvoir prouver sa propre consistance.
Même en forgeant une arithmétique qui rend décidables les assertions non-décidables d'une autre arithmétique, on retrouvera d'autres assertions non-décidables.	L'assertion "cette arithmétique est cohérente" ne peut pas être prouvée, quelle que soit l'arithmétique choisie.
Démonstration Elle trop complexe pour être exposée ici! Mais le principe consiste à convertir le problème en équations polynomiales, et l'astuce repose sur la démonstration que ces équations n'ont pas de solutions en nombres entiers. Pour en savoir plus rendez-vous sur le site de La tour d'ivoire de John Bonobo

Assertion:

Affirmation telle que " la somme de deux nombres impairs est paire ", " le carré de tout nombre est négatif "... Elle peut être juste (démontrable) ou fausse selon les hypothèses prises au départ.

Axiome:

Assertion non démontrée, prise comme point de départ de construction d'une arithmétique. Il existe de nombreuses arithmétiques selon le choix de ces points de départ.

Théorème:

Déduction faite à partir des axiomes de départ et, également, des théorèmes déjà établis. Un théorème indique si une assertion est juste ou fausse.

Décidable:

Il existe effectivement un théorème qui vérifie ou rejette l'assertion.

Cohérence:

Une assertion ne peut pas être à la fois vraie et non vraie, comme par exemple: " cette phrase est fausse ".

Voir DicoMot Maths

SOLUTION DES PARADOXES

Le deuxième théorème d'incomplétude met fin aux réflexions sur les paradoxes en affirmant qu'il est vain de penser trouver une solution sur le même plan de raisonnement.

Il faut passer à un sur-ensemble, une méta-position, un système plus large.

Exemples
Cette phrase	est fausse
Il est interdit	d'interdire
Toutes les règles	ont des exceptions
Je n'épouserai qu'une femme assez intelligente ...	pour ne pas m'épouser
Recto: La phrase du verso est vraie	Verso: La phrase du recto est fausse
Épiménide le Crétois disait:	" tous les Crétois sont des menteurs "
Socrate: Ce que dit Platon est faux	Platon: Ce que dit Socrate est vrai
Dites-vous toujours la vérité ?	Non!
Tout dans ce livre est digne de confiance	Sauf la phrase ci-contre, à gauche
Lu sur un badge:	Interdisons les badges
Un graffiti disait:	A bas les graffitis
Cette phrase contient sept mots	Cette phrase ne contient pas sept mots Voir Autoréférences
Parmi ces propositions, trois sont fausses: 2 + 2 = 4 3 x 6 = 17 8 / 4 = 2 13 - 6 = 5 5 + 4 = 9	Solution Les trois propositions fausses sont: - deux des équations et... - l'affirmation que 3 propositions sont fausses
Le crocodile: "Vais-je manger ton bébé. Réponds sans mentir et je te rends le bébé intact "	La mère répond: " Tu vas croquer mon bébé ! "
Dans Don Quichotte: À la frontière d'un pays, il faut dire la vérité sinon c'est la pendaison	- Pourquoi venez-vous ? - Pour être pendu !
Constitution US: On peut amender la Constitution si les 2/3 des Parlementaires sont d'accord	Mais même avec 2/3 des voix, ou plus, peut-on amender cette partie même de la Constitution ?
Tu places ta main dans le trou du rocher de la vérité. Si tu mens tu ne peux pas retirer ta main	Je dis: " je ne retirerai pas ma main "
Le barbier rase tous ceux qui ne se rasent pas eux-mêmes, et que ceux-là	Qui rase le barbier ?
Le prochain mot que tu diras sera-t-il " non " ?	- OUI, ah non! - NON, raté, tu mens!
Je ferai un examen surprise dans la semaine et personne ne pourra en prévoir la date!	Ce n'est donc pas samedi, car vendredi soir on saurait; ni vendredi, car jeudi soir on saurait...
Le robot qui répare tous les robots qui ne se réparent pas eux-mêmes	Qui répare le robot ?
Le catalogue qui répertorie tous les catalogues qui ne se répertorient pas eux-mêmes	Dans quel catalogue le trouvera-t-on ?
Soit l'ensemble de tous les ensembles qui ne se contiennent pas eux-mêmes	Est-ce que ce nouvel ensemble se contient lui-même ? Paradoxe de RUSSEL

Voir Phrases en logique formelle

PARADOXE DE RUSSEL
Ensemble qui ne se contient pas lui-même	Ensemble qui se contient lui-même
Ensemble normal *Homme: l'ensemble des hommes n'est pas un homme. Long* n'est pas un adjectif long. *Monosyllabe*: ce mot ne fait pas partie des mots monosyllabiques. L'ensemble des choses qui ne peuvent pas se décrire en douze mots.	Ensemble non-normal *Idée abstraite: ce concept appartient bien à l'ensemble des idées abstraites. Court* est un adjectif court. *Polysyllabe*: ce mot est bien polysyllabique. L'ensemble des choses qui peuvent se décrire en dix mots.
Soit N l'ensemble de tous ces ensembles normaux
Si on place N dans cette colonne: Il est normal, il ne se contient pas lui-même. Mais, puisqu'il est normal, c'est aussi un membre de l'ensemble N, il est non – normal.	Si on place N ici: Il est non-normal, il se contient lui-même. Mais, puisqu'il est non - normal, il n'est pas membre de N, il est normal.
Contradiction dans les deux cas !
Gödel à montré qu'en effet, en restant à ce niveau on est toujours bloqué. Pour s'en sortir, il faut sortir du domaine dans lequel on parle. Alors on passe dans un *MÉTALANGAGE. On parle des choses du domaine, sans être dans le domaine lui-même. Cette manière de voir est due à Russel et s'appelle " la théorie simple des types ". Exemple* *Langage:* La neige est blanche. *Métalangage:* La neige est blanche est une phrase vraie. Avec le métalangage aucun ensemble ne peut s'inclure lui-même ! Force est d'admettre que: Une classe d'ensembles n'est pas nécessairement un ensemble.

Voir Paradoxes

Bertrand RUSSELL (1872 – 1970, 98 ans)

Philosophe et logicien britannique.

1927: Il fonde une école sur des bases pédagogiques de liberté.

Il a fondé le logicisme et la théorie des types.

1910-1913: Il a écrit Principia mathematica, en collaboration. avec Whitehead.

1950: Prix Nobel de littérature 1950.

Il a toujours milité en en faveur du pacifisme.

La démonstration de Russell

Humour: En 1959, Bertrand Russel (80 ans), philosophe britannique, expert en logique paradoxale répond à la question: que pensez-vous es femmes ? – Je pense des femmes ce que j'en pensais il y a exactement cinquante ans. Mais, pendant ce demi-siècle, il m'est parfois arrivé de croire qu'une femme ne faisait pas partie des femmes.

Voir Contemporains / Démonstrations erronées / 2 + 2 = 5

L’intelligence n’arrive pas à définir l’intelligence.

Intelligence artificielle et indécidabilité

Théorème d'incomplétude de Gödel (1931)

La plupart des systèmes formels peuvent formuler des énoncés corrects qui ne sont ni démontrables, ni infirmables: ils sont indécidables.

Est-ce applicable à l'informatique ?

Oui ! Savoir si un programme informatique va s'arrêter de calculer est une proposition indécidable.

Analyser le code ? Oui, mais si le programme est complexe, il n'y a aucune méthode générale, aucune théorie ni aucun modèle qui permette de conclure.

Avec les réseaux de neurones et leur auto-apprentissage (machine learning), difficile d'aller voir finement ce qui s'y passe.

Indécidabilité ?

Pas de risque pour les programmes actuels, ils sont encore trop basiques, occupés à faire des tris.

Le jour où, ce niveau sommaire sera dépassé, et selon le théorème de Gödel, on butera sur le mur de l'indécidabilité.

L'intelligence artificielle est une nouvelle science, et elle manque encore cruellement de théorie.

Cas de l'apprentissage par les machines

Pas d'exception, on y retrouve ce problème d'indécidabilité. Mais pas de panique, pas pour le moment !

L'apprentissage machine actuel est si basique qu'il n'est pas concerné.

Les algorithmes apprennent simplement à classer des items selon diverses catégories. Avec assez d'exemples, on a prouvé que ça marche.

Comment la machine apprend ?

Les programmes d'apprentissage, comme les réseaux de neurones artificiels fonctionnent sur le principe de l'apprentissage statistique par l'exemple.

Pour reconnaître un animal, on entraîne l'algorithme avec des millions d'images de l'animal à reconnaitre.

Le réseaux de neurones enregistre l'image qu'il s'en fait et la modifie avec les nuances apportées à chaque expérience.

À la longue, le programme reconnait l'objet avec un taux d'erreur acceptable et contrôlable.

Notion avancée**

Une autre notion introduite par Gödel

Théorème d'accélération de Gödel

Extrait de Wikipédia:

Une vision de spécialiste

Ce qui gêne principalement l'immense majorité des mathématiciens, c'est qu'il existe un grand nombre de propositions intéressantes et en principe déductibles des axiomes, mais qu'on n'arrive pas à démontrer parce que leur démonstration est trop compliquée.

Et cette limitation-la n'a rien à voir avec l'incomplétude de Gödel.

Ce qui fait que, lorsqu'un mathématicien aborde un problème concret, il ne craint jamais — ou presque — de ne pouvoir le résoudre à cause théorème de Gödel; mais plutôt parce qu'il n'est pas assez malin.

N'oubliez pas non plus que Gödel montre que certaines propositions «indécidables» sont vraies. Le formalisme ne permet pas de les démontrer, mais nous pouvons néanmoins voir qu'elles sont vraies.

C'est une remarque élémentaire, mais qui est souvent oubliée par les philosophes qui aiment utiliser le théorème de Gödel pour disserter sur les limites de la connaissance.

Vu ainsi, le théorème de Gödel élargit plutôt nos connaissances que le contraire.

Références

Le texte ci-dessus est un extrait du livre: À l'ombre des lumières - Livre très intéressant, mais d'un niveau relevé.

Propos de Jean Bricmont – Professeur de physique à l'Université de Louvain, Président de l'Association française pour l'information scientifique – Coauteur de: Les impostures intellectuelles.

En réponse à Régis Debray – Président de l'Institut européen de l'histoire et des sciences des religions.