Fondements des mathématiques/Les expressions formelles, les ensembles et les fonctions

Début de la boite de navigation du chapitre

Ce chapitre expose les problèmes de l’existence des êtres mathématiques. Qu’est-ce qui existe au sens mathématique ?

fin de la boite de navigation du chapitre

L’ontologie mathématique

La question de l’existence est aussi nommée la question ontologique. L’ontologie d’une théorie, c’est l’ensemble de tous les énoncés d’existence des objets qu’elle étudie.

L’ontologie des mathématiques a été très controversée. Les nouveaux êtres mathématiques, les nombres négatifs, complexes, infinis, les lignes continues non-différentiables, les espaces abstraits et beaucoup d’autres ont tous rencontré des résistances avant d’être assez généralement acceptés. On dispose aujourd’hui de méthodes ontologiques très tolérantes, les théories des ensembles, qui sont suffisantes pour la grande majorité des besoins des mathématiciens. Elles permettent d’attribuer l’existence à presque tous les êtres abstraits concevables. Mais cette section et les suivantes montreront qu’on ne peut pas supprimer le « presque » dans la phrase précédente, que l’incomplétude ontologique est fondamentale.

Si on définit les mathématiques comme la science des formes de déduction, la question ontologique ne se pose pas. On suppose que les prémisses sont vraies. Tous les énoncés d’existence qu’elles contiennent sont des hypothèses dont la vérité dépend des objets (non-mathématiques) auxquels elles sont appliquées. Autrement dit tous les énoncés d’existence mathématique auraient un caractère hypothétique. Mais cette approche ne rend pas complètement compte des questions qui se posent aux mathématiciens.

Quand on a prouvé par exemple qu’il existe un corps ordonné, archimédien et complet, à savoir l’ensemble des nombres réels, on interprète en général ce théorème comme une vérité absolue, qui ne dépend pas d’hypothèses sur l’existence des êtres non-mathématiques. Cela revient à croire d’une certaine façon en l’existence d’un monde idéal, platonicien, où les êtres mathématiques existent vraiment et où ils sont comme nous disons qu’ils sont. Mais comment savoir que ce monde idéal existe vraiment ?

La théorie des modèles apporte une réponse plus prudente. Elle ne dit pas qu’il existe un monde idéal mais seulement qu’on peut l’imaginer. On interprète alors le théorème d’existence de l’ensemble des nombres réels, non comme une affirmation sur un mystérieux au-delà, mais seulement comme l’affirmation qu’il est possible de développer une théorie cohérente à propos d’un corps (au sens de l’algèbre), ordonné, archimédien et complet.

De ce point de vue, la théorie des ensembles est interprétée non en référence à l’au-delà mais seulement à l’ici-bas, parce qu’ici nous sommes bien sûrs qu’il y a des êtres humains qui font des théories. On peut alors voir les théories des ensembles comme des théories de toutes les théories, ou de tous les mondes possibles, ceux-ci étant déterminés par celles-là.

Les théories des ensembles apportent donc un point de vue très général. En fait, tous les théorèmes mathématiques peuvent être démontrés à l’intérieur d’une théorie des ensembles. Mais la puissance de ces théories posent des difficultés. Nous allons voir qu’il n’est pas facile de les formuler d’une façon cohérente.

L’existence des extensions conceptuelles, Frege et le paradoxe de Russell

Frege est l’un des premiers à avoir proposé une liste explicite des principes d’existence des ensembles. Il l’avait incorporée à une œuvre destinée à fonder l’ensemble des mathématiques sur des méthodes complètement formalisées. Son principal axiome dit que pour tout concept C il existe un ensemble, l’ensemble E des êtres pour lesquels ce concept est vrai. E est l’extension conceptuelle de C.

L’axiome de Frege semble assez naturel, et il est adopté sous une forme restreinte dans toutes les théories modernes des ensembles. Mais Bertrand Russell a montré que sous la forme originale proposée par Frege, l’axiome conduit à une contradiction. Quand Frege a reçu la lettre de Russell, il eut le sentiment injustifié que toute son œuvre s’était effondrée d’un seul coup. En vérité Frege a été et demeure l’un des plus grands logiciens de tous les temps. On lui doit l’une des premières formulations complètes du calcul des prédicats et de son application aux fondements des mathématiques. Son erreur était assez naturelle, elle a révélé des aspects jusque là inconnus de la raison, et elle peut être corrigée tout en conservant l’essentiel du système.

