Précis d'épistémologie/ L'incomplétude des principes mathématiques

Un livre de Wikilivres.
Aller à : navigation, rechercher

Kurt Gödel a prouvé, en 1931, que nous ne pouvons pas donner explicitement une liste complète de tous les principes mathématiques. Plus précisément, une liste explicite de principes ne peut jamais suffire pour prouver toutes les vérités mathématiques, même si on se limite aux vérités sur les nombres naturels. C'est le premier théorème d'incomplétude de Gödel. L'incomplétude des principes est nécessaire. Elle ne vient pas de notre manque d'imagination ou de travail. Les mathématiciens sont capables de donner des listes d'axiomes très puissants, qui suffisent en général pour prouver toutes les vérités qu'on souhaite prouver. Mais ces listes sont incomplètes au sens où elles ne suffisent pas pour prouver toutes les vérités mathématiques. Elles peuvent être enrichies avec de nouveaux axiomes plus puissants mais elles ne peuvent jamais être définitivement complétées. Il y aura toujours des vérités mathématiques qu'elles ne permettent pas de prouver.

Ce théorème d'incomplétude est parfois interprété à tort comme une preuve qu'il y a des vérités que nous ne pourrons jamais connaître, qu'il y a des questions sensées auxquelles nous ne pourrons jamais répondre, qu'il y a des solutions que nous ne pourrons jamais trouver. Cette interprétation commet une faute de logique. Gödel a prouvé que pour toute théorie T cohérente et définie par une liste explicite d'axiomes il existe au moins une vérité V que T ne peut pas prouver. Mais cela ne prouve pas qu'il existe une vérité V qu'aucune théorie ne peut prouver. De fait, quand on a trouvé une vérité V improuvable dans une théorie T, il est en général très facile de définir une théorie T+, en ajoutant à T un nouvel axiome, qui permet de prouver V.

Le principe de Hilbert (1930), « Nous devons savoir, nous saurons », tient toujours, même après Gödel. Rien ne permet d'affirmer qu'il y a des vérités mathématiques que nous ne pourrons jamais connaître.

On est en général très étonné la première fois qu'on entend parler du théorème d'incomplétude de Gödel, parce qu'on est habitué à identifier vérité mathématique et prouvabilité. Nous savons qu'un théorème est vrai quand nous savons le prouver. Mais cet étonnement est facilement dissipé quand on comprend qu'une liste explicite d'axiomes ne peut pas suffire pour prouver l'existence de tous les êtres mathématiques, même si on se limite aux plus élémentaires, les nombres naturels et les ensembles de nombres naturels.

Résumé

On commence par prouver le premier théorème d'incomplétude de Gödel d'une façon qui élimine les difficultés techniques et permet de se concentrer sur le cœur de l'argument, un énoncé vrai qui dit de lui-même qu'il est improuvable. Gödel prouve que cet énoncé est vrai sous l'hypothèse où la théorie T qui permet de le formuler est vraie. Mais cette preuve de la vérité de l'énoncé "improuvable" ne peut pas être formalisée dans T. L'énoncé est improuvable à partir des axiomes de T mais il n'est pas absolument improuvable, puisque Gödel a prouvé sa vérité. Pour formaliser cette preuve, on a besoin d'une théorie qui prouve que les axiomes de T sont vrais. Or Tarski a prouvé qu'une théorie ne peut jamais définir un prédicat de vérité pour elle-même. C'est pourquoi la preuve de l'énoncé "improuvable" ne peut pas être formalisée dans T. Plus généralement, une théorie ne permet pas de prouver tous les énoncés vrais qu'elle énonce parce qu'elle ne peut jamais définir assez de prédicats ou d'ensembles pour donner ces preuves. On applique le principe du raisonnement par récurrence aux prédicats ou aux ensembles d'une théorie. Si des prédicats ou des ensembles ne sont pas définis dans la théorie, on ne peut pas s'en servir pour raisonner par récurrence. On peut en conclure que l'incomplétude mathématique est une conséquence de l'indénombrabilité, puisqu'une théorie ne peut jamais définir un nombre indénombrable d'ensembles, et donc qu'il y a toujours des ensembles qu'elle ne peut pas définir.

Le théorème de Cantor, que l'ensemble des ensembles de nombres naturels n'est pas dénombrable, les théorèmes d'incomplétude de la prouvabilité de Gödel, le théorème d'indéfinissabilité de la vérité de Tarski, le paradoxe de l'ensemble de tous les ensembles qui ne sont pas éléments d'eux-mêmes de Russell et les théorèmes d'indécidabilité de Church et Turing sont tous des manifestations de la même incomplétude mathématique.

On présentera les deux principaux systèmes d'axiomes, de Peano et Zermelo, avec lesquels on fonde habituellement les mathématiques. On expliquera pourquoi ils sont vrais, et donc cohérents, et comment le prouver.

On terminera en montrant que l'incomplétude des principes mathématiques n'est finalement pas très étonnante, parce que si on savait trouver toutes les solutions d'un problème indécidable, on aurait une sorte d'omniscience, on saurait comment trouver toutes les solutions de tous les problèmes.


Le premier théorème d'incomplétude de Gödel[modifier | modifier le wikicode]

La preuve ici proposée n'est pas conventionnelle. Gödel raisonne sur une théorie arithmétique. Il montre que les formules peuvent être représentées par des nombres et que les relations de conséquence logique entre formules peuvent alors être représentées par des relations entre des nombres. Toute la difficulté technique de sa preuve vient de là : montrer que les relations logiques entre formules peuvent être déterminées par des relations numériques entre les nombres qui représentent ces formules. On élimine cette difficulté en raisonnant non sur une théorie des nombres mais d'emblée sur une théorie des formules.

Rien n'interdit de faire une théorie qui permet de raisonner sur ses propres formules. Cette façon de faire n'est pas aussi convaincante que celle de Gödel, parce qu'elle ne prouve pas que la théorie des nombres est incomplète mais seulement qu'une bizarre théorie de ses propres formules est incomplète. On pourrait même croire que l'énoncé paradoxal qui est au cœur de la preuve vient seulement de la bizarrerie de la théorie et craindre qu'elle ne soit pas cohérente, donc pas une bonne théorie mathématique. Cette crainte n'est pas fondée. Si on s'y prend correctement, il est facile de faire une théorie mathématique vraie et donc cohérente qui énonce des vérités sur ses propres formules. C'est la façon la plus facile et la plus rapide de prouver l'incomplétude mathématique. Mais cela ne suffit pas pour prouver l'incomplétude de la théorie des nombres.

La preuve qui suit est identique à celle de Gödel, sauf sur un point, qu'on raisonne sur une théorie des formules, et donc que les formules ne sont pas représentées par des nombres.

T est une théorie qui considère ses propres formules comme des individus, ou des objets. Elle contient le prédicat binaire est une conséquence logique de et admet parmi ses axiomes les principes logiques. Toute liste finie de prémisses peut être identifiée à une unique formule, leur conjonction.

Elle a aussi d'autres prédicats et d'autres axiomes qui permettent de raisonner sur la façon dont les formules sont construites. En particulier, elle doit permettre de définir un prédicat est une formule à une variable libre. Les formules qui ont des variables libres ne sont ni vraies, ni fausses. Il faut attribuer des valeurs à leurs variables f, x, y ... avant que leur vérité puisse être décidée. Par exemple f est une formule est une formule à une variable libre f. La théorie T doit aussi permettre de définir un prédicat ternaire défini par g est obtenu à partir d'une formule f à une variable libre en substituant x à toutes les occurrences de sa variable. On suppose que tous les axiomes ont été correctement choisis, donc qu'ils sont vrais, et suffisants pour prouver les vérités formelles les plus élémentaires.

Une fois que la liste de ses axiomes est définie, T permet de définir un prédicat est prouvable dans T, parce que pour être prouvable, il suffit d'être une conséquence logique d'une conjonction finie d'axiomes.

