L’argument diagonal de Cantor
novembre 23, 2008 par Julien
Catégorie Mathématiques
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.
Il y a un manque de logique dans le raisonnement… L’argument se trouve en fait à utiliser le cheminement pris pour créer la liste elle-même… argument voulant que tous les termes de la liste soit obligatoirement différents et que la liste soit en création perpétuelle de nouveaux termes.
Si la liste est infinie alors elle ne possède logiquement pas de dernier terme (il sera toujours le terme suivant ou actuel pendant la création de la liste) … il n’y a qu’à placer le nombre crée comme dernier de la liste… son dernier terme ne pourra donc jamais exister car par définition la liste n’en possède pas (liste ouverte) et la contradiction sur le fait que sa dernière décimale ne puisse être égale à elle-même sera surmontée.
Le second terme de la liste ne peut également pas exister selon ce principe car le premier terme est déjà lui-même une liste de chiffres s’étendant à l’infini, donc ne possédant pas de dernier terme et ne se terminant jamais… le second terme de la liste ( dont seule la dernière décimale peut et différée du premier terme) ne peut donc être comparée au premier car la dernière décimale ne sera jamais accessible et vérifiée en réalité…
Parfaitement logique est plutôt douteux dans ces circonstances… ne trouvez-vous pas?
Non, non, je vous assure que le raisonnement est bon.
Il est cependant normal que vous le mettiez en doute tant il est contre intuitif au départ.
A proprement parlé, il n’y a pas de création de liste. Ce qui est démontré, c’est l’impossibilité d’une bijection entre l’ensemble des entiers et celui des nombres réels.
En fait vous devez vous imaginer quelqu’un qui vient vers vous avec une liste infini à la main en vous disant : “tiens regarde, sur cette liste j’ai noté l’ensemble des nombres réels entre 0 et 1″.
Vous regardez brièvement la liste, et vous lui répondez :
“hum, je crois que tu en as oublié quelques uns”
Lui :
“Lesquels ?”
Vous :
“Tu vois la diagonale qui part de ton premier nombre et qui s’étend à l’infini dans la liste, elle forme bien un nombre réel ?”.
Lui :
“Oui, bien sûr, et puisque ma liste est complète, je peux même te dire en regardant, qu’il se trouve à la 980740239278789479834928eme ligne”.
Vous :
“Ok, maintenant, remplace tous les chiffre de ce nombre par des 7, sauf les 7 que tu remplaces par des 3 (ou fait n’importe qu’elle autre substitution de ce type. Dis moi ou se trouve le nombre obtenu dans ta liste ?”.
Lui :
“Ben je ne le trouve pas”.
Vous :
“C’est normal. Si on suppose cette liste complète, alors il doit avoir une position dans la liste. Mettons L. Mais si on regarde à la ligne L, par construction, la Lième décimale doit être différente d’elle même.
Lui :
“En effet, je vais le rajouter quelque par dans ma liste ainsi ma liste sera complète”.
Vous :
“Mais si vous faite ça, je pourrais toujours avec le même argument créer un nombre qui ne sera pas présent.”
Lui :
“Et mince, en effet. Il est donc impossible d’établir une liste infini de tout les nombres réels entre 0 et 1. Et donc, cet ensemble n’est pas bijectif avec celui des entiers. Donc l’ensemble infini des réels est plus grand que l’ensemble infini des entiers.
C’est assez contre intuitif, mais oui, parfaitement logique.
Vous avez une liste infinie mon cher… on ne peut la supposée complète car elle ne possède pas de dernier terme…
Comme le dernier terme n’existera jamais alors je ne pourrai jamais le vérifier et encore moins poser que ce terme sera égale à une valeur chiffrée quel qu’il soit.
Je vous répondrais que si vous partez du dernier terme et puis que vous passer à l’avant dernier… puis à son précédent et ainsi de suite jusqu’au premier de la liste (en partant du dernier vers le premier plutôt que du premier vers le dernier) et que vous appliquez l’argument à la suite de chiffres produite alors le problème vous apparaitra sous un autre jour…
En fait tout ce que l’argument fourni c’est une méthode pour construire le prochain terme de la liste… un terme qui sera différent de tous les termes précédents… le terme suivant.
Une liste infinie serait complète selon vous… dans ce cas ne serait-elle pas finie tout simplement…
Je vous invite à consulter la littérature sur le sujet. La démonstration que je présente ici est ce qu’il y a de plus trivial dans la théorie des ensembles, et je vois mal comment l’expliquer plus simplement. Une bonne référence en ligne sont les notes de cours de Patrick Dehornoy disponibles sur sa page personnelle :
http://www.math.unicaen.fr/~dehornoy/
Vous pouvez très bien imaginer une liste complète des nombre rationnels et établir une bijection avec l’ensemble des entiers naturels. Dès lors à partir d’une procédure préalablement définie d’énumération, vous me donnez n’importe quel nombre rationnel et en parcourant ma liste je vous trouverais sa position sur celle-ci. En ce sens on peut établir une liste infini complète de l’ensemble des entiers naturel et des nombres rationnels, ce qui n’est pas le cas avec les réels.
Vous parlez d’une liste complète (auquelle il ne manque rien)… mais qui s’étendrait à l’infini… donc qui ne comprend pas de dernier terme car alors elle ne serait pas infini… quel serait le dernier réel de la liste complète que vous projetez de mettre en bijection dans ce cas…
Mon imagination me permettrait de créer une liste qui n’en serait pas une… ou un nombre qui ne serait pas un nombre… ou de fournir une réponse qui serait une question… mais ce ne serait que dans mon imagination.
Poseriez-vous l’infini comme un fait réalisé… un ensemble infini contient-il un dernier terme…
Une liste qui n’est pas une liste, un nombre qui n’en est pas un, désignent des objets par nature contradictoires, donc qui ne peuvent avoir d’existence logique.
>> Poseriez-vous l’infini comme un fait réalisé ?
Bien sûr. Mathématiquement, dans la théorie des ensembles, ces derniers sont considérés comme réalisés, et manipulés ainsi. C’est la distinction même qui est faite entre la notion d’infini actuel (sur laquelle se base la théorie des ensembles) et celle d’infini potentiel datant d’Aristote.
C’est une idée triviale, mais pas forcément évidente. Poincaré lui même la refusait : “Entre autres, à cause de son refus d’accepter l’infini actuel, c’est-à-dire la possibilité de considérer l’infini comme une entité achevée et non simplement comme un processus qui peut se prolonger arbitrairement longtemps, Poincaré est considéré par beaucoup d’intuitionnistes comme un précurseur.” http://fr.wikipedia.org/wiki/Henri_Poincare
Au fond, on peut ou non utiliser ces deux notions. L’important est conserver la cohérence logique du raisonnement, et de bien savoir de quoi on parle quand on parle d’infinis. On peut faire des mathématiques très intéressantes dans l’un ou l’autre des deux cas.
Vous parlez d’objets de nature contradictoires… mais si vous considérez l’infini comme une entité ”achevée” alors c’est qu’elle est bel et bien de nature finie car délimitée et cernée, terminée ou achevée… Serait-ce différent d’affirmer que l’infini est fini que de d’affirmer l’existence d’une liste qui ne serait pas une liste… ou d’un objet qui ne serait pas cet objet…
Prenez le premier terme de la liste de Cantor, si il s’étend à l’infini et est non-périodique (si il se trouve lui-même à être une liste ouverte de chiffres s’étendant à l’infini, donc un terme qui est une liste mais pas la liste) alors comment pourrez-vous savoir que sa dernière décimale est différente de celle du nombre qui le suit dans la liste si il s’étend lui aussi à l’infini et que toutes ses décimales sont identiques à celles du premier terme sauf la dernière… Comment pourrez-vous remplacer ou substituer un chiffre que vous ne pouvez pas connaitre…
Comme vous savez que seulement dix termes peuvent être différent entre eux par leur dernière décimale si ils comptent le même nombre de chiffres et une suite identique de chiffres jusqu’à cette dite décimale… considérez-vous que le onzième terme puisse avoir comme dernièrere décimale PI ou racine de 2 ou même X pour être différent des autres étant donné que le système décimal considéré ne comporte que 10 symboles différents…
Drôle de logique que celle qui affirme que ce qui n’a pas de limite (infini) serait en fait complet (comprenant tous ses termes y compris le dernier)… l’infini ne serait donc pas si infini que ça… tout comme je ne serais pas toujours moi-même en fait…
Je suis d’accord avec messieurs Hilbert et Brouwer… il y a quelquechose qui ne tourne pas rond dans la logique de l’infini actuel.
Comme il n’est pas interdit de substituer un chiffre par zéro (0)… si le dernier chiffre du nombre crée via la diagonale est remplacé par 0 alors ce nombre ne compte pas de dernier chiffre car le zéro est non significatif… il possèdera donc un chiffre de moins que le nombre qui le dénote et le nombre X ne possédant pas de Xième chiffre car ce chiffre vaut (0) se trouvera donc à être dans la liste et non-contradictoire avec le processus de création (diagonale de Cantor) du nombre en question car ne possédant pas assez de chiffres pour rejoindre la diagonale.
1) 0,1
2) 0,11
3) 0,111
4) 0,1111
5) 0,11111
Ce qui donne la diagonale 6) 0,11111
En remplaçant le dernier chiffre de la diagonale par 0 car celui de la diagonale n’est pas 0 et qu’au moins un des chiffres du nombre créé se doit d’être différent de par sa position de celui de la diagonale, alors le terme nouveau sera 0,11110 (soit 0,1111) et donc identique à un des termes le précédant (celui représenté par la 4ième ligne… donc dans la liste. Si vous remplacez tous les termes (1) par zéro (0) alors vous aurez un nombre qui ne fait pas partie (composé uniquement de zéro) de la liste car exclus dans les prémisses elles-même ( compris entre 0 et 1)…
0,1 (1/10) peut s’écrire 0,10 (10/100) ou encore 0,100 (100/1000)…
À moins que le dernier chiffre ne puisse pas être zéro…
N’oubliez pas que le nombre de chiffre (symboles) et la base (10) sont choisis arbitrairement et qu’elle peut tout aussi bien posséder une infinité de symboles différents dans la base que nous dirions infinie… dans ce cas il n’y aurait pas de second termes dans la suite décimale, toute décimale serait constituée d’un seul et unique symbole et la méthode de la diagonale serait innapplicable… de même chaque symbole serait dénoté par son propre symbole… et la bijection serait évidente.
Une base 10 est par définition précise au dixième… une base 100 l’est au centième… une base infinie le serait donc à l’infinitième… donc infiniment précise.
Peut-être ne suffit-il que de partir sur une meilleur base… question de précision.
Donald vous vous trompez de raisonnement. Le raisonnement diagonal construit un contre-exemple pour prouver l’invalidité de l’hypothèse de départ (la dénombrabilité), vous, vous construisez un exemple isolé (ce qui ne prouve rien).
quant- à votre problème de liste en perpétuelle formation, rien n’est contradictoire non plus puisque le N en question est bien fini lui.
L’article de wikipédia présente d’autres formulations de cette démonstration qui sont très claires.
Enfin, les arguments que vous utilisez du genre “comment pouvez vous savoir” n’ont pas de sens puisque c’est bien d’une construction dont il s’agit ici, on “sait” que l’on peut construire une suite de réels telle que …