Le concept, ou prédicat, qui a posé problème pour l’axiome de Frege est celui des ensembles qui n’appartiennent pas à eux-mêmes, (x est un ensemble et x n’est pas dans x).

En général les ensembles n’appartiennent pas à eux-mêmes. Un ensemble de nombres n’est pas lui-même un nombre, un ensemble de personnes n’est pas une personne… Les éléments existent en un sens avant l’ensemble. L’ensemble ne fait que réunir des éléments préexistants. Mais on peut trouver des exceptions, l’ensemble de tous les ensembles, par exemple, peut être considéré comme un ensemble, il est donc élément de lui-même.

D’après l’axiome de Frege, il devrait exister un ensemble de tous les ensembles qui ne sont pas éléments d’eux-mêmes. Cet ensemble contiendrait la plupart des ensembles usuels mais il ne contiendrait pas l’ensemble de tous les ensembles ni quelques autres un peu bizarres. Cet ensemble, appelons le BR, est il élément de lui-même ?

Si BR est élément de BR alors il n’est pas élément de lui-même par définition de BR, puisque BR contient tous les ensembles qui ne sont pas éléments d’eux-mêmes. On a donc dans ce cas une contradiction. BR appartient à BR et BR n’appartient pas à BR.

Si BR n’est pas élément de BR alors il est élément de lui-même, toujours par définition de BR. On a donc également une contradiction.

Le principe du tiers exclu, la règle de disjonction des hypothèses et la règle du détachement permettent alors de conclure à (BR appartient à BR et BR n’appartient pas à BR). Comme tous ces principes étaient acceptés par Frege, son système contenait une contradiction. Pour un logicien, c’est une catastrophe, parce qu’un système contradictoire permet de démontrer n’importe quoi, qu’il soit vrai ou faux, à l’aide du principe du raisonnement par l’absurde. Un système qui permet de démontrer des faussetés ne démontre rien du tout.

On peut donner au paradoxe de Russell la forme plus intuitive suivante : un barbier rase tous les hommes de son village qui ne se rasent pas eux-mêmes. Ce barbier se rase-t-il ?

De l’examen des réponses il faut conclure qu’un tel barbier ne peut pas exister. De la même façon un ensemble qui contiendrait tous les ensembles qui ne sont pas dans eux-mêmes ne peut pas exister. Autrement dit, toute ontologie des extensions conceptuelles ne peut pas donner l’existence à l’extension du concept de ne pas être élément de soi-même sous peine d’être contradictoire.

On peut noter ici une différence entre l’exemple du barbier et BR. Le concept d’un tel barbier dans un tel village existe, mais c’est un concept vide. De même, le concept d’un univers d’ensembles et d’un ensemble qui contiendrait tous les ensembles qui ne sont pas dans eux-mêmes existe. Russell a prouvé que c’est un concept vide. Mais que faut-il dire du concept « ne pas être élément de soi-même » ? Est-ce qu’il existe ?

Un concept existe dès qu’il fait partie d’une théorie sensée. L’ensemble des nombres entiers n’est pas un nombre entier et n’est donc pas élément de lui-même. C’est sensé. Le concept de ne pas être élément de soi-même existe donc. Seule son extension conceptuelle ne peut pas exister. Le concept du barbier ci-dessus existe et a une extension conceptuelle. Elle est tout simplement vide. Le concept de ne pas être élément de soi-même existe mais n’a pas d’extension conceptuelle. S’il en avait une, elle ne pourrait pas être vide, puisqu’il y a des ensembles qui ne sont pas éléments d’eux-mêmes. Appelons concepts extensionnels les concepts qui ont une extension. Russell a prouvé qu’une théorie générale des concepts ne peut pas se limiter aux concepts extensionnels.