T permet alors de définir le prédicat suivant :

Gödel(f) égale par définition à f est une formule à une variable libre et il existe g tel que g n'est pas prouvable dans T et g est obtenu à partir de f en substituant f à toutes les occurrences de sa variable libre.

Gödel(f) est une formule à une variable libre f, parce que la variable g est liée par le quantificateur existentiel.

On peut alors prouver que Gödel(Gödel(f)) est un énoncé vrai mais improuvable dans T.

Gödel(Gödel(f)) veut dire par définition Gödel(f) est une formule à une variable libre et Gödel(Gödel(f)) n'est pas prouvable dans T.

Si Gödel(Gödel(f)) était prouvable dans T alors elle serait fausse, puisqu'elle dit d'elle-même qu'elle n'est pas prouvable dans T. Or on a supposé que tous les axiomes de T sont vrais. Tous les théorèmes de T, c'est à dire les énoncés prouvables dans T, sont donc également vrais. Il en résulte que Gödel(Gödel(f)) ne peut pas être un théorème de T et donc qu'elle est vraie, puisque c'est exactement ce qu'elle affirme. On a donc trouvé un énoncé vrai et improuvable dans T.

Pour transposer cette preuve à la théorie des nombres il suffit de montrer que les prédicats est prouvable dans la théorie des nombres et g est obtenu à partir d'une formule f à une variable libre en substituant x à toutes les occurrences de sa variable peuvent être représentés par des relations arithmétiques entre les nombres qui représentent des formules.

Note technique : pour formuler correctement la théorie T il faut faire attention à l'usage des variables de formule. f est une variable de formule, mais elle n'est pas à elle toute seule une formule bien formée de T. Il en résulte que Pour toute formule f, f, par exemple, n'est pas non plus une formule bien formée de T. Une formule bien formée doit toujours contenir des prédicats constants appliqués à des constantes ou des variables. En outre, quand une formule A(f) est appliquée une autre formule B(f), c'est à dire qu'on a formé A(B(f)), la variable f est libre dans B(f) mais pas dans A(B(f)), parce que B(f) y est une constante.

L'infini indénombrable[modifier | modifier le wikicode]

Un ensemble est dénombrable lorsqu'on peut identifier tous ses éléments en les numérotant, avec des nombres naturels : 0, 1, 2, 3, 4 ... Un ensemble dénombrable peut être fini ou infini. L'ensemble de tous les nombres naturels est infini dénombrable. Cantor (1874) a prouvé qu'il y a des ensembles infinis encore plus grands. En particulier, l'ensemble des ensembles de nombres naturels n'est pas dénombrable.

On le prouve par l'absurde. Supposons que l'ensemble des ensembles de nombres naturels soit dénombrable. Cela veut dire qu'ils peuvent tous être identifiés par un numéro. Définissons alors l'ensemble C des nombres qui ne sont pas dans l'ensemble qui porte leur numéro et soit n le numéro de C. Mais si n n'est pas dans C alors il est dans C par définition de C. Donc il doit être dans C. Mais alors il n'est pas dans C, encore par définition de C. n est dans C si et seulement si il n'est pas dans C. C'est une absurdité. Donc l'ensemble C ne peut pas exister. Donc l'ensemble des ensembles de nombres naturels n'est pas dénombrable.

On peut en conclure immédiatement qu'une théorie des nombres est toujours incomplète, parce qu'elle ne permet jamais de définir tous les ensembles de nombres. L'ensemble des êtres définis et nommés par une théorie est toujours dénombrable, parce que pour définir et nommer on se sert d'un alphabet fini. On peut toujours numéroter les mots formés à partir d'un alphabet fini. Il suffit de les ranger par ordre de longueur, puis par ordre alphabétique pour les mots d'une même longueur. Le numéro d'un mot est alors son numéro d'ordre.

La preuve du théorème de Gödel ressemble à celle du théorème de Cantor, parce qu'une formule à une variable libre peut être considérée comme le nom de l'ensemble de tous les êtres pour lesquels elle est vraie. La preuve de Gödel définit l'ensemble de tous les nombres pour lesquels il n'est pas prouvable qu'ils sont dans l'ensemble nommé par la formule qu'ils numérotent.

Il n'est a priori pas évident que l'incomplétude de Gödel résulte de l'indénombrabilité de l'ensemble des ensembles de nombres. L'énoncé vrai et improuvable de Gödel porte seulement sur les nombres, pas sur les ensembles de nombres. On aurait pu espérer que l'arithmétique permette de prouver toutes les vérités qui ne portent que sur des nombres, qu'elle n'a pas besoin pour cela de prouver l'existence de tous les ensembles de nombres. Mais cet espoir est vain.

Pour prouver des vérités arithmétiques, on se sert du principe du raisonnement par récurrence, qu'on peut énoncer comme suit :

Si un ensemble de nombres contient zéro et s'il contient toujours le successeur de chacun de ses éléments alors il contient tous les nombres naturels.

Une théorie des nombres qui ne porte pas explicitement sur les ensembles de nombres applique ce principe aux formules à une variable libre. Celles-ci servent à représenter les ensembles de nombres.

Il n'est pas étonnant qu'une théorie explicite ne puisse jamais prouver toutes les vérités sur les nombres, parce qu'il y a toujours des ensembles de nombres qu'elle ne permet pas de définir et qui peuvent être nécessaires pour prouver certaines vérités sur les nombres. Un énoncé vrai sur les nombres est improuvable lorsque la théorie ne permet pas de définir l'ensemble de nombres dont on a besoin pour le prouver. La suite montrera que pour l'énoncé vrai et improuvable de Gödel, l'ensemble qui manque est l'ensemble des numéros des vérités arithmétiques.

Le théorème d'indéfinissabilité de la vérité de Tarski[modifier | modifier le wikicode]

On peut dire la vérité en disant simplement ce qu'on a à dire, mais on peut aussi la dire en insistant d'une façon redondante et en disant que ce qu'on dit est vrai. Nous nous servons d'un prédicat de vérité que nous pouvons attribuer ou non à tout ce que nous disons. Tarski (1933) a prouvé qu'un tel prédicat de vérité ne peut pas exister dans une théorie mathématique si elle est vraie.

Commençons par raisonner comme plus haut sur une théorie T qui parle de ses propres formules.

Si T contenait un prédicat de vérité Il est vrai que, alors les formules Il est vrai que f si et seulement si f seraient vraies pour toutes les formules f de T. Il est vrai que la neige est blanche si et seulement si la neige est blanche, par définition de la vérité. C'est avec ce principe que Tarski a fondé une théorie de la vérité mathématique (Tarski 1933) que l'on comprend aujourd'hui comme la théorie des modèles.

Montrons par l'absurde qu'un prédicat de vérité ne peut pas exister dans la théorie T si elle est vraie.

Supposons qu'un prédicat est vraie soit défini dans T pour toutes les formules de T.

Définissons la formule Tarski(f) à une variable libre par f est une formule à une variable libre et il existe une formule g telle que g n'est pas vraie et g est obtenue à partir de f par substitution de f à toutes les occurrences de sa variable libre.

