L’argument diagonal de Cantor

Dans l’article sur l’hypothèse du continu nous avons brièvement présenté l’argument diagonal dans une version assez peu intuitive.

Pour rappel :

considérons une liste infini de nombres entre 0 et 1. La question étant, cette liste peut-elle contenir tout les réels ? La réponse étant évidement non.
En effet, raisonnons par l’absurde, et supposons que oui. Notons A(n) le n-iéme nombre, et Φn(m) la m-iéme décimale de A(n). Soit β le nombre dont la n-iéme décimale soit égale à 1 – Φn(n). Si ce nombre était dans la liste il existerait un entier K tel que quel que soit n, 1 – Φn(n) = Φk(n). En prenant n = K, on obtient 1 = 2Φk(K), donc 1 est un nombre pair. Ce qui est absurde. Donc ce nombre ne peut être dans la liste.

Nous allons ici en présenter une version identique sur le fond, mais certainement plus claire :

- Nous voulons prouver que l’ensemble des réels n’est pas dénombrable. C’est à dire qu’on ne peut dresser une liste infini de nombre qui les contiennent tous. Nous allons réaliser cette démonstration sur un sous ensemble de R, celui de tous les réels compris entre 0 et 1. En effet, si ce sous ensemble n’est pas dénombrable, il est évident que l’ensemble complet ne l’est pas non plus.

Supposons dressé une telle liste :
L’ordre des nombres de cette liste n’a aucune importance, le raisonnement qui va suivre étant valable pour toute liste infini de réels indexée par des entiers.

1. 0,73627477283883…
2. 0,87824246287462…
3. 0,79872772362783…
4. 0,12238382897894…
5. 0,23889746726784…
6. 0,43984928478479…
7. 0,03982874874746…
…

En prenant le premier chiffre du premier réel de notre liste, puis le second chiffre du second réel, et ainsi de suite, nous formons le nombre réel suivant 0,7783997…

Maintenant considérons un nombre ou chaque n-ième terme après le zero diffère du n-ième terme de notre nombre de référence. Ex : 0,8894008… Ce nombre est bien un réel. Il doit donc avoir une position dans notre liste. Soit N l’entier qui désigne cette position.

Nous voyons bien que l’existence de ce nombre à la position N est impossible. Son N-ième chiffre doit être par construction différent de lui même, ce qui est absurde.

Conclusion : tous les nombres réels ne peuvent être listé par une liste d’entier, fusse-t-elle infini.

J’admets volontiers qu’à première lecture cette démonstration puisse laisser circonspect. Pourtant elle est tout ce qu’il y a de plus rigoureux et logique. Elle laisse pourtant une impression étrange. Peut-être ne nous attendions pas à ce qu’une liste infini ne puisse tout contenir.

Les implications de cet argument sont énormes. Mais nous aurons peut-être l’occasion d’en discuter une prochaine fois. En attendant je vous invite à consulter l’article de Wikipedia pour approfondir le sujet.

L’hypothèse du continu

Certainement l’une des plus belles conjectures des mathématiques, l’hypothèse du continu constitue un défi à l’entendement humain. Formulé par Cantor, elle énonce l’égalité entre ℵ_c et ℵ₁. Essayons de voir ce que cela veut dire.

Présentation de l’hypothèse du continu
La théorie des ensembles, dont les fondements sont l’œuvre de Greg Cantor, considère l’existence d’ensembles pouvant contenir une infinité d’éléments, comme les exemples particuliers que sont N, Q et R. Une des caractéristique essentielle de tout ensemble, est l’existence d’un cardinal qui lui est rattaché. Le cardinal d’un ensemble est défini comme le nombre d’éléments que cet ensemble contient. Par exemple, l’ensemble des entiers de 1 à 10 a pour cardinal 10. Si la notion de cardinal est simple concernant les ensembles finis, elle se laisse plus difficilement apprivoiser dans le cas d’ensembles plus grands que tout ensemble fini, c’est à dire possédant une infinité d’éléments.

Les travaux de Greg Cantor apportent les outils nécessaires pour maitriser de tels ensembles. Il démontre notamment que :
- Deux ensembles équipotents ont même cardinal. Ainsi, si à tout élément d’un ensemble A, je peux associer un élément d’un ensemble B, et réciproquement, alors A et B ont même cardinal.
- Le cardinal de l’ensemble des parties d’un ensemble E, est strictement supérieur au cardinal de E. Ce résultat évident concernant les ensembles finis, ne l’était pas forcement pour ce qui est des ensembles infinis. On aurait pu par exemple penser que tout ensemble infini était équipotent à tout autre ensemble infini, et avait donc même cardinal comme cela peut être le cas entre N et Q. Ceci est faux, et Card{P(E)} > Card{E}.
- Le cardinal de l’ensemble des réels R est identique à celui de l’ensemble des parties de l’ensemble des entiers N.