Qu’est-ce qu’un ensemble ?

Pour faire un ensemble il suffit d’avoir des objets et de donner un critère d’appartenance à l’ensemble que l’on définit. Le critère d’appartenance est en général un prédicat unaire, c’est-à-dire une formule qui contient une seule variable libre. Un prédicat unaire est un concept qualitatif. C’est pourquoi toute ontologie des ensembles incorpore sous une forme plus ou moins restreinte l’axiome de Frege. Il y a des concepts qui ont une extension. Plus il y en a, plus l’ontologie est tolérante. Mais si elle est trop tolérante, elle tombe dans l’absurdité.

Un même ensemble peut être défini et nommé de plusieurs façons. Comment sait-on qu’il s’agit toujours du même ensemble ? Il suffit de montrer qu’il y a toujours les mêmes éléments. Plus précisément, deux ensembles E et F sont égaux lorsque tout élément de E est élément de F et réciproquement. C’est l’axiome d’extensionalité.

Ce nom vient de la distinction entre la signification et l’extension d’un concept, ou prédicat. Par exemple « être humain » et « être humain avec ADN » sont deux prédicats qui ont la même extension, parce que tous les êtres humains ont de l’ADN, mais ils n’ont pas la même signification, parce que quelqu’un qui ne connait pas la biologie moléculaire ne sait pas qu’un être humain est toujours un être humain avec ADN.

L’extension d’un prédicat, c’est l’ensemble de tous les êtres pour lesquels ce prédicat est vrai. L’axiome d’extensionnalité ne fait qu’énoncer la propriété essentielle des extensions, c’est-à-dire des ensembles.

Les ensembles indicibles

La fin de cette section prouvera qu’une théorie ne peut pas donner l’existence à tous les ensembles. Elle ne contient pas assez de noms. Quel que soit l’ensemble infini des ensembles nommés dans une théorie, il est toujours incomplet. Qu’on puisse prouver que l’incomplétude ontologique est une propriété nécessaire de toutes les théories montre que la raison est capable de connaître ses propres limites.

Il n’y a pas de théorie qui contienne assez de noms pour tous les ensembles. Cela ne veut pas dire forcément que le concept d’ensemble n’a pas d’extension, parce qu’on peut parler de l’ensemble de tous les ensembles . Mais cela veut quand même dire que cette extension ne peut jamais être bien définie, qu’on ne peut jamais donner un nom à tous ses éléments. Tant qu’on peut donner un nom à tous ses éléments, l’ensemble est dicible, sinon il est indicible.

Le paradoxe de Russell oblige à renoncer à l’axiome de Frege sous sa forme trop générale. Mais on n’a pas besoin de l’ensemble BR. L’ensemble de tous les ensembles n’est pas non plus nécessaire, au moins dans les mathématiques élémentaires. Quand on développe une théorie, on se contente en général d’ensembles relativement petits, comme l’ensemble des nombres entiers, et de principes d’existence qui permettent de définir de nouveaux ensembles à partir de ceux qui sont déjà définis. Il en va de même que pour les nombres entiers eux-mêmes. Il suffit de partir de 0 et on peut définir tous les autres nombres entiers positifs simplement en ajoutant 1 à ceux qui ont déjà été définis.

En général, on n’a pas besoin d’ensembles aussi grands que l’ensemble de tous les ensembles, parce qu’on se contente des ensembles de nombres et de ceux que l’on peut définir à partir d’eux. On pourrait donc songer à limiter les mathématiques à des ensembles dicibles tels que celui des entiers. On pourrait vouloir exclure de notre ontologie tous les ensembles indicibles, sous prétexte qu’ils sont problématiques. Mais ce serait une erreur aussi grave que de vouloir arranger nos vies pour ne plus jamais avoir de problèmes. Les êtres rationnels sont assez forts pour résoudre des problèmes. Il ne faut pas nous prendre pour des incapables.

