Précis d'épistémologie/Les fondements des mathématiques

Les mathématiques, ou la mathématique, peuvent être définies comme la science de tout ce qui est logiquement possible, tous les êtres et tous les concepts qui peuvent être étudiés dans une théorie. Pour qu'un être mathématique existe, il suffit qu'une théorie détermine correctement son existence, on ne demande pas qu'il existe dans la réalité tangible et observable.

Précis d'épistémologie

1. Mode d'emploi de la raison
2. L'esprit, comment ça marche ?
3. La recherche de la raison
4. Principes logiques
5. Les fondements des mathématiques
6. Les dispositifs de mesure spatio-temporelle
7. La théorie quantique des destinées multiples
8. Ordinateurs et consommation d'énergie
9. L'origine et l'évolution de la vie et de l'esprit
10. Principes de psychiatrie

Références

La logique du premier ordre donne les moyens de faire des théories avec un nombre fini de concepts fondamentaux appliqués à un domaine, fini ou non, d'individus. Pour raisonner avec les principes de la logique du premier ordre sur tous les concepts qu'on peut appliquer aux individus d'un domaine spécifié, il suffit de considérer les concepts (les propriétés et les relations) comme de nouveaux individus et de se donner une nouvelle relation d'attribution, qui relie les propriétés (les relations) aux individus auxquels elles sont attribuées (aux n-uplets d'individus). On peut ainsi fonder la logique du deuxième ordre et les logiques d'ordre supérieur. La théorie des ensembles est une façon plus simple de faire une théorie de tout ce qui est logiquement possible, tout en restant dans le cadre de la logique du premier ordre. Comme elle est un peu déroutante pour le débutant, ce chapitre commence par exposer une façon plus naturelle de fonder les mathématiques, en partant de la théorie des nombres naturels.

Les nombres naturels et les axiomes de Peano

Dedekind (1888) et Peano (1889) ont donné des systèmes d'axiomes suffisants pour prouver la plupart des théorèmes sur les nombres naturels. 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, même ceux du calcul différentiel et intégral, parce que les théorèmes sur les nombres réels peuvent être traduits en théorèmes sur les nombres naturels.

Dans le présent formalisme, tous les nombres naturels sont nommés à partir de 0 et d'un unique opérateur s (le successeur de) :

1=s0, 2=s1=ss0, 3=sss0, ...

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.
• 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
• 0+0=0
• n+sp=sn+p=s(n+p)
• 0.0=0
• n.sp=n.p+n
• sn.p=n.p+p

Le principe du raisonnement par récurrence (ou de l'induction infinie) :

• 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.

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. Avec de telles formules arithmétiques on peut définir de très nombreux ensembles de nombres naturels, assez pour la plupart des besoins théoriques, mais pas tous.

L'arithmétique de Peano est à la fois assez simple et très puissante. En raisonnant sur des nombres, on peut raisonner sur tous les ensembles d'êtres qu'on peut numéroter. Or quand on étudie un monde logiquement possible, la façon dont ses individus sont identifiés importe peu. Qu'ils soient numérotés ou représentés d'une autre façon ne change rien au monde logiquement possible étudié. Ce qui compte ce sont les concepts (les propriétés et les relations) attribués aux individus, pas la façon dont les individus sont identifiés. C'est pourquoi l'arithmétique de Peano est très puissante. Elle donne les moyens de raisonner sur de très nombreux mondes logiquement possibles.

La théorie des ensembles de Zermelo

La théorie des ensembles permet de faire la théorie de tous les concepts, parce qu'un concept peut être représenté par son extension, l'ensemble des êtres pour lesquels il est vrai. Le concept de nombre pair peut être représenté par l'ensemble des nombres pairs. La relation est plus grand que entre nombres peut être représentée par l'ensemble de tous les couples de nombres (x,y) tels que x est plus grand que y.

Pour faire une théorie des ensembles, le plus naturel est de partir d'êtres qui ne sont pas des ensembles, les nombres naturels par exemple, ou d'autres êtres, qu'on prend comme éléments des ensembles qu'on définit.

Une théorie pure des ensembles n'étudie que des ensembles. Tous les êtres dont l'existence est postulée par la théorie sont toujours des ensembles. C'est un peu déroutant pour le débutant. Comment peut-on faire des ensembles à partir de rien ? On part de l'ensemble vide {}, qui ne contient aucun élément. On peut ensuite définir de nouveaux ensembles : {{}}, { {}, {{}} } ...

Les nombres naturels peuvent être représentés par 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.

Pour étudier les mondes logiquement possibles, la façon dont les individus sont identifiés importe peu. On peut les représenter par des nombres, ou des systèmes de nombres ou des ensembles. Un monde logiquement possible n'est pas déterminé par la façon dont ses individus sont identifiés mais par les propriétés et les relations qu'il leur attribue. C'est pourquoi une théorie pure des ensembles permet de faire une théorie de tout ce qui est logiquement possible.

Une fonction (un opérateur) f peut être représentée par une relation : y=f(x), ou z=f(x,y) ...

Une relation peut être représentée par un ensemble de couples, ou de triplets, ou de n-uplets.

Un couple (x,y) peut être représenté par un ensemble, { {x}, {x,y} } par exemple. Un triplet peut être représenté à partir des couples : (x,y,z)=((x,y),z) par exemple. Il en va de même pour tous les n-uplets.

Comme une théorie pure des ensembles donne les moyens de représenter tous les individus, toutes les propriétés, toutes les relations, toutes les fonctions, elle donne les moyens de raisonner sur tout ce qui est logiquement possible.

Pour prouver l'existence de tous les nombres naturels, il suffit de postuler que 0 est un nombre naturel et que le successeur d'un nombre naturel est toujours un nombre naturel. Pour prouver l'existence des ensembles on procède d'une façon assez semblable, on part de l'ensemble vide {} et on prouve l'existence de nouveaux ensembles construits à partir d'ensembles dont on a déjà prouvé l'existence.

Les axiomes de Zermelo (1908)

• L'axiome d'extensionnalité : Deux ensembles sont égaux si et seulement s'ils ont les mêmes éléments.
• L'axiome de l'ensemble vide : Il existe un ensemble vide.
• L'axiome de la paire : Si deux ensembles existent, il existe un ensemble dont ils sont les deux seuls éléments.
• L'axiome de l'ensemble-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 bien définie 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é ci-dessous.

Le premier axiome est la caractéristique essentielle des ensembles. Si deux êtres sont différents alors qu'ils ont exactement les mêmes éléments alors ils ne sont pas des ensembles.

Les trois axiomes suivants permettent de construire les nombres naturels. La réunion de deux ensembles est l'ensemble-somme de leur paire. Le successeur d'un 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 cinquième axiome et le sixiè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.

À partir de là, le septième axiome permet de construire la hiérarchie des premiers ensembles infinis : N, l'ensemble P(N) des parties de N, P(P(N))=P²(N), P(P(P(N)))=P³(N) ...

L'axiome de séparation peut être comparé au ciseau d'un sculpteur. On construit des ensembles en se donnant de grands ensembles, comme de grands blocs de marbre, et on les taille au ciseau, avec l'axiome de séparation.

Pour formuler ces axiomes avec les moyens de la logique du premier ordre, il suffit de se donner deux relations fondamentales, la relation d'appartenance à un ensemble est élément de, et la relation d'égalité =, et de postuler que le domaine de tous les individus est le domaine de tous les ensembles (ou tous les ensembles qui nous intéressent).

• L'axiome d'extensionnalité : Pour tout x et tout y, x=y si et seulement si pour tout z (z est élément de x si et seulement si z est élément de y)
• L'axiome de l'ensemble vide : Il existe x tel que pour tout y, y n'est pas élément de x
• L'axiome de la paire : Pour tout x et tout y il existe z tel que pour tout w (w est élément de z si et seulement si (w=x ou w=y))
• L'axiome de l'ensemble-somme : Pour tout x il existe y tel que pour tout z (z est élément de y si et seulement si (il existe w tel que (w est élément de x et z est élément de w))

Pour formuler l'axiome de l'infini, on commence par définir la relation de succession entre ensembles : y est le successeur de x si et seulement si y=xU{x}

y=xU{x} si et seulement si pour tout z (z est élément de y si et seulement si (z est élément de x ou z=x))

L'existence du successeur de x pour tout ensemble x est garantie par l'axiome de la paire et l'axiome de la somme.

• L'axiome de l'infini : Il existe x tel que ({} est élément de x et pour tout y, si y est élément de x alors yU{y} est élément de x)
• L'axiome de séparation : Pour toute formule bien définie A(x) et tout y il existe z tel que pour tout w (w est élément de z si et seulement si (A(w) et w est élément de y))

Pour formuler l'axiome de l'ensemble des parties, on commence par définir la relation d'inclusion entre ensembles : x est inclus dans y, ou x est une partie de y, ou un sous-ensemble de y, si et seulement si tout élément de x est aussi un élément de y.

x est inclus dans y si et seulement si pour tout z, si z est élément de x alors z est élément de y

• L'axiome de l'ensemble des parties : Pour tout x il existe y tel que pour tout z (z est élément de y si et seulement si z est inclus dans x)

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 Pⁿ(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 bien définie? Selon Fraenkel, toute formule bien formée à partir des prédicats fondamentaux est élément de et est égal à, et des connecteurs logiques, est une formule bien définie. L'axiome de séparation peut donc toujours leur être appliqué. Mais ces formules dites bien définies 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 à définir les ensembles dans ZFC. Cette théorie conduit à prouver l'existence d'ensembles mal définis. Or un ensemble mal défini n'est pas un ensemble, il n'existe pas. Donc ZFC est fausse.

Pour corriger l'erreur de Fraenkel, il suffit d'exiger des formules bien définies 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 a une puissance bien suffisante pour les mathématiques courantes.

L'axiome du choix

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.

Les 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.

Le paradoxe de Russell

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

L'axiome de Frege : Si A(x) est une formule bien définie 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 bien définie. 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.

La théorie de Zermelo permet de définir des ensembles très grands mais quand même pas l'ensemble de tous les ensembles. Sinon, l'axiome de séparation permettrait de définir l'ensemble de tous les ensembles qui ne sont pas éléments d'eux-mêmes et la théorie serait contradictoire. On montrera plus loin qu'elle est vraie et donc cohérente. Elle ne permet donc pas de construire des ensembles paradoxaux qui la conduiraient à une contradiction.

Une théorie des ensembles ne permet pas en général de définir l'ensemble de tous les ensembles qu'elle permet de définir. Sinon cet ensemble serait élément de lui-même, et avec l'axiome de séparation, la théorie serait contradictoire, parce que l'ensemble de tous les ensembles définissables dans la théorie qui ne sont pas éléments d'eux-mêmes serait définissable dans la théorie. Si la théorie est bien définie, l'ensemble de tous les ensembles définissables dans la théorie est lui aussi bien défini, mais il n'est pas définissable dans la théorie. C'est une des raisons de l'incomplétude des fondements des mathématiques.

L'ensemble de tous les ensembles définissables dans la théorie de Zermelo n'est pas définissable dans la théorie de Zermelo, mais il est définissable dans une théorie plus puissante. Par exemple, l'axiome de remplacement donne les moyens de le définir.

L'infini indénombrable

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.

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.

L'indénombrabilité est une des raisons de l'incomplétude des fondements des mathématiques. Une théorie ne peut définir qu'un ensemble dénombrable d'ensembles, elle ne peut donc jamais définir tous les éléments d'un ensemble indénombrable, elle ne donne jamais les moyens de remplir complètement les ensembles indénombrables.

Deux ensembles ont le même cardinal lorsqu'il existe une bijection de l'un vers l'autre. Cela veut dire qu'on peut identifier tous les éléments de l'un par les éléments de l'autre. Une bijection de E vers F est une fonction qui a E pour domaine et qui est telle que chaque élément de F a un unique antécédent. Deux ensembles finis qui ont le même cardinal ont donc nécessairement le même nombre d'éléments. Le concept de cardinal généralise le concept de nombre d'éléments aux ensembles infinis. Deux ensembles, finis ou infinis, ont le même cardinal si et seulement si ils ont le même nombre d'éléments. Avec cette définition Cantor a fondé une théorie des nombres infinis.

Un ensemble est infini dénombrable lorsqu'il a le même cardinal que l'ensemble des nombres naturels.

Cantor a montré qu'un ensemble ne peut pas avoir le même cardinal que l'ensemble de ses parties. Il en a conclu qu'il y a de nombreux nombres infinis, pas seulement le nombre des nombres naturels.

Les ensembles bien ordonnés et l'induction infinie

Le concept de bon ordre permet de préciser le concept d'un processus dont chaque étape est déterminée dès que les étapes précédentes ont été franchies. Lorsqu'un tel processus est fini, chacune de ses n étapes peut être numérotée par les nombres naturels de 1 à n. Lorsqu'un processus est infini, chacune de ses étapes peut être identifiée par un élément d'un ensemble bien ordonné.

Un ensemble E est totalement ordonné si et seulement s'il existe une relation < telle que pour tous les x, y et z dans E,

• si (x<y et y<z) alors x<z
• si x<y alors non y<x
• x<y ou y<x ou x=y

Pour qu'un processus par étapes soit déterminé il faut que la première des étapes qui reste à franchir soit toujours déterminée. On exige donc pour l'ordre des étapes qu'un ensemble d'étapes ultérieures ait toujours un premier élément (ou un plus petit élément). Cela conduit à imposer à la relation d'ordre sur E la propriété suivante :

S'il n'est pas vide, l'ensemble des majorants stricts de toute partie de E a un premier élément.

(x est un majorant strict de y si et seulement si x est strictement plus grand (ou après) tous les éléments de y.)

On peut montrer que la propriété des majorants stricts est équivalente à la suivante (pour un ensemble totalement ordonné) :

Toute partie non-vide de E a un premier élément.

Un ensemble est bien ordonné si et seulement si (il est totalement ordonné et chacune de ses parties non-vides a un premier élément).

L'ensemble des nombres naturels est le plus petit ensemble infini bien ordonné pour sa relation d'ordre naturelle. On peut définir des ensembles bien ordonnés plus grands simplement en ajoutant des étapes après une succession infinie d'étapes.

Le principe du raisonnement par récurrence peut être généralisé à tous les ensembles bien ordonnés :

Si x est un ensemble qui contient le premier élément d'un ensemble bien ordonné y et qui contient toujours l'élément z de y quand il contient tous les éléments de y strictement avant z alors x contient tous les éléments de y.

On le prouve par l'absurde : s'il n'est pas vide, l'ensemble de tous les éléments de y qui ne sont pas dans x a un premier élément. L'existence de ce premier élément contredit l'une ou l'autre des conditions sur x. Donc l'ensemble de tous les éléments de y qui ne sont pas dans x est vide.

Deux ensembles bien ordonnés E et F représentent le même ordinal si et seulement si ils sont isomorphes, c'est à dire qu'il existe une bijection f de E sur F telle que x<y si et seulement si f(x)<f(y).

Comme les cardinaux, les ordinaux peuvent considérés comme des nombres, finis ou infinis. Mais l'arithmétique des ordinaux est plus fine que celle des cardinaux, parce que deux ensembles bien ordonnés infinis peuvent avoir le même cardinal tout en représentant des ordinaux très différents.

Comment les ensembles sont-ils bien définis ?

Hormis l'ensemble vide, tous les ensembles d'une théorie pure des ensembles sont définis à partir d'ensembles antérieurement définis. Les ensembles sont bien définis lorsqu'ils sont toujours définis en respectant les trois conditions suivantes :

• Pour un ensemble nouvellement défini, on doit pouvoir donner une liste bien ordonnée d'ensembles, finie ou infinie, telle que chaque ensemble de la liste soit défini à partir des ensembles antérieurement définis. Le premier élément de la liste est toujours l'ensemble vide. Le dernier élément de la liste est l'ensemble nouvellement défini.

• Les éléments d'un ensemble nouvellement défini doivent toujours être des ensembles antérieurement définis ou des parties d'ensembles antérieurement définis.

• Les vérités atomiques d'appartenance à un ensemble nouvellement défini doivent être déterminées par la définition de l'ensemble et les vérités atomiques d'appartenance aux ensembles antérieurement définis et à leurs parties.

À la place de la deuxième condition, on peut songer à une condition plus restrictive : les éléments d'un ensemble nouvellement défini doivent être des ensembles antérieurement définis. Mais cette condition pourrait empêcher de définir l'ensemble des parties d'un ensemble infini, parce qu'il est indénombrable. Comme l'ensemble des parties d'un ensemble bien défini est lui-même bien défini, il faut accepter qu'un ensemble bien défini puisse avoir pour éléments des ensembles qui n'ont pas été antérieurement définis.

L'axiome de Frege ne respecte pas la deuxième condition, parce que les éléments d'un ensemble nouvellement défini ne sont pas nécessairement des ensembles antérieurement définis ou des parties de tels ensembles.

Dans la formulation de Fraenkel (ZFC) l'axiome de séparation ne respecte pas la troisième condition, parce que l'usage des quantificateurs non-bornés fait que les vérités atomiques d'appartenance à un ensemble nouvellement défini sont déterminées par toutes les vérités atomiques d'appartenance à tous les ensembles, pas seulement par les vérités atomiques d'appartenance aux ensembles antérieurement définis. Pour respecter la troisième condition, il faut que tous les quantificateurs utilisés dans la définition d'un ensemble soient bornés par des ensembles antérieurement définis.

Tous les axiomes de construction d'ensembles proposés par Zermelo respectent les trois conditions, pourvu que les quantificateurs soient bornés dans la définition des ensembles construits avec l'axiome de séparation.

Quels sont les ensembles définissables dans la théorie de Zermelo ?

On peut définir tous les nombres naturels naturels à partir d'un nombre initial, zéro, et d'une fonction constructrice de nombres, le successeur de. De même on peut définir tous les ensembles définissables dans la théorie de Zermelo à partir d'ensembles initiaux et de constructrices d'ensembles. Les ensembles initiaux sont l'ensemble vide et l'ensemble de tous les nombres naturels. Les constructrices fondamentales sont la paire de, l' ensemble-somme de, l'ensemble des parties de et toutes les constructrices en nombre infini qu'on peut définir avec l'axiome de séparation, pourvu que les quantificateurs soient bornés dans la définition des ensembles. Les constructrices sont toutes les compositions finies de constructrices fondamentales. Les ensembles définissables dans la théorie de Zermelo sont tous ceux qu'on obtient en appliquant une de ces constructrice à l'ensemble vide et à l'ensemble des nombres naturels.

L'axiome de remplacement

Si R est une relation fonctionnelle bien définie entre ensembles et si E est un ensemble alors on peut remplacer tous les éléments de E par leur image fonctionnelle et obtenir ainsi un ensemble. Plus précisément il existe un ensemble qui contient tous les y tels qu'il existe x dans E tel que Rxy, et seulement eux.

Une relation est fonctionnelle lorsqu'elle associe toujours un seul élément au même élément : Pour tous x, y et z, si Rxy et Rxz alors y=z.

L'interprétation de l'axiome de Fraenkel pose une difficulté : quand est-ce qu'une relation fonctionnelle est bien définie ?

Dans la théorie ZFC, Fraenkel autorise les relations fonctionnelles définies avec des quantificateurs non-bornés, donc des relations fonctionnelles mal définies. Dans la version de Fraenkel, l'axiome de remplacement est donc faux. Pour appliquer correctement l'axiome de Fraenkel, on a besoin d'une théorie des relations fonctionnelles bien définies.

Une théorie des ensembles bien définis

La théorie de Zermelo est une théorie des ensembles bien définis, pourvu qu'on impose la règle des quantificateurs bornés dans les définitions qui construisent des ensembles avec l'axiome de séparation. Mais si on veut développer la théorie des ensembles infinis, elle n'est pas suffisante. ZFC est beaucoup plus puissante mais elle autorise des constructions mal définies.

On peut définir une théorie beaucoup plus puissante que celle de Zermelo qui n'autorise que des constructions bien définies en se servant des constructrices fondamentales et de leurs compositions finies.

Les constructrices de première espèce construisent des ensembles à partir d'ensembles déjà construits. Les constructrices fondamentales de la théorie de Zermelo (la paire de, l'ensemble-somme de, l'ensemble des parties de et toutes les constructrices qu'on peut définir avec l'axiome de séparation pourvu que tous les quantificateurs soient bornés dans la définition des ensembles) sont des constructrices de première espèce. Les compositions finies de constructrices de première espèce sont aussi des constructrices de première espèce. On introduit deux nouvelles constructrices fondamentales : l'ensemble-image par et l'ensemble obtenu par les itérations finies de, que l'on abrège en l'ensemble infini par. Ce sont des constructrices de deuxième espèce. Elles construisent des constructrices de première espèce à partir des constructrices de première espèce.

Si f est une constructrice de première espèce à un argument, l'ensemble-image par f de est une constructrice de première espèce qui pour tout ensemble x construit l'ensemble de tous les y tels qu'il existe z dans x tel que y=f(z). L'ensemble infini par f de x est l'ensemble dont les éléments sont x, f(x), f(f(x)), f(f(f(x))) ... pour toutes les itérations finies de f.

Une constructrice f peut être définie par une relation : f(x)=y ou f(x,y)=z ou ...

Montrons que toutes les constructrices de première espèce de la présente théorie peuvent être définies par des relations dans une théorie pure des ensembles.

{x,y}=z est défini par Pour tout w, w est élément de z si et seulement si (w=x ou w=y)

y est l'ensemble-somme de x est défini par Pour tout z, z est élément de y si et seulement s'il existe w tel que (w est élément de x et z est élément de w)

y est l'ensemble des parties de x est défini par Pour tout z, z est élément de y si et seulement si z est inclus dans x

Soit A(w, y₁ ... y_n) un énoncé dont toutes les variables libres sont w, y₁ ... y_n. On suppose qu'un quantificateur dans A(w, y₁ ... y_n) est toujours borné par l'un des y₁ ... y_n. L'axiome de séparation affirme que Pour tous les y₁ ... y_n et tout x, il existe z tel que pour tout w, w est élément de z si et seulement si (w est élément de x et A(w, y₁ ... y_n)). Cela revient à affirmer l'existence d'une constructrice f à n+1 arguments. f(x,y₁ ... y_n) = z est défini par Pour tout w, w est élément de z si et seulement si (w est élément de x et A(w, y₁ ... y_n)). Toutes les constructrices définies avec l'axiome de séparation sont donc définissables par des relations dans une théorie pure des ensembles.

Une constructrice obtenue par composition de constructrices définissables dans la théorie est elle aussi définissable dans la théorie. Par exemple g(f(x))=y peut être défini par Il existe z tel que f(x)=z et g(z)=y

Soit f une constructrice de première espèce à un argument et R la relation qui la définit : Rxy si et seulement si f(x)=y

y est l'ensemble-image par f de x est défini par Pour tout z (z est élément de y si et seulement si il existe w tel que (w est élément de x et Rwz))

x est clos pour R (ou pour f) est défini par Pour tout y et tout z si y est élément de x et Ryz alors z est élément de x

y est l'ensemble infini par f de x est défini par x est élément de y et y est clos pour R et pour tout z si (x est élément de z et z est clos pour R) alors y est inclus dans z

On en conclut que toutes les constructrices de première espèce de la présente théorie peuvent être définies par des relations dans une théorie pure des ensembles.

Pour fonder une théorie des ensembles bien définis, on retient tous les axiomes de Zermelo, sauf l'axiome de l'infini, et on leur ajoute deux schémas d'axiomes : l'axiome de remplacement et un axiome de l'infini généralisé.

• L'axiome de remplacement : Si R est une relation qui définit une constructrice de première espèce à un argument alors pour tout x il existe y tel que pour tout z (z est élément de y si et seulement si il existe w tel que (w est élément de x et Rwz))
• Un axiome de l'infini généralisé : Si R est une relation qui définit une constructrice de première espèce à un argument alors pour tout x il existe y tel que (x est élément de y et y est clos pour R et pour tout z si (x est élément de z et z est clos pour R) alors y est inclus dans z)

Toutes les constructrices de première espèce sont obtenues par composition finie des constructrices fondamentales : la paire de, l'ensemble-somme de, l'ensemble des parties de, l'ensemble infini par, l'ensemble-image par et toutes les constructrices définies avec l'axiome de séparation pourvu que tous les quantificateurs soient bornés dans la définition des ensembles.

L'ensemble de tous les ensembles définissables dans cette théorie est obtenu en appliquant toutes les constructrices de première espèce à l'ensemble vide.

On peut enrichir cette théorie avec un axiome de l'infini plus puissant qui autorise l'induction infinie pour n'importe quel ordinal.

Les preuves de cohérence

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.

La vérité des axiomes de Peano

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 que les expressions numériques 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. Il est donc clair que cet ensemble de vérités atomiques existe. Tous les axiomes de Peano sont vrais pour ce modèle, d'une façon évidente ou facile à prouver. Comme une théorie vraie est nécessairement cohérente, on prouve du même coup la cohérence des axiomes de Peano.

Un modèle des axiomes de Zermelo

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 Sⁿ(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 Sⁿ(N) est inclus dans Sⁿ⁺¹(N), Sⁿ(N) est inclus dans S^p(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 Sⁿ(N) et y est élément S^p(N). Si n<=p, x et y sont tous les deux dans S^p(N) et leur paire est donc dans S^p+1(N). Si n>=p, {x,y} est dans Sⁿ⁺¹(N). L'axiome de la paire est donc vrai dans M.

Montrons par récurrence qu'un élément d'un élément de S^p(N) est aussi élément de S^p(N). L'énoncé est vrai pour N=S⁰(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 Sⁿ⁺¹(N) s'il est vrai pour Sⁿ(N), donc il est vrai pour tout nombre naturel n.

Il en résulte que la somme d'un élément de Sⁿ(N) est incluse dans Sⁿ(N) et est donc un élément de Sⁿ⁺¹(N). L'axiome de la somme est donc vrai dans M.

Il en résulte également que les parties d'un élément de Sⁿ(N) sont toutes incluses dans Sⁿ(N) et donc toutes éléments de Sⁿ⁺¹(N). L'ensemble des parties d'un élément de Sⁿ(N) est donc inclus dans Sⁿ⁺¹(N) et est donc un élément de Sⁿ⁺²(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.

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

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ûrs 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.

Pour formaliser la preuve de cohérence des axiomes de Zermelo 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.

Il n'y a pas de modèle ultime pour les théories des ensembles

On définit un modèle pour une théorie des ensembles lorsqu'on définit un ensemble d'ensembles tel que tous les axiomes sont vrais quand les quantificateurs non-bornés sont interprétés comme des quantificateurs bornés à cet ensemble d'ensembles. L'ensemble d'ensembles joue le rôle d'univers de tous les ensembles étudiés dans la théorie. Un modèle naturel pour une théorie des ensembles est de prendre la réunion de tous les ensembles définissables dans la théorie (M est un tel modèle naturel pour la théorie de Zermelo). Mais ce modèle ne peut pas être un modèle ultime, parce qu'il ne permet pas de définir une vérité ultime. Quand on énonce un théorème qui porte sur tous les ensembles, sa vérité va au delà de la vérité sur la réunion de tous les ensembles définissables dans la théorie. On veut qu'il soit vrai même pour des ensembles qui ne sont pas définissables dans la théorie, parce qu'on veut qu'il soit vrai vraiment pour tous les ensembles, pourvu qu'ils soient bien définis.

Pour avoir un modèle ultime, il faudrait pouvoir bien définir l'ensemble de tous les ensembles bien définis, mais ce n'est pas possible, parce qu'il serait élément de lui-même.

On peut songer à définir un modèle ultime $V$ pour une théorie des ensembles de la façon suivante :

$V_{0}=\varnothing$ où $\varnothing$ est l'ensemble vide {}.

$V_{\alpha }=\bigcup _{\beta <\alpha }{\mathcal {P}}(V_{\beta })$ pour chaque ordinal α, où ${\mathcal {P}}(X)\!$ est l'ensemble des parties de $X$.

La classe $V$ est alors définie comme la réunion de tous les $V_{\alpha }$ pour tous les ordinaux α :

$V=\bigcup _{\alpha }V_{\alpha }$

Mais cette classe n'est pas bien déterminée. Pour qu'elle le soit il faudrait que la classe de tous les ordinaux soit bien déterminée au préalable. Or un ordinal est essentiellement un ensemble bien ordonné. On ne peut pas définir la classe de tous les ensembles à partir de celle de tous les ordinaux, parce que la seconde est définie à partir de la première.

Pour les théories des nombres ou d'autres êtres mathématiques particuliers, la vérité des axiomes est toujours établie par référence à un modèle. On a un modèle qui nous sert de critère pour la vérité des axiomes. Pour les théories des ensembles, on ne peut pas avoir de modèle ultime, mais on a quand même un critère de vérité. Il faut que les ensembles dont nous prouvons l'existence soient ou bien bien définis, ou bien que leur existence résulte de celle des ensembles bien définis. Faute d'un modèle ultime, c'est l'exigence de bonnes définitions qui nous sert de critère de vérité.

L'incomplétude des fondements

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 à des êtres très élémentaires, les ensembles de nombres naturels.

Le théorème de Cantor, l'ensemble des ensembles de nombres naturels n'est pas dénombrable, peut être considéré comme le premier théorème sur l'incomplétude des principes, parce qu'il montre qu'une théorie ne permet jamais de définir explicitement tous les ensembles de nombres naturels. Plus généralement, dès que les ensembles sont indénombrables, une théorie ne permet jamais dé définir explicitement tous leurs éléments.

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 d'ensembles pour donner ces preuves. Par exemple, on applique le principe du raisonnement par récurrence aux ensembles de nombres naturels. Si des ensembles ne sont pas définis dans la théorie, on ne peut pas s'en servir pour définir des formules avec lesquelles raisonner par récurrence. On peut en conclure que l'incomplétude mathématique est une conséquence de l'indénombrabilité.

On prouvera 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.

Le théorème de l'indénombrabilité de l'ensemble des ensembles de nombres naturels de Cantor, 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, 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 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

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.

Incomplétude et indénombrabilité

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

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 ?

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.

Le second théorème d'incomplétude de Gödel

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 : 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.

Les preuves de cohérence sont-elles prises dans un cercle vicieux ?

Les preuves de cohérence qui exhibent une modèle sont formalisées dans une théorie T₊ plus forte que la théorie T₀ dont elles prouvent la cohérence, parce qu'elles définissent l'ensemble des vérités de T₀ et que cet ensemble ne peut pas être défini dans T₀. 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 T₀ dont on ignorerait tout. T₀ 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.

Les théories, les logiciels et les ensembles récursivement énumérables

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

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

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

Le problème de l'arrêt : Étant donnés un 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. À 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

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é

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.