Un des résultats les plus célèbre de Cantor, est la démonstration du caractère indénombrable de l’ensemble des réels R. L’adjectif indénombrable est couramment utilisé pour signifier qu’un ensemble, ici R, ne peut pas être dénombré par l’ensemble des entiers naturel, ou tout autre ensemble dénombrable. Autrement dit, un ensemble est indénombrable si aucune correspondance biunivoque ne peut être établie entre cet ensemble, et l’ensemble ou une partie des entiers naturels, donc si son cardinal est supérieur au cardinal de N. Il va de soit que ceci est évident à la vue des résultats présentés au dessus. En effet, si Card{R} = Card{P(N)}, puisque Card{P(N)} est nécessairement supérieur à Card{N}, alors Card{R} est supérieur à Card{N}. Mais la démonstration initialement utilisé par Cantor est particulièrement intéressante, du fait qu’elle constitue le premier usage de l’argument diagonal qui sera ensuite reprit sous diverses formes par Russell, Gödel ou Turing.

Pour présenter brièvement l’argument diagonal, il nous suffit de considérer une liste infini de nombres entre 0 et 1. La question étant, cette liste peut-elle contenir tout les réels ? La réponse étant évidement non.
En effet, raisonnons par l’absurde, et supposons que oui. Notons A(n) le n-iéme nombre, et Φn(m) la m-iéme décimale de A(n). Soit β le nombre dont la n-iéme décimale soit égale à 1 – Φn(n). Si ce nombre était dans la liste il existerait un entier K tel que quel que soit n, 1 – Φn(n) = Φk(n). En prenant n = K, on obtient 1 = 2Φk(K), donc 1 est un nombre pair. Ce qui est absurde. Donc ce nombre ne peut être dans la liste.

Nous savons donc à ce stade, qu’il existe des cardinaux finis (1, 2, 3, 4, …) et des cardinaux infinis, puisque Card{P(E)} > Card{E}, même pour des ensembles infinis. On considère alors l’ensemble des cardinaux infinis. On nomme ℵ₀ (prononcer aleph-zero) le premier d’entre eux, ℵ₁ le second, et ainsi de suite. On associe a N le cardinal ℵ₀.

P(N) ou R, on un cardinal infini, supérieur à celui de N, donc supérieur à ℵ₀, on note à ce stade ℵ_c le cardinal de R, ℵ_c étant nommé le cardinal du continu. Tout le problème se pose alors de savoir ou se situe ℵ_c dans l’échelle des cardinaux infinis.

Intuitivement, il est tentant de croire que ℵ_c = ℵ₁, ℵ_c étant le cardinal de l’ensemble de parties de N, c’est le premier cardinal infini supérieur à Card{N} qu’on rencontre et qu’on connaisse. Et cette égalité, est connue sous le nom d’hypothèse du continu. Pourtant, rien n’indique objectivement que cette intuition soit la bonne. En effet, rien ne prouve qu’il n’existe pas de cardinaux intermédiaire pouvant être associer à des ensembles compris entre N et P(N), comme cela est déjà le cas pour les cardinaux finis. Soit E(3) un ensemble de cardinal 3, Card{P(E(3))} = 2 puissance 3, soit 8, et non 4.

La question de l’égalité entre ℵ_c et ℵ₁ constitue l’hypothèse du continu. Mais à ce stade rien n’indique la non existence d’ensembles de cardinaux intermédiaires entre N et P(N).

Statut de la conjecture
Si l’hypothèse du continu n’a pas grand intérêt pratique, elle se place néanmoins au cœur des fondements même de la théorie usuelle des ensembles, socle des mathématiques modernes, à tel point qu’un des plus grand mathématiciens de l’histoire, Hilbert, a qui on doit notamment des espaces vectoriels particuliers qui portent son nom, ou la première formulation de l’équation d’Einstein en relativité générale, quand il dressa une liste des principaux problèmes mathématiques de son époque, parmi lesquels la conjecture de Riemann, ou le problème de la décision, plaça l’hypothèse du continu en première position.

Aujourd’hui, beaucoup considèrent ce problème comme résolu. En effet, Gödel d’une part, et Cohen, ont démontrés l’indépendance de l’hypothèse du continu vis-à-vis de la théorie des ensemble. Autrement dit, l’hypothèse du continu est un indécidable de ZFC, elle n’est pas démontrable en utilisant les axiomes admis de la théorie des ensembles.

Mais l’histoire s’arrête-t-elle à ce point ?
Gödel le premier pensait que non. En effet, les termes de la notion d’ensemble sont déterminés à l’origine, avant même que les axiomes ne soient posés. Les axiomes restreignent le champs de la notion d’ensemble, et dans l’absolu l’hypothèse du continu est nécessairement vrai ou fausse. Un parallèle avec le théorème de Gödel est facile. Dans ce dernier, Gödel exhibe une proposition qui affirme sa non décidabilité, et s’il est vrai qu’un indécidable de Gödel est non démontrable dans le système axiomatique considéré, il n’en est pas moins vrai en dehors. La proposition : je suis indécidable est vrai hors du système considéré.

Conclusion
Nous venons ici de jeter un premier regard sur la beauté de cette entité mathématique qu’est l’univers des réels. Je reviendrais probablement dans un autre article préciser le fonctionnement précis de l’argument diagonal qui mérite un développement plus important que le petit encart que je lui ai réservé. Si j’ai le temps, je préciserais également plusieurs choses sur ces mystérieux alephs.