La théorie cantorienne des nombres infinis montre que même des ensembles beaucoup plus petits que l’ensemble de tous les ensembles sont également indicibles. Deux des plus petits sont l’ensemble des nombres réels et l’ensemble P(N) de tous les ensembles de nombres entiers positifs, ou ensemble des parties de N. Les parties sont ici les sous-ensembles. N est l’ensemble des entiers naturels, ou positifs. L’ensemble P(N) est très important. Il est fondamental pour définir l’ensemble des nombres réels.

À priori l’existence de l’ensemble de tous les ensembles n’est pas interdite. On peut accepter n’importe quelle théorie des ensembles pourvu qu’elle n’ait pas de conséquences contradictoires et qu’elle respecte les significations usuelles que l’on attribue à la notion d’ensemble. La théorie du zig-zag interdit de Quine donne l’existence à l’ensemble de tous les ensembles et elle respecte les significations usuelles de la notion d’ensemble.

La stratégie ontologique de cette encyclopédie est progressive. On commencera par les ensembles dicibles. Les ensembles dicibles fondamentaux sont les systèmes formels, ou ensembles d’expressions formelles. Les autres ensembles sont définis à partir des systèmes formels avec des règles de construction.

Les systèmes formels

Un système formel est un ensemble de formules, ou expressions formelles, que l’on peut interpréter comme des noms, des phrases, ou de toute autre façon.

• Les ensembles de nombres, entiers, rationnels, algébriques, peuvent être définis comme des systèmes formels, mais pas les ensembles qui contiennent tous les nombres transcendants, réels ou complexes.
• La nomenclature de la chime organique est un système formel.
• Une théorie est un ensemble de phrases et est donc un système formel.

Les théories générales des systèmes formels ont été conçues par des logiciens surtout pour étudier les théories. De ce point de vue on peut les considérer comme des métathéories générales, des théories de toutes les théories.

Comme une formule peut toujours être nommée, les systèmes formels sont toujours dicibles. Il y a de nombreuses façons de nommer les formules. La plus économique consiste à considérer qu’une formule est un nom pour elle-même.

L’ensemble des noms des éléments d’un ensemble E relativement à une théorie est un système formel. Mais même s’il est dicible, E lui-même n’est pas forcément un système formel, si ses éléments sont interprétés non comme des expressions formelles mais comme des ensembles ou d’autres objets.

Le point de vue formel introduit une limitation. On se soucie peu de la signification des mots ou des symboles. Les théories n’y sont pas considérées comme des fenêtres sur le monde réel. Elles sont opaques. Elles ne contiennent que des assemblages de mots et on se soucie d’abord de leurs formes, pas de leurs significations. D’où le nom de point de vue formaliste.

Les systèmes formels de base sont des ensembles énumérables. Intuitivement, ce sont tous les ensembles pour lesquels on peut donner un procédé mécanique d’énumération de tous leurs éléments. Le chapitre suivant (l’incomplétude) donnera deux définitions équivalentes de cette notion fondamentale d’énumérabilité.

L’existence des non-ensembles

Une méthode couramment acceptée en mathématiques fondamentales consiste à limiter l’ontologie aux ensembles. Les seuls êtres mathématiques sont des ensembles. La raison de cette méthode, c’est qu’il semble qu’on ne gagne rien à accueillir les non-ensembles. Tous les non- ensembles peuvent être représentés fidèlement dans une théorie des ensembles. Cela peut surprendre le débutant, parce que les non-ensembles, les nombres et la plupart des objets sont premiers par rapport aux ensembles. Les ensembles ne font que réunir des êtres qui existent déjà. Cependant, si l’on part de l’ensemble vide, et que l’on forme d’autres ensembles, tels que l’ensemble qui contient l’ensemble vide comme unique élément, l’ensemble qui contient les deux précédents, l’ensemble qui contient les trois précédents et ainsi de suite, on obtient une ontologie réduite aux ensembles et cependant assez riche pour définir des représentations de tous les êtres mathématiques. L’économie des moyens justifie donc cette réduction ontologique. Mais cette méthode de réduction ne sera pas suivie dans les pages qui suivent pour plusieurs raisons.

