La Démonstration du théorème de Gödel représente un tournant majeur dans l’histoire de la logique et des mathématiques. Ce théorème, formulé par Kurt Gödel au début du XXe siècle, a profondément modifié notre compréhension des limites des systèmes formels axiomatiques.
Enoncé du théorème
Le théorème d’incomplétude de Gödel se compose en réalité de deux théorèmes distincts, bien que souvent regroupés sous une seule appellation. Le premier théorème d’incomplétude stipule que tout système formel cohérent et suffisamment puissant pour exprimer l’arithmétique élémentaire contient des énoncés vrais qui ne sont pas démontrables dans le système lui-même. Formellement, si un système \( \mathcal{F} \) est cohérent et contient l’arithmétique de Peano (ou une théorie équivalente), alors il existe un énoncé \( \mathcal{G} \) tel que :
- \( \mathcal{G} \) est vrai (dans le modèle standard de l’arithmétique).
- \( \mathcal{F} \nvdash \mathcal{G} \) (c’est-à-dire que \( \mathcal{G} \) n’est pas démontrable dans \( \mathcal{F} \)).
- \( \mathcal{F} \nvdash \neg \mathcal{G} \) (c’est-à-dire que la négation de \( \mathcal{G} \) n’est pas démontrable dans \( \mathcal{F} \)).
Un tel énoncé \( \mathcal{G} \) est dit indécidable dans le système \( \mathcal{F} \).
Le second théorème d’incomplétude, qui découle du premier, affirme que la cohérence d’un tel système formel ne peut pas être prouvée à l’intérieur du système lui-même. En d’autres termes, si \( \mathcal{F} \) est cohérent et contient l’arithmétique de Peano, alors l’énoncé \( \text{Cons}(\mathcal{F}) \), qui exprime la cohérence de \( \mathcal{F} \) (c’est-à-dire l’absence de contradiction), n’est pas démontrable dans \( \mathcal{F} \). Formellement :
Si \( \mathcal{F} \) est cohérent, alors \( \mathcal{F} \nvdash \text{Cons}(\mathcal{F}) \).
Démonstration du théorème de Gödel
La démonstration du théorème de Gödel est complexe et repose sur plusieurs concepts clés. L’un des éléments fondamentaux est la numérotation de Gödel, qui permet de coder les expressions et les suites de symboles d’un système formel en nombres entiers. Cela permet de « parler » des propriétés du système formel (comme la prouvabilité) à l’intérieur du système lui-même, en utilisant l’arithmétique.
L’idée centrale est de construire un énoncé, souvent appelé l’énoncé de Gödel \( \mathcal{G} \), qui, via la numérotation de Gödel, affirme sa propre indémontrabilité dans le système formel \( \mathcal{F} \). Cet énoncé est construit de manière autoréférentielle, un peu comme le paradoxe du menteur (« Cette phrase est fausse »).
La construction de \( \mathcal{G} \) repose sur le lemme de diagonalisation. Ce lemme permet, étant donné une formule \( \phi(x) \) avec une variable libre \( x \), de construire un énoncé \( \psi \) tel que \( \mathcal{F} \vdash \psi \leftrightarrow \phi(\ulcorner \psi \urcorner) \), où \( \ulcorner \psi \urcorner \) est le nombre de Gödel de \( \psi \). En appliquant ce lemme à une formule exprimant la non-prouvabilité, on obtient l’énoncé de Gödel.
Si \( \mathcal{G} \) était démontrable dans \( \mathcal{F} \), alors, par la construction de \( \mathcal{G} \), le système prouverait sa propre non-prouvabilité, ce qui conduirait à une contradiction (si le système est cohérent). Si la négation de \( \mathcal{G} \) était démontrable, cela signifierait que le système prouve que \( \mathcal{G} \) est prouvable, ce qui, encore une fois, mènerait à une contradiction (en supposant que le système est \( \omega \)-cohérent, une condition plus forte que la simple cohérence, mais souvent satisfaite par les systèmes considérés).
Pour le second théorème, Gödel a montré que le raisonnement utilisé pour prouver le premier théorème peut être formalisé à l’intérieur de l’arithmétique. Cela permet de déduire que si le système pouvait prouver sa propre cohérence, il pourrait également prouver l’énoncé de Gödel, ce qui contredirait le premier théorème.
Il est important de noter que les théorèmes de Gödel ne signifient pas que certaines vérités mathématiques sont inaccessibles. Ils montrent plutôt qu’aucun système formel unique, suffisamment puissant pour l’arithmétique, ne peut capturer toutes les vérités arithmétiques par le biais de démonstrations finies à partir d’un ensemble fini d’axiomes. Pour approfondir vos connaissances en théorie des ensembles, vous pouvez consulter des ressources sur la théorie des ensembles. L’étude de la logique mathématique est également essentielle pour une compréhension complète de ces concepts.
Les théorèmes d’incomplétude de Gödel ont eu un impact considérable sur la philosophie des mathématiques et la logique, remettant en question le programme de Hilbert qui visait à établir une fondation formelle complète et cohérente pour toutes les mathématiques.
Pour explorer d’autres concepts mathématiques à différents niveaux, n’hésitez pas à visiter :