Tarski(Tarski(f) veut dire par définition que Tarski(Tarski(f)) n'est pas vraie. Tarski(Tarski(f)) est vraie si et seulement si elle n'est pas vraie, ce qui est une absurdité. Donc le prédicat est vraie ne peut pas exister dans la théorie T si elle est vraie.

Pour transposer cette preuve à la théorie des nombres il suffit de raisonner sur le prédicat est le numéro d'une formule vraie. Une théorie des nombres ne permet jamais de définir un tel prédicat si elle est vraie.

Tarski est à la fois le théoricien qui a su définir la vérité mathématique et qui a prouvé qu'elle est indéfinissable dans toutes les théories mathématiques.

Le théorème de Tarski fournit une autre preuve, indirecte, du premier théorème d'incomplétude de Gödel : si une théorie permet de définir un prédicat de sa propre prouvabilité et si tous ses théorèmes sont vrais, alors il doit y avoir au moins un énoncé vrai et improuvable, sinon le prédicat de prouvabilité serait un prédicat de vérité.

Comment prouver l'improuvable ?[modifier | modifier le wikicode]

Revenons à la théorie T qui permet de définir un prédicat de prouvabilité est prouvable dans T et un énoncé vrai et improuvable dans T. En présentant cet énoncé "improuvable" nous avons prouvé qu'il était vrai. La preuve est facile mais elle repose sur l'hypothèse que la théorie T est elle-même vraie. Or la théorie T ne permet pas de définir un prédicat de vérité pour elle-même, si elle est vraie, seulement un prédicat de prouvabilité. On ne peut donc pas formaliser la preuve informelle de l'énoncé "improuvable" avec les moyens de la théorie T. C'est pourquoi cet énoncé prouvable est improuvable dans T. Mais la définition de la vérité mathématique par Tarski permet de définir une théorie T+ avec un prédicat de vérité limité à T : est une formule vraie de T. La preuve informelle de l'énoncé vrai et improuvable dans T peut alors être formalisée dans T+. L'énoncé improuvable dans T est donc un théorème prouvé dans T+. Mais bien sûr T+ n'est pas une théorie complète, parce qu'on peut trouver un nouvel énoncé vrai et improuvable dans T+ qui requiert un prédicat de vérité limité à T+ pour être prouvé.

Pour formaliser dans T+ la preuve informelle, on doit prouver dans T+ que tous les théorèmes de T sont vrais. On le prouve en raisonnant par récurrence. Si un ensemble de formules contient tous les axiomes de T et toutes les conséquences logiques immédiates de ses éléments alors il contient tous les théorèmes de T, par définition de l'ensemble des théorèmes de T. Il suffit donc de prouver que tous les axiomes de T sont vrais, et que les conséquences logiques immédiates de formules vraies sont également vraies, pour prouver que tous les théorèmes de T sont vrais. Mais pour formaliser cette preuve informelle on a besoin dans T+ d'un prédicat de vérité pour les formules de T.

Pour transposer cette preuve à la théorie des nombres il suffit de raisonner sur le prédicat est le numéro d'une formule vraie de la théorie. On peut toujours enrichir une théorie arithmétique avec de nouveaux axiomes pour que ce prédicat de vérité, limité à la théorie initiale, soit définissable. On peut ainsi prouver dans la théorie enrichie l'énoncé vrai et improuvable dans la théorie initiale. Il suffit de formaliser la preuve informelle.

Les preuves de cohérence[modifier | modifier le wikicode]

Une théorie est cohérente, ou non-contradictoire, ou consistante, lorsqu'elle ne permet jamais de prouver à la fois une formule et sa négation, sinon elle est incohérente, contradictoire, absurde, inconsistante.

Bien sûr on attend d'une théorie mathématique qu'elle soit cohérente. Une théorie incohérente ne permet pas de faire la différence entre le vrai et le faux.

Pour prouver qu'une théorie est cohérente, la façon la plus directe est simplement de prouver qu'elle est vraie, c'est à dire que tous ses théorèmes sont vrais. Une théorie vraie ne peut pas être incohérente, parce que si une formule est vraie, sa négation est fausse et n'est donc pas vraie.

Pour prouver que tous les théorèmes d'une théorie sont vrais, il suffit de prouver que tous ses axiomes sont vrais, parce que les conséquences logiques des formules vraies sont toujours vraies.

La vérité mathématique d'une formule est toujours définie à partir d'un modèle, un être théorique qui existe en tant qu'être pensé. Être mathématiquement vrai, c'est être vrai d'un modèle mathématique.

Pour prouver qu'une théorie est cohérente, il suffit donc de prouver que ses axiomes sont vrais pour un modèle théorique.

Avec cette méthode, on prouve facilement d'une façon informelle que les axiomes d'une théorie des nombres, les axiomes de Peano par exemple, sont cohérents. Mais on ne peut pas formaliser cette preuve à l'intérieur de la théorie dont on prouve la cohérence, parce qu'elle ne peut pas avoir de prédicat de vérité pour elle-même. De fait, Gödel a prouvé qu'une théorie cohérente ne peut jamais prouver sa propre cohérence. Ce second théorème d'incomplétude de Gödel est souvent interprété à tort. On croit que les preuves de cohérence sont très difficiles, ou inaccessibles, ou qu'elles ne pourraient jamais être rationnellement justifiées parce qu'elles seraient dans un cercle vicieux. Mais il y a une explication beaucoup plus directe. Les preuves de cohérence sont parfois très faciles à trouver, et irréfutables, sans aucune erreur de logique, et sans que le moindre doute puisse subsister, mais elles ne peuvent pas être formalisées à l'intérieur de la théorie dont la cohérence est prouvée, parce qu'elles requièrent un prédicat de vérité pour cette théorie. Le théorème de Tarski de l'indéfinissabilité d'un prédicat de vérité explique donc le second théorème d'incomplétude de Gödel.

Le second théorème d'incomplétude de Gödel[modifier | modifier le wikicode]

Une théorie vraie ne peut pas prouver sa propre cohérence.

Raisonnons sur la théorie T et son énoncé vrai et improuvable dans T, Gödel(Gödel(f)).

Montrons par l'absurde que T ne peut pas prouver sa propre cohérence. Si elle le pouvait elle pourrait prouver que Gödel(Gödel(f)) et non Gödel(Gödel(f)) n'est pas prouvable dans T.

Or elle peut prouver Si non Gödel(Gödel(f)) alors (Gödel(Gödel(f)) est prouvable dans T) par définition de Gödel(f). Elle pourrait donc prouver Si non Gödel(Gödel(f)) alors (non Gödel(Gödel(f)) n'est pas prouvable dans T). Mais non Gödel(Gödel(f)) veut dire que Gödel(Gödel(f)) est prouvable dans T par définition de Gödel(f). Donc T pourrait prouver Si non Gödel(Gödel(f)) alors ((Gödel(Gödel(f)) est prouvable dans T) n'est pas prouvable dans T.

En outre T peut prouver que Pour toute formule f, si f est prouvable dans T alors la formule qui affirme que f est prouvable dans T est prouvable dans T. C'est un point parfois considéré comme difficile dans la preuve de Gödel. Mais pour la théorie T il est presque évident, parce qu'en donnant une preuve d'un théorème on prouve en même temps qu'il est prouvable. Comme T peut prouver Si non Gödel(Gödel(f)) alors (Gödel(Gödel(f)) est prouvable dans T), elle peut aussi prouver Si non Gödel(Gödel(f)) alors ((Gödel(Gödel(f)) est prouvable dans T) est prouvable dans T).

Comme T pourrait tirer des conclusions contradictoires à partir de non Gödel(Gödel(f)), elle pourrait prouver Gödel(Gödel(f)) par l'absurde. Mais Gödel(Gödel(f)) affirme d'elle-même qu'elle n'est pas prouvable dans T. Donc T ne serait pas vraie.

Il en résulte que T ne peut pas prouver sa propre cohérence si elle est vraie.

On peut transposer ce raisonnement à la théorie des nombres en numérotant les formules.

La science de tout ce qui peut être imaginé[modifier | modifier le wikicode]

On imagine toujours en attribuant des concepts. L'imagination visuelle par exemple attribue des qualités visuelles (couleur, luminosité ...) à tout ce qui est imaginé. Les êtres qu'on se représente et les concepts qu'on leur attribue, y compris les relations, définissent une structure mathématique. De façon générale une structure, ou un système, ou un modèle, mathématique est défini par l'ensemble de ses constituants, ou des êtres qui lui appartiennent, et par des concepts et des relations qu'on leur attribue. Comme les mathématiques donnent les moyens de connaître tous les modèles mathématiques, elles permettent d'étudier n'importe quel ensemble d'êtres imaginés à partir des concepts que l'imagination leur attribue, elles sont la science de tout ce qui peut être imaginé, ou conçu.

La théorie des ensembles de Zermelo[modifier | modifier le wikicode]

Les ensembles sont omniprésents en mathématiques. Un concept peut toujours être associé à l'ensemble des êtres pour lesquels il est vrai, l'extension du concept. Le concept de nombre pair définit l'ensemble des nombres pairs. La relation est plus grand que entre nombres définit l'ensemble de tous les couples de nombres (x,y) tels que x est plus grand que y.

Les nombres ne sont en général pas considérés comme des ensembles, les constituants des modèles non plus. Une théorie mathématique devrait donc inclure à la fois des êtres de base, les nombres et les autres constituants des modèles qui ne sont pas des ensembles, et tous les ensembles qu'on peut construire à partir d'eux. Mais il est plus commode de définir une théorie pure des ensembles. Cela simplifie les axiomes.

Les nombres naturels peuvent être définis comme des ensembles. On peut par exemple identifier 0 à l'ensemble vide {}, 1 à {0}, 2 à {0,1} et plus généralement n à {0...n-1}. Tous les autres nombres peuvent être construits à partir des nombres naturels. Tous les constituants des modèles peuvent toujours être numérotés par des nombres naturels, ou identifiés à des systèmes de nombres, ou à des ensembles construits à partir des nombres. Une théorie pure des ensembles permet donc en principe d'étudier tout ce qui peut être imaginé.

Pour faire une théorie on a besoin d'axiomes qui permettent de prouver l'existence des êtres sur lesquels on raisonne. Un nombre réduit de principes (Zermelo 1908) suffit pour prouver l'existence de tous les êtres mathématiques sur lesquels on raisonne habituellement :

  • L'axiome de l'ensemble vide : Il existe un ensemble vide.
  • L'axiome de la paire : Si deux ensembles existent, l'ensemble qui les contient tous les deux, et seulement eux, existe aussi.
  • L'axiome de la somme : Si un ensemble existe, l'ensemble de tous les éléments de ses éléments existe aussi.
  • L'axiome de l'infini : Il existe un ensemble qui contient tous les nombres naturels.
  • L'axiome de séparation : Si E est un ensemble et si A(x) est une formule sensée qui porte sur les ensembles alors l'ensemble de tous les x dans E tels que A(x) est vraie existe.
  • L'axiome de l'ensemble des parties : Si un ensemble existe, l'ensemble de toutes ses parties, ou sous-ensembles, existe aussi.
  • L'axiome du choix : Il sera présenté plus loin.

Il faut leur ajouter :

  • L'axiome d'extensionnalité : Deux ensembles sont égaux lorsqu'ils ont les mêmes éléments.

et bien sûr les principes logiques, et on a des fondements suffisants pour prouver la plupart des vérités mathématiques.

Les trois premiers axiomes permettent de construire les nombres naturels. La réunion de deux ensembles est la somme de leur paire. Le successeur d'en ensemble x est la réunion x U {x}. On définit alors : 0 = {}, 1 = 0 U {0} = {0}, 2 = 1 U {1} = {0,1} ...

Le quatrième et le cinquième axiome permettent de prouver l'existence de l'ensemble N des nombres naturels. C'est l'ensemble qui contient tous les nombres naturels et qui est inclus dans tous les ensembles qui contiennent tous les nombres naturels. On retrouve ainsi le principe du raisonnement par récurrence comme une conséquence de la définition de l'ensemble des nombres naturels.

A partir de là, le sixième axiome permet de construire la hiérarchie des premiers ensembles infinis : N, l'ensemble P(N) des parties de N, P(P(N))=P2(N), P(P(P(N)))=P3(N) ...

Ces axiomes ne permettent pas de définir tous les ensembles. En particulier, l'existence de l'ensemble {N, P(N), P(P(N)) ...} qui contient tous les Pn(N) pour tous les nombres naturels n ne peut pas être prouvée à partir des axiomes de Zermelo. Elle peut être prouvée avec un nouvel axiome, l'axiome de remplacement, proposé par Fraenkel (1922), beaucoup plus puissant pour prouver l'existence des grands ensembles infinis. Mais même avec ce nouvel axiome, il reste des ensembles que la théorie ne permet pas de définir.

Pour les mathématiques ordinaires, et même pour les mathématiques d'un niveau très avancé, la théorie de Zermelo est plus que suffisante pour construire tous les ensembles qu'on veut construire et pour prouver tout ce qu'on veut prouver. En particulier, les nombres réels, les espaces construits à partir des nombres réels, les fonctions qui y sont définies, les espaces de ces fonctions, les fonctionnelles, et donc tous les objets de l'analyse, peuvent tous êtres construits en se limitant aux premiers niveaux de la hiérarchie des ensembles infinis. Les grands ensembles infinis que la théorie de Zermelo ne permet pas de construire sont beaucoup plus rarement utilisés.

L'interprétation de l'axiome de séparation pose une difficulté. Qu'est-ce qu'une formule sensée ? Selon Fraenkel et Skolem, toute formule bien formée à partir des prédicats fondamentaux est élément de et est égal à, et des connecteurs logiques, est une formule sensée. L'axiome de séparation peut donc toujours leur être appliqué. Mais Zermelo n'a pas été convaincu par cette approche, parce que ces formules dites sensées peuvent contenir des affirmations sur tous les ensembles, comme si l'univers de tous les ensembles avait une existence objective. Mais nous ne savons pas ce que pourrait être un tel univers. Nous ne savons donc pas toujours quel sens donner aux formules qui servent à construire les ensembles dans la théorie ZFC proposée par Fraenkel et Skolem.

Cette difficulté n'est pas gênante pour les mathématiques courantes, parce qu'on se limite aux "petits" ensembles infinis. On peut exiger des formules sensées auxquelles l'axiome de séparation est appliqué qu'elles ne contiennent que des quantificateurs bornés, c'est à dire qu'elles ne contiennent pas d'affirmations sur tous les ensembles, mais seulement sur tous les éléments d'ensembles déjà définis. Avec ces limitations, et sans l'axiome de remplacement, on n'a pas toute la puissance de ZFC, mais on a une puissance bien suffisante pour les mathématiques courantes, et on sait mieux de quoi on parle.

Le paradoxe de Russell[modifier | modifier le wikicode]

Au lieu de l'axiome de séparation, on aurait pu songer à un axiome plus simple :

Si A(x) est une formule sensée alors l'ensemble de tous les x tels que A(x) existe.

Cet axiome a été proposé par Frege (1879) pour fonder toutes les mathématiques, mais Russell (1901, publié en 1903) s'est rendu compte qu'il conduisait à une contradiction. x n'est pas élément de x est une formule sensée. En général les ensembles ne sont pas éléments d'eux-mêmes, mais il pourrait y avoir des exceptions, comme l'ensemble de tous les ensembles. L'ensemble de tous les x tels que x n'est pas élément de x, de tous les ensembles qui ne sont pas éléments d'eux-mêmes, existe, si on adopte l'axiome de Frege. Est-il élément de lui-même ? De sa définition il résulte qu'il est élément de lui-même si et seulement si il n'est pas élément de lui-même. C'est une absurdité, donc il ne peut pas exister, donc l'axiome de Frege est faux.

Le théorème de Cantor prouve qu'une théorie des ensembles ne peut jamais définir tous les ensembles, parce qu'elle ne peut en définir qu'un nombre dénombrable. Le théorème de Tarski prouve qu'une théorie des ensembles ne peut jamais définir l'ensemble de toutes ses vérités. Le paradoxe de Russell prouve qu'une théorie des ensembles ne peut jamais définir tous les ensembles, parce qu'elle ne peut jamais définir l'ensemble de tous les ensembles qu'elle peut définir et qui ne sont pas éléments d'eux-mêmes.

En général, une théorie des ensembles ne définit pas l'ensemble de tous les ensembles qu'elle peut définir, parce qu'on exige habituellement que les ensembles soient bien fondés, c'est à dire qu'ils ne sont ni éléments d'eux-mêmes, ni éléments de leurs éléments, ni ... ainsi de suite. Mais on peut aussi faire une théorie d'ensembles qui ne sont pas tous bien fondés et qui accueille l'ensemble de tous les ensembles qu'elle peut définir. Le paradoxe de Russell nous avertit que même une telle théorie ne peut pas définir tous les ensembles.

Le théorème de Tarski et le paradoxe de Russell sont très semblables. La formule Tarski(f) affirme que f n'est pas vraie d'elle-même. Comme Tarski(f) peut être identifiée à l'ensemble des f pour lesquelles elle est vraie, la preuve du théorème de Tarski est presque identique à la preuve que l'ensemble de tous les ensembles qui ne sont pas dans eux-mêmes ne peut pas exister.

La vérité des axiomes de Peano[modifier | modifier le wikicode]

Pour les mathématiques ordinaires on peut souvent se contenter d'une théorie beaucoup moins puissante que celle de Zermelo, simplement l'arithmétique élémentaire, la théorie des nombres naturels. Dedekind (1888) et Peano (1889) ont donné des systèmes d'axiomes suffisants pour prouver la plupart de ses théorèmes. L'arithmétique à la façon de Peano peut être considérée comme la théorie mathématique la plus fondamentale. Et elle suffit pour prouver une grande partie des plus grands théorèmes, parce que les théorèmes sur les nombres réels peuvent être traduits en théorèmes sur les nombres naturels.

Les axiomes de Peano :

  • 0 est un nombre naturel.
  • Un nombre naturel n a toujours un unique successeur sn qui est aussi un nombre naturel.
  • Un nombre naturel est toujours différent de son successeur.
  • Deux nombres naturels différents ont des successeurs différents.
  • 0 n'est le successeur d'aucun nombre naturel.

Pour tous les nombres naturels n et p :

  • leur somme n+p existe et est unique, de même pour leur unique produit n.p
  • n+0=0+n=n
  • n+sp=sn+p=s(n+p)
  • 0.n=n.0=0
  • n.sp=n.p+n
  • sn.p=n.p+p
  • Tout ensemble de nombres naturels qui contient 0 et qui contient toujours le successeur de chacun de ses éléments contient tous les nombres naturels.

On définit un modèle d'une théorie en définissant un ensemble de vérités atomiques. Une formule est atomique lorsqu'elle ne contient pas de connecteurs logiques. Les formules atomiques de l'arithmétique de Peano sont les égalités entre expressions numériques et les formules qui affirment qu'elles sont des nombres naturels. Une expression numérique est formée à partir de 0, s, + et .

Par exemple ss0+ss0=ssss0 (2+2=4) est une formule atomique, et elle est vraie. Il en va de même pour s0+(ss0.ss00) est un nombre naturel.

L'ensemble de toutes les égalités numériques vraies peut être construit de nombreuses façons. C'est un peu laborieux, parce qu'il faut se donner suffisamment de règles pour engendrer toutes ces vérités élémentaires, sans en oublier aucune, mais ce n'est pas très difficile, parce que c'est très élémentaire. N'importe quel ordinateur sait faire très facilement la différence entre les égalités vraies et les autres. Il est donc clair que cet ensemble de vérités atomiques existe. Il est également clair que tous les axiomes de Peano sont vrais pour ce modèle, sauf peut-être le dernier, qui pose une difficulté d'interprétation.

Pour faire de l'arithmétique on a besoin de raisonner sur les ensembles de nombres naturels. On peut donc songer à compléter les axiomes de Peano par des axiomes sur l'existence des ensembles de nombres, mais cela n'est pas nécessaire. Les formules arithmétiques à une variable libre suffisent pour nommer des ensembles de nombres. Par exemple la formule A(n) définie par Il existe p tel que n=2.p nomme l'ensemble de tous les nombres pairs. En appliquant le dernier axiome à toutes ces formules arithmétiques qui définissent des ensembles, on définit l'arithmétique de Peano au premier ordre. Il est facile de montrer que toutes les formules ainsi prises comme axiomes sont nécessairement vraies pour le modèle défini ci-dessus. On peut donc conclure que tous les axiomes de Peano sont vrais pour notre modèle. Comme une théorie vraie est nécessairement cohérente, on a prouvé du même coup la cohérence des axiomes de Peano.

La vérité des axiomes de Zermelo[modifier | modifier le wikicode]

On peut définir un modèle des axiomes de Zermelo en prenant comme univers d'ensembles l'ensemble M défini comme suit :

Soit S(x) = x U P(x), la réunion de x et de l'ensemble de ses parties. M est la réunion de N avec S(N), S(S(N)) ... c'est à dire de tous les Sn(N) pour tout nombre naturel n.

Montrons que tous les axiomes sont vrais pour cet univers M d'ensembles.

De la définition de M, il résulte immédiatement que l'axiome de l'ensemble vide et l'axiome de l'infini y sont vrais.

Comme Sn(N) est inclus dans Sn+1(N), Sn(N) est inclus dans Sp(N) si n<p.

Soient x et y deux éléments de M. On doit donc avoir n et p tels que x est élément de Sn(N) et y est élément Sp(N). Si n<=p, x et y sont tous les deux dans Sp(N) et leur paire est donc dans Sp+1(N). Si n>=p, {x,y} est dans Sn+1(N). L'axiome de la paire est donc vrai dans M.

Montrons par récurrence qu'un élément d'un élément de Sp(N) est aussi élément de Sp(N). L'énoncé est vrai pour N=S0(N) parce que tout nombre naturel n={0 ... n-1}. Comme les éléments des éléments de P(x) sont dans x, l'énoncé est vrai pour Sn+1(N) s'il est vrai pour Sn(N), donc il est vrai pour tout nombre naturel n.

Il en résulte que la somme d'un élément de Sn(N) est incluse dans Sn(N) et est donc un élément de Sn+1(N). L'axiome de la somme est donc vrai dans M.

Il en résulte également que les parties d'un élément de Sn(N) sont toutes incluses dans Sn(N) et donc toutes éléments de Sn+1(N). L'ensemble des parties d'un élément de Sn(N) est donc inclus dans Sn+1(N) et est donc un élément de Sn+2(N). L'axiome de l'ensemble des parties est donc vrai dans M.

L'axiome de séparation est nécessairement vrai dans M, puisque toutes les parties des éléments de M sont des éléments de M.

La vérité dans M de l'axiome du choix sera montrée un peu plus loin.

De la vérité de ses axiomes pour l'ensemble M, on peut conclure que la théorie de Zermelo est cohérente. Il y a cependant une différence entre cette preuve de cohérence et la précédente, sur la cohérence de l'arithmétique. On n'a pas construit explicitement l'ensemble des vérités atomiques. On n'a pas nommé tous les éléments du modèle et on n'a pas dit comment engendrer l'ensemble des formules atomiques vraies pour tous ces éléments. On ne peut pas le faire, parce que l'ensemble M est indénombrable.

Faut-il en conclure que cette preuve de cohérence est sans valeur ? Non. Mais elle éveille un doute. Sommes-nous bien sûr que l'ensemble que nous construisons existe ? Parler d'ensembles dont on ne peut même pas nommer tous les éléments, n'est-ce pas prendre le risque de l'absurdité ?

Nous savons que les ensembles indénombrables existent parce que nous pouvons y penser. Rien n'interdit de penser à l'ensemble de tous les ensembles de nombres naturels. On peut même le voir en imagination :

L'arbre binaire infini est construit en partant d'une racine, qui se sépare en deux branches, l'une à gauche, l'autre à droite, qui à leur tour se séparent en deux branches, et ainsi de suite à l'infini. Un chemin qui part de la racine et ne s'arrête jamais définit un ensemble de nombres naturels. Si à l'étape n le chemin prend la branche à gauche alors n fait partie de l'ensemble, mais pas si le chemin prend la branche à droite. L'ensemble de tous les chemins de l'arbre binaire infini est donc une représentation de l'ensemble de tous les ensembles de nombres naturels. Or on peut voir en imagination l'arbre binaire infini en le regardant se déployer à l'horizon. On peut donc voir tous ses chemins d'un seul coup d'œil, et ils sont indénombrables.

Il y a un nombre indénombrable de points sur une ligne, même si elle est de longueur finie. Comme on peut voir des lignes et des surfaces, on peut voir l'indénombrable.

Pour que la preuve de cohérence des axiomes de Zermelo soit fausse, il faudrait que nous ayons tort de concevoir les ensembles indénombrables, qu'à notre insu les raisonnements sur l'indénombrable nous conduisent à l'absurdité. Mais pourquoi craindre qu'on puisse être ainsi dupé par notre propre raison ? Il semble bien qu'on ne commet aucune erreur quand on raisonne sur l'ensemble des parties d'un ensemble, même s'il est infini.

La preuve de cohérence des axiomes de Zermelo peut être formalisée dans ZFC, parce que l'axiome de remplacement permet de définir M dans ZFC. Mais on n'a pas besoin d'un axiome aussi fort pour formaliser cette preuve. Il suffit d'ajouter aux axiomes de Zermelo un élargissement de l'axiome de l'infini : Il existe un ensemble qui contient N et qui contient toujours x U P(x) quand il contient x. On obtient ainsi une théorie plus puissante qui permet de prouver la cohérence de la précédente. Si on veut prouver la cohérence de cette nouvelle théorie, il suffit de se donner un nouvel axiome de l'infini : Il existe un ensemble qui contient M et qui contient toujours x U P(x) quand il contient x. On peut définir ainsi une suite de théories toujours plus puissantes telles que la cohérence de l'une peut toujours être prouvée par la suivante.

La cohérence de ZFC peut elle aussi être prouvée en exhibant un modèle indénombrable, mais il est plus difficile à construire, parce que l'axiome de remplacement permet de construire des ensembles infinis beaucoup plus grands.

Il est en principe possible, et souhaitable, de donner une autre preuve de la cohérence des axiomes ensemblistes, en contruisant explicitement un modèle dénombrable, en définissant explicitement l'ensemble de ses vérités atomiques. On sait que c'est possible en principe parce que Löwenheim (1915) et Skolem ont prouvé que toute théorie cohérente admet un modèle dénombrable, mais jusqu'à présent, personne à ma connaissance n'a réussi à en trouver un pour la théorie de Zermelo, ni a fortiori pour ZFC.

L'axiome du choix[modifier | modifier le wikicode]

La façon la plus directe de prouver qu'un ensemble existe est de le définir, ce qui revient à le construire à partir d'ensembles déjà définis. L'ensemble vide suffit pour amorcer la construction de tous les ensembles que nous définissons. Mais on peut aussi donner des preuves indirectes d'existence. On prouve qu'un ensemble existe et a certaines propriétés sans le définir explicitement, sans le construire, sans dire précisément de quel ensemble on parle. Le raisonnement par l'absurde permet de donner ces preuves indirectes d'existence. On commence par supposer qu'aucun ensemble ne vérifie les propriétés demandées et on en déduit une contradiction. On est alors en droit de conclure qu'il existe au moins un ensemble qui a les propriétés demandées, mais on ne s'est pas donné la peine de le construire.

Ces preuves indirectes d'existence nous permettent de prouver qu'on peut toujours faire un nombre fini de choix arbitraires pour prouver l'existence d'un ensemble. Plus précisément, si on a une liste finie d'ensembles non-vides et disjoints, on peut prouver qu'il existe au moins un ensemble qui contient un élément et un seul de chacun des ensembles de la liste. On n'a pas construit ce nouvel ensemble, on n'a pas choisi ses éléments, on s'est contenté de prouver qu'il existe. Les principes logiques et les axiomes de construction d'ensembles finis suffisent pour prouver son existence. Mais si la liste d'ensembles non-vides et disjoints est infinie, ces principes et ces axiomes ne permettent pas de prouver l'existence d'un ensemble qui contient un élément et un seul de chacun des ensembles de la liste. L'axiome du choix affirme précisément qu'un tel ensemble existe (Zermelo 1904) :

L'axiome du choix : Si E est un ensemble d'ensembles non-vides et disjoints alors il existe un ensemble qui contient un élément et un seul de chacun des éléments de E.

Montrons que l'axiome du choix est vrai dans l'univers M d'ensembles. Si E est une ensemble d'ensembles non-vides et disjoints et s'il est dans Sn(N) alors l'ensemble qui choisit un élément de chacun des éléments de E est inclus dans Sn(N), puisque les éléments des éléments de E sont dans Sn(N), et il est donc un élément de Sn+1(N), donc dans M. Donc l'axiome du choix est vrai dans M.

Les preuves de cohérence sont-elles prises dans un cercle vicieux ?[modifier | modifier le wikicode]

Les preuves de cohérence qui exhibent une modèle sont formalisées dans une théorie T+ plus forte que la théorie T0 dont elles prouvent la cohérence, parce qu'elles définissent l'ensemble des vérités de T0 et que cet ensemble ne peut pas être défini dans T0. Si une théorie est absurde, toute théorie obtenue en rajoutant des axiomes est également absurde. Une théorie absurde peut tout prouver, une affirmation et son contraire, y compris que l'absurde n'est pas absurde. Notre méthode pour prouver la cohérence d'une théorie ne permet donc pas de faire la différence entre les théories cohérentes et les théories incohérentes, puisqu'une théorie "plus forte" qu'une théorie incohérente pourrait prouver qu'elle est cohérente. C'est pourquoi on croit parfois que de telles preuves ne prouvent rien, mais on se trompe.

On ne raisonne pas sur n'importe quelle théorie T0 dont on ignorerait tout. T0 est l'arithmétique de Peano ou la théorie de Zermelo, ou d'autres théories que l'on choisit pour fonder notre savoir mathématique. On sait d'avance que ces théories nous permettent de prouver des vérités, parce que sans elles nous n'aurions pas de savoir mathématique, et il semble assez clair que nous en avons. Si on est très pessimiste on peut craindre que nos théories formelles aient accueilli à notre insu des fautes de formulation qui pourraient conduire à des contradictions. Mais on ne doute pas que ces théories nous révèlent souvent la vérité, sauf si on renonce au savoir mathématique. Quand on prouve que les théories formelles sont vraies et cohérentes, on confirme ce que nous croyons déjà intuitivement. Et on se prouve à soi-même que nos facultés naturelles de raisonnement sont suffisantes pour raisonner correctement sur la raison. Ce n'est donc pas un cercle vicieux. C'est le cercle vertueux de la raison qui se comprend elle-même.

L'indépendance de l'hypothèse du continu[modifier | modifier le wikicode]

L'ensemble P(N) des parties de N, c'est à dire l'ensemble de tous les ensembles de nombres naturels, est strictement plus grand que N. Mais est-il le plus petit des ensembles strictement plus grands que N ? Cantor a conjecturé que oui, mais il n'a pas réussi à le prouver. Cette conjecture, que l'ensemble des ensembles de nombres naturels est le plus petit ensemble strictement plus grand que l'ensemble des nombres naturels, est appelée l'hypothèse du continu. Elle fait partie de la liste des grands problèmes que Hilbert a proposé en 1900 aux mathématiciens du XXe siècle.

Cohen (1963) a montré que cette hypothèse est indépendante des axiomes de ZFC, habituellement retenus pour fonder les mathématiques. Ni elle-même, ni sa négation, ne peuvent être prouvées à partir de ces axiomes.

On peut chercher de nouveaux axiomes pour prouver l'hypothèse du continu. L'axiome de constructibilité est un candidat, parce qu'il permet de prouver cette conjecture. Mais il n'est habituellement pas retenu, parce qu'il n'a pas le caractère d'évidence intuitive qu'on est en droit d'attendre d'un axiome. Il est un peu compliqué à formuler et sa signification est tout sauf claire, parce qu'il marie une approche constructiviste et une approche anticonstructiviste. Il exige que les ensembles soient construits étape par étape, comme le demandent les constructivistes, mais il autorise un nombre arbitrairement infini d'étapes, ce qui est habituellement interdit par les constructivistes.

On ne sait pas si l'hypothèse du continu peut être prouvée, ou réfutée, à partir de nouveaux axiomes dont la vérité serait évidente.

L'indépendance de l'hypothèse du continu est parfois appelée indécidabilité, mais il faut proscrire cet usage, parce qu'il incite à confondre l'indépendance d'une formule par rapport à des axiomes, qui est une indépendance relative, avec l'indécidabilité des problèmes et des ensembles, expliquée plus loin, qui est une indécidabilité absolue.

Les théories, les logiciels et les ensembles récursivement énumérables[modifier | modifier le wikicode]

Il existe une correspondance très étroite entre les théories mathématiques et les logiciels, les programmes informatiques. Quand on a défini explicitement une théorie, on peut toujours écrire un programme qui prouve tous ses théorèmes. Il suffit qu'il imprime d'une façon ordonnée tous les axiomes et toutes les conséquences logiques immédiates des formules qu'il a précédemment imprimées. Cette méthode de recherche de preuves n'a qu'un intérêt théorique. En pratique, l'ordinateur imprimerait un déluge de formules sans intérêt avant de trouver un théorème qui mérite d'être écrit. Et même avec les ordinateurs les plus puissants, il faudrait en général attendre un temps démesuré pour trouver ainsi des preuves ou des réfutations de conjectures intéressantes.

On peut donner plusieurs définitions, toutes équivalentes, des ensembles récursivement énumérables. Les conditions suivantes, choisies parmi de nombreuses autres, définissent toutes les trois l'énumérabilité récursive d'un ensemble E :

  • Toutes les vérités atomiques d'appartenance à E sont des théorèmes, des énoncés prouvables, d'une théorie explicite.
  • Il existe un logiciel qui répond toujours oui lorsqu'on lui présente le nom d'un élément de E, et qui ne répond pas, ou qui répond non, lorsqu'on lui présente le nom d'un être qui n'est pas dans E.
  • Il existe un nombre fini d'expressions de départ et un nombre fini de règles de production (Smullyan 1961) qui suffisent pour engendrer toutes les vérités atomiques d'appartenance à E.

L'ensemble des théorèmes d'une théorie explicite est toujours un ensemble récursivement énumérable. Si on présente un théorème à un logiciel chercheur de preuves, il finira toujours par reconnaître que c'est un théorème, parce qu'il examine toutes les preuves possibles, aussi longues soient-elles. Si on lui présente un non-théorème, il ne répondra pas, parce qu'il cherchera pour l'éternité une preuve qui n'existe pas.

Les ensembles et les problèmes indécidables[modifier | modifier le wikicode]

Les ensembles récursivement énumérables sont toujours dénombrables. Comme tous leurs éléments peuvent être nommés, on peut toujours définir leur complémentaire dans l'ensemble de tous les êtres nommés, dès qu'on s'est fixé un système de désignation.

Un ensemble est décidable lorsque lui-même et son complémentaire sont récursivement énumérables, sinon il est indécidable.

Un problème est indécidable lorsque l'ensemble de ses solutions est indécidable.

Un exemple d'ensemble indécidable est l'ensemble de toutes les vérités dans l'arithmétique de Peano. Le premier théorème d'incomplétude de Gödel prouve que cet ensemble de vérités n'est pas récursivement énumérable et donc pas décidable. S'il était récursivement énumérable, on pourrait trouver une liste complète d'axiomes qui suffise pour prouver toutes les vérités arithmétiques, mais Gödel a prouvé qu'une telle liste ne peut pas exister.

Dire qu'un problème est indécidable ne veut pas dire que nous sommes incapables de le résoudre, ni qu'il a des solutions que nous ne trouverons jamais, cela veut seulement dire qu'il n'existe pas de théorie explicitement définie qui apporte toutes les solutions du problème. Les théories que nous définissons ne peuvent résoudre un problème indécidable que partiellement, jamais totalement. Avec les problèmes indécidables, nous n'en aurons jamais fini, c'est la galère assurée pour l'éternité. Mais nous pouvons quand même chercher et trouver des solutions, et aucune solution n'est a priori inaccessible. Il suffit d'être suffisamment créatif pour inventer une théorie qui permette de la trouver.

L'incomplétude des principes mathématiques vient de l'existence des ensembles indécidables. Si tous les ensembles de vérités étaient récursivement énumérables, on pourrait donner des listes d'axiomes qui suffisent pour les trouver toutes. Mais l'indécidabilité montre que les ensembles de vérités ne sont pas toujours récursivement énumérables.

Machines et théories universelles[modifier | modifier le wikicode]

Un ordinateur programmable est une machine universelle, au sens où elle est capable d'exécuter tous les programmes concevables. Si le programme est écrit une fois pour toutes, en mémoire morte (ROM, Read Only Memory), l'ordinateur est seulement une machine particulière.

Une machine universelle peut faire tout ce que les autres machines, universelles ou particulières, peuvent faire. Il suffit de lui donner le programme. Toutes les machines universelles sont donc essentiellement équivalentes. Elles peuvent toutes faire exactement les mêmes choses.

En pratique, les ordinateurs sont limités par leur puissance de calcul et par leur espace de stockage. Mais la puissance de calcul n'est qu'un problème de rapidité et l'espace de stockage peut en principe être agrandi sans limites. Il suffit d'imaginer un ordinateur monté sur un robot qui se déplace dans une base de données qu'on peut toujours agrandir.

Une théorie universelle est une théorie qui permet de prouver tout ce que les autres théories permettent de prouver. Par exemple, la logique peut être formalisée comme une théorie universelle. Il suffit de se donner suffisamment d'axiomes pour que toutes les formules vraies de la forme C est une conséquence logique de P soient prouvable, pour toutes les formules bien formées C et P. Comme n'importe quel théorème de n'importe quelle théorie est toujours prouvé à partir d'une conjonction finie d'axiomes, la logique ainsi formalisée est une théorie universelle.

En prouvant que les relations logiques entre formules peuvent être représentées par des relations arithmétiques entre des nombres qui représentent les formules, Gödel a prouvé que l'arithmétique est elle aussi une théorie universelle, même si on la limite à l'arithmétique de Peano au premier ordre.

L'existence des théories universelles pose un paradoxe. Comme toute théorie explicite, une théorie U universelle ne peut pas prouver toutes les vérités. Ces vérités qu'elles ne peut pas prouver sont en principe prouvables dans une théorie plus riche U+, qui a davantage d'axiomes. Mais comme la théorie initiale U est universelle, elle peut prouver tout ce que U+ peut prouver, ce qui semble contraire à l'hypothèse que U+ est plus riche que U. En particulier, la preuve de cohérence de l'arithmétique du premier ordre peut être formalisée dans l'arithmétique du premier ordre, puisqu'elle peut être formalisée dans une théorie explicite et puisque l'arithmétique du premier ordre est une théorie universelle. Mais le second théorème d'incomplétude de Gödel semble interdire une telle possibilité.

L'explication de ce paradoxe est un peu subtile. La théorie U+ peut être formalisée dans U, mais U "ne sait pas" que U+ est un enrichissement de U, c'est à dire que U peut prouver que tous les théorèmes de U+ sont des théorèmes de U+ mais elle ne peut pas prouver que les théorèmes de U+ valent pour elle-même. U peut donc formaliser la preuve de sa propre cohérence sans le dire explicitement, sans affirmer qu'il s'agit de sa propre cohérence.

L'indécidabilité du problème de l'arrêt[modifier | modifier le wikicode]

Le problème de l'arrêt : Étant donnés une programme informatique et un état initial de la mémoire, l'ordinateur va-t-il s'arrêter et fournir une réponse, ou va-t-il tourner indéfiniment sans jamais donner de réponse ?

On a supposé que l'ordinateur n'est pas limité en espace de stockage et qu'il ne subit pas d'influence extérieure pendant qu'il calcule.

Turing a prouvé que le problème se l'arrêt est indécidable (1936).

L'ensemble des couples (programme, état initial) d'une machine qui s'arrête est récursivement énumérable, parce qu'un ordinateur peut simuler tous les autres. Si on lui présente un programme et un état initial, il n'a qu'à faire tourner le programme sur l'état initial et attendre qu'il s'arrête. S'il s'arrête, l'ordinateur répond qu'il s'arrête. S'il ne s'arrête pas, l'ordinateur ne s'arrête pas et ne répond pas.

En revanche l'ensemble des couples (programme, état initial) d'une machine qui ne s'arrête pas n'est pas récursivement énumérable. On le prouve par l'absurde. S'il était récursivement énumérable, il y aurait un programme P tel que pour tout couple (programme p, état initial i), la machine s'arrête et répond que p ne s'arrête pas à partir de i à chaque fois que c'est vrai. Un programme peut être écrit en mémoire et est donc lui aussi un état initial possible. A partir de P on pourrait alors écrire un programme P' tel que pour tout programme p, la machine s'arrête et répond que p ne s'arrête pas à partir de l'état initial p à chaque fois que c'est vrai. Et on pourrait donner P' comme état initial de la mémoire de la machine qui tourne avec P' . Cette machine va-elle s'arrêter ? Par construction, elle s'arrête si et seulement si elle ne s'arrête pas. C'est une absurdité. Donc P' ne peut pas exister, et donc P non plus. L'ensemble des couples (programme, état initial) d'une machine qui ne s'arrête pas n'est donc pas récursivement énumérable. Le problème de l'arrêt est donc indécidable.

L'indécidabilité de l'ensemble des lois logiques[modifier | modifier le wikicode]

L'ensemble des lois logiques est une théorie universelle, parce qu'une formule est une théorème d'une théorie si et seulement si l'affirmation qu'elle résulte d'une conjonction finie de ses axiomes est une loi logique. En connaissant toutes les lois logiques, on connaît donc tous les théorèmes de toutes les théories.

Lorsqu'une théorie est définie avec un nombre fini d'axiomes, une formule n'est pas un théorème si et seulement si l'affirmation qu'elle résulte de la conjonction des axiomes n'est pas une loi logique.

Les théories fondamentales (l'arithmétique de Peano, la théorie de Zermelo ...) sont en général définies avec des schémas d'axiomes. L'axiome de séparation par exemple est un schéma qui permet de formuler autant d'axiomes qu'il y a de formules sensées, en nombre infini. Il en va de même pour le principe du raisonnement par récurrence quand on le formule dans l'arithmétique du premier ordre. Mais ces théories qui ont un nombre infini d'axiomes sont toujours équivalentes à des théories qui n'en ont qu'un nombre fini. En introduisant des classes, qui sont comme des ensembles, mais trop grandes pour être vraiment considérées comme des ensembles, à la façon de Gödel et Bernays, la théorie de Zermelo n'a plus qu'un nombre fini d'axiomes.

Même quand les théories ont un nombre infini d'axiomes, on exige toujours qu'il y ait un nombre fini de principes ou de règles qui suffisent pour engendrer mécaniquement tous les axiomes, sinon la théorie n'est pas explicite. C'est pourquoi les théories explicites sont toujours équivalentes à des théories à nombre fini d'axiomes.

Si l'ensemble des lois logiques était décidable, tous les ensembles récursivement énumérables seraient décidables : Toutes les vérités d'appartenance à un ensemble E récursivement énumérable sont des théorèmes d'une théorie à nombre fini d'axiomes. Le complémentaire de E est donc l'ensemble de tous les x tels que Si les axiomes alors x est dans E n'est pas une loi logique. Si l'ensemble des lois logiques était décidable, cet ensemble serait récursivement énumérable, et donc E serait décidable.

La preuve de l'indécidabilité du problème de l'arrêt montre qu'il existe au moins un ensemble récursivement énumérable qui n'est pas décidable. L'ensemble des lois logiques n'est donc pas décidable.

La preuve du premier théorème d'incomplétude permet de prouver plus directement l'indécidabilité de l'ensemble des lois logiques. Si l'ensemble des lois logiques était décidable, la théorie T pourrait avoir assez d'axiomes pour prouver toutes les formules vraies de la forme f n'est pas une conséquence logique de g. Elle pourrait donc prouver toutes les formules vraies de la forme f n'est pas prouvable dans T. Comme Gödel(Gödel(f)) n'est pas prouvable dans T, elle pourrait le prouver. Mais Gödel(Gödel(f)) dit d'elle même qu'elle n'est pas prouvable dans T. T pourrait alors prouver que Gödel(Gödel(f)) n'est pas prouvable dans T, ce qui est absurde. Donc l'ensemble des lois logiques est indécidable.

L'indécidabilité de l'ensemble des lois logiques, ou de l' Entscheidungsproblem (Hilbert 1928) a été prouvée indépendamment et avec des méthodes différentes par Church et Turing en 1936.

L'universalité est la cause de l'indécidabilité[modifier | modifier le wikicode]

Les problèmes dont nous savons prouver l'indécidabilité sont toujours des problèmes complets, au sens où si nous avions une méthode pour trouver toutes leurs solutions, nous aurions du même coup une méthode pour résoudre tous les problèmes. De ce point de vue, l'incomplétude des principes mathématiques n'est finalement pas très étonnante. On n'est pas obligé de la voir comme un signe d'incapacité, parce qu'elle est une conséquence de l'universalité de la pensée. Nous pouvons raisonner sur tous les problèmes, sur toutes les théories. Nous pouvons énoncer des lois universelles qui valent pour tout ce qui est concevable et pensable. Mais nous n'avons pas de méthodes ou de principes qui suffisent pour résoudre tous les problèmes. Nos méthodes, même les plus puissantes, ne peuvent pas tout résoudre. Nous ne sommes que des créatures. Savoir trouver toutes les solutions d'un problème indécidable serait une sorte d'omniscience, parce qu'on saurait du même coup comment trouver toutes les solutions de tous les problèmes.

Une liste finie de principes suffit pour engendrer toutes les lois logiques. C'est le théorème de complétude de la logique de Gödel. L'ensemble des lois logiques est donc récursivement énumérable. Mais puisque l'ensemble des lois logiques est indécidable, l'ensemble des formules qui ne sont pas des lois logiques n'est pas récursivement énumérable. Les lois logiques sont vraies dans tous les mondes possibles. Les négations des lois logiques sont des absurdités, fausses dans tous les mondes possibles. Une formule qui n'est ni une loi logique, ni la négation d'une loi logique, est vraie dans certains mondes et fausse dans d'autres, elle décrit des mondes possibles, des mondes qu'on peut imaginer. Tout système fini d'axiomes qui décrit un monde possible est tel que la négation de sa conjonction n'est pas une loi logique. L'ensemble des formules qui ne sont ni des lois logiques, ni des absurdités est l'ensemble de tous les axiomes et de tous les systèmes finis d'axiomes qui portent sur au moins un monde qu'on peut imaginer. Dire qu'il n'est pas récursivement énumérable veut dire qu'on ne peut pas donner une liste finie de principes qui suffise pour engendrer toutes ces systèmes d'axiomes. L'imagination déborde tous les cadres. Quelle que soit la liste finie de principes qu'on se donne, il y a toujours des mondes possibles qu'elle ne permet pas d'étudier. L'incomplétude mathématique est donc une conséquence de l'universalité et de la puissance de l'imagination.