Avant l’existence des ensembles on accepte celle des expressions formelles. Celles-ci pourraient être représentées par des ensembles, mais cette représentation fait perdre à la théorie son caractère naturel. L’évidence des principes de la théorie des systèmes formels est un critère important pour évaluer sa fiabilité. Tant que ces principes sont évidents, nous pouvons être sûrs de la qualité des preuves autant que nous pouvons l’être de toute preuve fondée sur des principes élémentaires. Comme elle fait perdre aux principes une partie de leur évidence, la réduction ontologique ensembliste ne me semble pas souhaitable si on s’interroge sur la fiabilité des principes.

En plus des expressions formelles et des ensembles, on accepte l’existence des fonctions. On a une fonction quand on sait associer à chaque être x d’une catégorie un être f(x) défini de façon univoque. L’ensemble ou la classe des x pour lesquels f(x) existe est le domaine de la fonction f. f(x) est l’image par f de x. On le note aussi parfois fx.

Le domaine d’une fonction n’est pas toujours un ensemble. Par exemple, soit f la fonction qui à un ensemble x associe l’ensemble Singleton de x, qui contient x comme unique élément. Le domaine de f est la classe de tous les ensembles. Je dis ici la classe et non l’ensemble, parce que dans de nombreuses théories, l’ensemble de tous les ensembles n’existe pas et ne peut pas exister sous peine de contradiction.

Lorsque le domaine de f est un ensemble, f elle-même peut être considérée comme l’ensemble de tous les couples (x, fx) pour lesquels fx existe. Un ensemble de couples est en général défini comme l’extension conceptuelle d’un prédicat binaire, ou formule à deux variables libres, ou relation binaire. Un ensemble F de couples est considéré comme une fonction si et seulement si pour tous x, y, et z, si (x, y) et (x, z) sont dans F alors y=z. Cette propriété traduit l’univocité de la relation définie par F. On dit aussi que F définit une relation fonctionnelle. C’est en accord avec la signification courante que x est fonction de y lorsque y suffit pour déterminer x, lorsque x ne dépend que de y. Comme les sciences consistent toujours à établir de tels liens de dépendance entre les êtres ou les évènements, les fonctions sont des êtres abstraits d’une importance considérable.

Tant que le domaine d’une fonction est un ensemble, l’ontologie des fonctions peut être réduite à celle des ensembles. Mais ce n’est pas toujours le cas. De telles fonctions, ou superfonctions, dont le domaine n’est pas un ensemble, sont utilisées dans toutes les théories des ensembles, parce qu’elles sont indispensables, mais elles ne sont pas considérées comme des fonctions ni vraiment comme des êtres mathématiques, mais seulement comme des auxiliaires du raisonnement, parce que l’ontologie strictement ensembliste interdit de leur donner l’existence. Telles sont par exemple, les fonctions de réunion et d’intersection d’ensembles.

Quand on adopte une démarche ontologique progressive, les fonctions sont parfois plus fondamentales que les ensembles. Il n’y a aucune difficulté à considérer « Singleton de… » comme une fonction. En revanche, il y a beaucoup de difficultés à considérer son domaine comme un ensemble. Dans certaines théories, on veut que tous les êtres soient définis à partir d’objets déjà définis. Comme les fonctions jouent un rôle de premier plan dans la construction, ou définition, des ensembles, leur existence est établie de façon prioritaire.

La théorie cantorienne des nombres infinis

Les nombres entiers positifs suffisent pour se faire une idée de l’infini. On peut écrire des nombres aussi grands que l’on veut. Il n’y a pas de nombre qui soit plus grand que tous les autres. On peut le démontrer par l’absurde. Supposons qu’il y ait un nombre plus grand que tous les autres. Appelons-le N. N+1 est plus grand que N contrairement à l’hypothèse, qui doit donc être rejetée, ce qu’il fallait démontrer. Montrons que l’on peut formaliser cette démonstration avec les règles de la déduction naturelle.

1 pour tout x, x est plus petit que x+1 (Axiome)

2 pour tout x et tout y, si x est plus petit qu'y alors y n’est pas plus petit que x (Axiome)

3 z est plus petit que z+1

4 si z est plus petit que z+1 alors z+1 n’est pas plus petit que z

5 z+1 n’est pas plus petit que z

