Incomplétude

Un article de Wikipédia, l'encyclopédie libre.

L’incomplétude des principes des mathématiques se manifeste par plusieurs théorèmes. Dans une théorie mathématique assez complexe, par exemple si elle contient l'autoréférencement, il n'y a pas que des propositions démontrables. Il y a en fait quatre différents types des propositions mathématiques :

• des propositions qui sont démontrables (ce qu'on apprend jusqu'au baccalauréat)
• des propositions qu'on ne peut pas démontrer, ni démontrer leur contraire, qu'on peut alors choisir (ce que l'on appelle incomplétude ou indécidabilité)
• des propositions qui ne peuvent ni être vraies, ni êtres fausses (ce sont des paradoxes)
• des propositions qu'on peut démontrer, mais dont le contraire peut aussi être démontré (ce qu'on appelle l'inconsistance)

Les mathématiques ne sont donc pas pure certitude. Ce sont des constructions qui ne sont cohérentes que si l'on ne cherche pas trop loin.

Sommaire 1 Le paradoxe du menteur 2 Les prédicats de vérité et le théorème de Tarski 3 Les prédicats de prouvabilité et le théorème d'incomplétude de Gödel 4 L’indécidabilité 5 Un théorème général sur l’incomplétude de la prouvabilité 6 L’incomplétude ontologique 7 Où sont les axiomes manquants ? 8 Lien externe

[modifier] Le paradoxe du menteur

Ce problème remonte à la Grèce antique, au sujet de la dialectique. A cette époque on n'avait pas notre formalisme mathématique actuel et que les démonstrations se faisaient par de grands discours. L'énoncé du problème est le suivant : peut-on croire un homme qui dit qu'il est un menteur ? Le paradoxe est le suivant : si cet homme est un menteur, alors il dit vrai, donc il n'est pas menteur. Et s'il n'est pas menteur, alors il ment, donc il est menteur... On peut rendre la question plus subtile, car le contraire de menteur tout le temps n'est pas ne jamais mentir. Mais si la personne dit qu'elle ment à l'instant où elle énonce qu'elle ment, cette question est tout simplement insoluble dans la logique mathématique. Ce genre de propositions ne sont ni vraies ni fausses.

Par extension, on peut imaginer une autre logique, dans laquelle le vrai et le faux sont moins absolus (voir la notion de logique floue), qui tiendrait compte des intentions par exemple. On aboutirait peut-être à quelque chose du genre : ce qui dit la personne est 50% vrai et 50% faux.

[modifier] Les prédicats de vérité et le théorème de Tarski

[modifier] Les prédicats de prouvabilité et le théorème d'incomplétude de Gödel

[modifier] L’indécidabilité

• Le problème de la décision
• Enoncés, ensembles et problèmes indécidables
• La théorie des systèmes formels
• Le problème de l'arrêt

[modifier] Un théorème général sur l’incomplétude de la prouvabilité

Toute théorie mathématique suffisamment riche n’est jamais capable de prouver toutes ses vérités.

On définit ici suffisamment riche par les conditions suivantes.

a) la théorie T permet de définir un ensemble indécidable

b) à partir de deux ensembles déjà définis E et F, T permet de définir le complémentaire de F dans E, E Moins F, ou ensemble différence de E et F, c’est-à-dire la partie de E qui ne contient aucun élément de F.

Si E est l’ensemble de toutes les expressions formelles et F un ensemble indécidable alors E Moins F, ou F, n’est pas énumérable. Comme l’ensemble des formules prouvables de T est énumérable, il y a des vérités d’appartenance à cet ensemble non-énumérable qui ne sont pas prouvables.

On peut voir ce théorème comme une généralisation du premier théorème d’incomplétude de Gödel. Les conditions a et b sont remplies par l’arithmétique formelle mais la preuve est un peu difficile et ne sera pas présentée ici.

[modifier] L’incomplétude ontologique

[modifier] Où sont les axiomes manquants ?

Si on ne peut pas prouver toutes les vérités, c’est qu’il manque des axiomes. Quels sont-ils ? Jusqu’ici on a seulement prouvé que des théories sont incomplètes mais on n’a pas dit pourquoi. Il semble également assez mystérieux que ces théories résistent toujours aux tentatives de complétude. Quelle que soit la façon dont on les complète avec de nouveaux axiomes elles restent incomplètes. Même si on se donne des axiomes en nombre infini elles restent incomplètes, dès que ces axiomes sont déterminés par des règles explicites et univoques. Qu’est-ce qui manque ? Qu’est-ce qui rend la complétude inaccessible à nos esprits finis ?

Il semble intuitivement très plausible que les incomplétudes de la prouvabilité axiomatique et de l’ontologie sont étroitement liées. Ce qui suit peut être considéré comme presqu’évident, mais il faut le prouver.

L’incomplétude mathématique est essentiellement ontologique. Les théories axiomatiques ne permettent jamais de prouver toutes leurs vérités parce que leur ontologie est toujours limitée. Elles n’ont jamais assez d’axiomes d’existence. Elles ne permettent jamais de définir assez d’ensembles, de prédicats ou de concepts pour formaliser toutes les preuves concevables. On ne peut pas donner un nombre fini de règles qui suffise pour établir l’existence de tous les êtres imaginables, c’est-à-dire tous les êtres qui ont le droit d’exister au yeux des mathématiciens.

L’imagination déborde tous les cadres.

[modifier] Lien externe

• La démonstration (et ses limites)