6 pour tout w, w+1 n’est pas plus petit que w

7 °°°°° pour tout x, x est plus petit que N (Hypothèse)

8 °°°°° n’est pas plus petit que N

9 °°°°° N+1 est plus petit que N

10 °°°°° N+1 est plus petit que N et N+1 n’est pas plus petit que N

11 non(pour tout x, x est plus petit que N)

12 pour tout N, non( pour tout x, x est plus petit que N)

CQFD (ce qu’il fallait démontrer)

3 est obtenu de 1 en remplaçant la variable x par le terme z en accord avec la règle de singularisation.

4 est obtenu de 2 en appliquant deux fois la règle de singularisation, on remplace d’abord x par z, puis y par z+1.

5 est obtenu de 3 et 4 par la règle du détachement.

6 est obtenu de 5 par la règle de généralisation. 6 est un théorème intermédiaire, ou lemme.

7 est l’hypothèse provisoire sur N dont on va montrer l’absurdité.

8 est obtenu de 6 par la règle de singularisation en remplaçant w par N. L’application de la règle est autorisée parce que 6 n’est pas décalé sur la droite par rapport à 8.

9 est obtenu de 7 par la règle de singularisation en remplaçant x par N+1.

10 est obtenu de 8 et 9 par la règle de synthèse.

11 est obtenu de 7 et 10 par la définition de la négation.

12 est obtenu de 11 par la règle de généralisation, parce que 11 ne dépend pas de l’hypothèse sur N faite en 7.

Dans la suite les nombres entiers sont les nombres entiers positifs, dits aussi nombres naturels.

Y a-t-il un sens à parler d’un nombre infini, du nombre de tous les nombres entiers par exemple ? Sous l’influence d’Aristote, on a lontemps considéré que c’était impossible. On disait que la notion d’infini a un sens quand il s’agit d’un infini potentiel, quand cela veut dire qu’une progression n’est pas limitée, mais que l’infini actuel n’a pas de sens, qu’on ne peut pas considérer un ensemble infini comme un tout. S’il n’y avait pas eu l’autorité d’Aristote, cette opinion n’aurait probablement pas été prise autant au sérieux, parce qu’il n’y a pas de difficulté à parler de l’ensemble de tous les nombres entiers et à dire des vérités à son sujet.

L’idée du nombre des nombres entiers posait cependant des paradoxes. Par exemple l’ensemble des entiers est en un sens plus grand que l’ensemble des entiers pairs puisqu’il contient aussi l’ensemble des entiers impairs. On pourrait même être tenté de dire qu’il est deux fois plus grand. Cependant en un autre sens ces deux ensembles sont également grands puisqu’on peut obtenir l’un à partir de l’autre en remplaçant un à un chacun de ses éléments. Il suffit de remplacer chaque entier par son double pour avoir l’ensemble des entiers pairs à partir de l’ensemble des entiers. Ce paradoxe était connu de Galilée. Cantor a résolu le problème en adoptant la seconde définition et en affirmant sans crainte que le nombre des entiers est égal au nombre des entiers pairs. On appelle ce nombre l’infini dénombrable. Les ensembles infinis dénombrables sont aussi grands que l’ensemble des entiers.

Deux ensembles E et F ont le même nombre d’éléments lorsqu’il existe une relation, ou correspondance, biunivoque entre leurs éléments. On dit aussi une fonction inversible ou une bijection. Une relation binaire R est biunivoque lorqu’elle est une fonction dans les deux directions, lorsque chaque élément de E est relié à un élément et un seul de F et inversement. On dit aussi qu'E et F ont le même cardinal. Il y a deux définitions cantoriennes des nombres infinis, les cardinaux et les ordinaux. Les ordinaux sont très importants, plus que les cardinaux à bien des égards, et ils seront présentés dans le chapitre 5, mais pour prouver l’existence des ensembles indicibles, c’est la théorie des cardinaux qui permet de conclure.

Y a-t-il des ensembles infinis (strictement) plus grands que l’ensemble des entiers ? Oui. C’est la grande découverte de Cantor. Le nombre des nombres réels en particulier est un infini plus grand que le nombre des nombres entiers. On peut définir des nombres infinis toujours plus grands. Le grand théorème de Cantor permet de le comprendre : l’ensemble P(E) des sous-ensembles d’un ensemble E est toujours plus grand qu'E. Sa démonstration n’est pas très difficile. Elle se fait par l’absurde. Supposons qu’il existe une fonction inversible f entre E et P(E). Définissons le sous-ensemble C de E par x appartient à C si et seulement si x n’est pas élément de f(x). Comme C est élément de P(E) il existe c tel que C=f(c). c est-il élément de f(c) ? Le raisonnement est semblable à celui du paradoxe de Russell. Si c est élément de f(c)=C alors c n’est pas élément de C par définition de C, et de même si c n’est pas élément de f(c). Il faut donc rejeter l’hypothèse. La fonction f ne peut pas exister. E ne peut donc pas être aussi grand que P(E) et il est forcément plus petit puisque P(E) contient toutes les sous-ensembles de E qui ne contiennent qu’un seul élément.

L’ensemble P(N) des ensembles de nombres entiers est donc plus grand que l’ensemble N des nombres entiers.

Pour montrer que l’ensemble des nombres réels est plus grand que celui des entiers Cantor avait proposé une version particulière de la méthode précédente. Supposons qu’il existe une bijection entre les réels et les entiers. On pourrait alors écrire la liste de tous les nombres réels dans le même ordre que celui des entiers. Supposons que cette liste soit écrite en notation décimale et que toutes les virgules soient placées sur une même verticale. Définissons alors le nombre réel GC. Le seul chiffre de GC avant la virgule est zéro. Si la première décimale du premier nombre réel listé est 1 alors la première décimale de GC est 2 sinon elle est 1. Si la deuxième décimale du deuxième nombre réel listé est 1 alors la deuxième décimale de GC est 2 sinon elle est 1. On applique la même règle pour toutes les décimales de GC en suivant la diagonale des décimales de la liste des nombres réels. C’est la méthode de la diagonale de Cantor. GC est un nombre réel bien défini puisqu’on a défini toutes ses décimales. GC n’appartient pas à la liste puisqu’il y a au moins une décimale de différence entre GC et chacun des nombres listés. La liste ne contient donc pas tous les nombres réels, contrairement à l’hypothèse. Il ne peut donc pas exister de fonction inversible entre les entiers et les réels.

On appelle le nombre des nombres réels la puissance du continu. Le théorème précédent affirme que la puissance du continu est plus grande (strictement) que l’infini dénombrable, qu’elle est indénombrable.

Le théorème de l’incomplétude ontologique : il existe des ensembles indicibles

Si un ensemble n’est ni fini, ni dénombrable, on dit qu’il est indénombrable. Le théorème de l’incomplétude ontologique est une conséquence des théorèmes de Cantor, parce qu’un ensemble indénombrable est indicible. Pour le prouver, il suffit de montrer que l’ensemble de tous les noms dans une théorie est toujours au plus dénombrable. La définition d’une théorie respecte deux conditions.

a) L’alphabet, ou liste des symboles fondamentaux, ou lettres, est toujours fini.

b) Les mots, ou expressions formelles, sont des suites finies de lettres. Pour prouver que l’ensemble infini de tous les mots est dénombrable il suffit de définir un ordre, par exemple un ordre de type lexicographique, sur cet ensemble. L’existence de la fonction inversible qui associe à chaque mot son numéro d’ordre suffit pour terminer la preuve.

Certains logiciens ont défini des « théories » pour lesquelles l’une ou l’autre des conditions a et b n’est pas vraie. Alors l’ensemble des mots peut être indénombrable. Mais ce ne sont pas des théories au sens ordinaire du mot. Même lorsque la condition a est relachée et qu’on autorise un alphabet infini dénombrable, l’ensemble de tous les mots est encore dénombrable.

À partir des théorèmes de Cantor et de la dénombrabilité de tout ensemble de noms, on peut conclure que si un ensemble E est infini, alors l’ensemble P(E) de ses parties est indicible.